SRM623-628 Div1E

25問をこえましたね

・SRM623 Div1E UniformBoard

N×Nのグリッドがある.各マスは空か,りんごが置いてあるか,なしが置いてあるかのどれか.K回までくだものを空のマスに動かす操作ができるとき,全てのマスにりんごが置かれているような長方形の面積を最大化せよ,という問題.

N≦20と小さいので全探索が出来ないかとかんがえる.長方形を固定したとき,その長方形の中をりんごで埋め尽くせるかの判定が出来ればいい.まず全体のりんごの数がその長方形のマスの数よりすくない場合は明らかに不可能.また長方形の中になしが含まれている場合,いったんそれを空のマスにどかしてりんごを置く必要があるので,空のマスが1個以上ないとダメ.逆にこれを満たしている場合,長方形内のなしを適当な空のマスにどかし,長方形の外のりんごをそのマスにもってくるという操作(元々りんごがあった所が空になるのでそのマスを使ってこの操作を繰り返せばいい)と長方形内の何も置いていないマスにりんごを置くという操作で長方形を満たせる.操作の回数は(なしの数)×2+(空のマスの数)なのでこれがK以下であればOK.

・SRM624 Div1E BuildingHeights

n個のビルがあり,i個目のビルの高さはheights[i]である.1≦M≦Nであるような全てのMについて「あるビルの高さを1増やすという操作を繰り返して同じ高さのビルをM個以上にするときの操作回数の最小値」を求め,それらのXORをとったものを答えよ,という問題.

ビルを高さの昇順にソートしておき,M個以上のビルをi番目のビルの高さに揃えることをかんがえると(heights[i]-heights[i-1])+...+(heights[i]-heights[i-M+1])=heights[i]*M-Σ[k=0...M-1]heights[i-k]回の操作をすればいい.これはあらかじめ累積和を取っておけばO(1)で計算できるので,各iについて計算していくとO(N)で1つのMに対する答えがわかる.よって全体O(N^2)でとけた.というのが一般的なやり方なのだけど僕はDPしてしまった(DPで片付くこと多いな).あらかじめ高さiのビルが何個あるかを数えておく(これをcnt[i])とする.すると"dp[i][j]=高さiのビルをj個以上作るときの操作回数の最小値"というDPができる.cnt[i]≧jならdp[i][j]=0で,cnt[i]<jならdp[i][j]=dp[i-1][j-cnt[i]]+(j-cnt[i])である.O(N^2)で計算できるので計算量は同じ(けど何故か気をつけないとTLEする).

・SRM625 Div1E PaindromePermutations

文字列Sが与えられる.Sのアナグラム(文字を並び替えて出来る文字列)を任意に選んだときそれが回文である確率を求めよ,という問題.

Sのアナグラムが何種類あるかというのは,おなじみ「重複のある順列」という奴で文字cの個数をcnt[c]とするとき|S|!/(cnt[a]!cnt[b]!...cnt[z]!)種類である.このうち回文であるものが何種類かというのが問題.まず並び替えて回文を作るには奇数個ある文字が1個以下でないといけないのでそれを調べる.次に,例えばS="haha"なら全体にaが2個,hが2個あるので並び替えた結果が回文であるためには左半分にaが1個,hが1個ないといけない,というように左半分(右半分でもいいけど)に含まれる各文字の個数が決まる.そうすると左半分として何種類あるかはまた「重複のある順列」になって(|S|/2)!/((cnt[a]/2)!(cnt[b]/2)!...(cnt[z]/2)!)種類であることがわかる.左半分を決めると右はそれと対称に置くしかないから回文であるようなアナグラムの種類数もこれ.求めるのは(回文であるアナグラムの種類数)/(アナグラムの種類数)ってだけなのだけど,上手くやらないと数が大きくなって計算できないのでdoubleなどで上手くやろう.

・SRM626 Div1E FixedDiceGameDiv1

アリスはa個のb面サイコロを振り,ボブはc個のd面サイコロをふった(x面サイコロは1以上x以下の目が等確率で出るものとする).出た目の和を得点とし,得点が高い方を勝ち.今,アリスが勝ったことがわかっている.アリスの得点の期待値を求めよ,という問題.

アリスが勝ったという前提の下での,アリスの得点がxである事前確率がわかればいい.これは(アリスが得点xで勝つ確率)/(アリスが勝つ確率)である.アリスが得点xで勝つとは(アリスの得点がx)かつ(ボブの得点がx未満)ということ.従ってDPであらかじめアリス/ボブの得点がxである確率を求めておくと,アリスが得点xで勝つ確率がわかり,それを全てのxについて足せばアリスが勝つ確率がわかるのでとけた.

・SRM627 Div1E HappyLetterDiv1

いくつかの英小文字が与えられる(重複もある).このうち種類の異なる2文字を選んで消す操作を繰り返す.操作ができなくなったときのこっている文字を「winning letter」と呼ぶ.winning letterになり得る文字は何種類か?という問題.

ある文字がwinning letterになり得るかの判定をかんがえる.各種類について何文字あるかを数えておき,大きい方から2つ取り出してペアにする(ただし注目している文字は1文字以上のこしたいので文字数を1減らしておき,同数の場合は注目している文字は選ばない)ことを繰り返せばまんべんなく消せそう.というのが自分のアイディアだったが,証明はわからない.

kmjpさんのブログを読むと,ある文字について何文字のこすかを決め打ちしたとき,消すべき文字数が偶数かつ過半数を占める文字が存在しないことを確かめればいいらしい.必要性は明らかだけど十分性は?過半数を占める文字が存在しないという前提の上で僕の方法を用いると全て消せることが示せそう.大きい方から2つ選んで減らすので操作前に条件を満たしていると操作のあとでも条件を満たす.なので条件を満たすまま文字数を減らせていけて,2文字になったときは必ず異なる文字なので全て消せる.うむ,そうすると自分のアルゴリズムの正当性もわかるかもしれない.過半数を占めている文字があったらどうやってもその文字がのこる.そうでない場合,偶数個なら全て消え,奇数個なら注目している文字だけのこる.

・SRM628 Div1E DivisorsPower

整数nの正の約数の数をd(n)としたとき関数hはh(n)=n^d(n)と表される.nが与えられるのでh(x)=nとなる最小のxを求めよ,という問題.

n≦10^18でTLEしないアルゴリズムがわからず人のブログを見た.yを固定してx^y=nとなるxを見つける(y≧10のときx≧70だと10^18をこえるのであり得ないとわかる,など適当にxの最大値を小さくしてやらないとTLEする).yは2^62≧10^18だから62まで調べればよい.x^y=nなるxを見つけたらd(x)=yかの判定をする.また,これだとy=2のときが不十分なので√nが整数かどうかも調べる.さらにシンプルにx^yを計算するとオーバーフローすることがあるのでa*b/b==a(かけて割ったら元に戻る)かどうかもべき乗を計算するときに調べる必要がある.うーん.罠すぎてアレ.