2017/10/22の精進

AtCoder400点埋め

・ARC074C Chocolate Bar

適当な所で縦(横)に分割して、のこりを出来るだけ均等に分割するときだけをかんがえればいいとわかる。

・ARC075D Widespread

にぶたん。k回爆発を起こすと全モンスターにB*kのダメージが入り、追加でA-Bのダメージをk回与えられる。よってB*kのダメージで消滅しなかったモンスターを全て消滅させるのにA-Bのダメージが何回必要かを計算し、k回以下ならOKと判定できる。

・ARC078D Fennec VS. Snuke

頂点1からの距離が頂点Nからの距離よりも短い(か等しい)頂点は黒く塗れ、そうでない頂点は白く塗れる。(頂点1を根としてみると、結局取り合いになるのは頂点Nから根へのパス上の頂点だけなので)

・ARC080C 4-adjacent

奇数があるときは、奇数 4の倍数 奇数 4の倍数 ... 奇数と並べる必要がある。もし奇数と4の倍数しかないなら、(4の倍数の個数)≧(奇数の個数-1)でOK。4の倍数でない2の倍数があるときは、2の倍数 2の倍数 ... 2の倍数 4の倍数 奇数 4の倍数 ... 奇数と並べることになって(4の倍数の個数)≧(奇数の個数)でOK。

・ARC081D Coloring Dominoes

隣り合うドミノのパターンは(横 横)(横 縦)(縦 横)(縦 縦)の4つ。左から塗り方を決めていくと、次のドミノの塗り方が何通りあるかはこのパターンで決まる。

・ARC082D Derangement

p[i]==iを満たすiがあるとき、p[i]とp[i+1]を交換すればいい。(この交換でp[i]!=iかつp[i+1]==iとなり、はじめp[i+1]==i+1だった場合2つ消せる)

・AGC002B Box and Ball

現時点で赤いボールが入っている可能性のある箱がわかっているとする。このとき、赤いボールが入っている可能性のある箱から1個取り出して適当な箱に移すと、移した先の箱も赤いボールが入っている可能性のある箱になる。また1個取り出したあと箱が空になってしまったら明らかに赤いボールが入っている可能性はなくなる。

・AGC003B Simlified mahjong

同じ数が2枚以上あるときは2枚ずつペアにしていけるので最終的に各数は1枚以下になる。あとは小さい方から隣り合うものをペアにしていく。

・AGC005B Minimum Sum

全ての区間についての最小値の和を求める問題。逆にa[i]が最小値となるような区間がいくつあるかと考えるとわかる。これはj<iかつa[j]<a[i]となる最大のjをl、i<jかつa[j]<a[i]となる最小のjをrとしたとき(i-l+1)*(r-j+1)個である。

問題はこのようなl/rを求める方法で、自分はスタックに(値,位置)のペアを入れていく方法でやった。a[i]がスタックの先頭の値より大きい間とりだしていって、小さくなったときの位置がl。(自分より大きい値の位置がのちのち答えになることはないので捨てていい)

・AGC006B Median Pyramid Easy

同じ値が2つ並ぶと、他の値によらずその上にも並び続けるということを利用すればいいらしい。

・AGC007B Construct Sequences

r[i]=a[i]+b[i]が何番目に小さいか、とおく。(このときr[p[i]]=iである)

するとa[i]+b[i]=C+r[i](Cは定数)となるよう定めればi<j⇒a[p[i]]+b[p[i]]<a[p[j]]+b[p[j]]を満たす。

あとはaが単調増加・bが単調減少を満たす必要があるが、これはa[i]=30000*i、b[i]=30000*(N-i)+r[i]とすればいい。

・AGC008B Contiguous Repainting

上書き操作を繰り返すときは逆順から見ると未確定のマスの色を確定していく操作になるという奴。(逆順から見て)最初の操作でKマスの色が確定するが、それ以外のマスは1マスずつ自由に色を確定していける。

・AGC011B Colorful Creatures

Aをソートしておく。i番目の生き物が他の全ての生き物を吸収できるかは簡単に判定できるのでにぶたん。

・AGC015B Evilator

S[i]=='U'のとき上には1回、下には2回で行けて、S[i]=='D'のとき上には2回、下には1回で行けるので算数をする。

・AGC017B Moderate Differences

d[i]=A[i+1]-A[i]とおくと、C≦d[i]≦Dまたは-D≦d[i]≦-Cを満たすdでd[0]+d[1]+...+d[N-2]=B-Aとなるものがあるかという問題になる。

ここでd[i]>0であるようなiがk個あるとすると、C*k-D*(N-1-k)=(C+D)*k-D*(N-1)≦d[0]+d[1]+...+d[N-2]≦D*k-C*(N-1-k)=(C+D)*k-C*(N-1)となる。この不等式を満たす和は全て作れるのでB-Aがこれを満たしているかで判定できる。

・CODEFESTIVAL2016予選A C 次のアルファベット

辞書順最小の性質から前の方が良ければ後ろはなんでもいいので、aにできる文字はaにしていけばいい。あまった分は最後の文字に対してやる。

・CODEFESTIVAL2016予選C C 二人のアルピニスト

高橋くんの情報からT[i-1]<T[i]ならi番目の山の高さはT[i]に確定、T[i-1]==T[i]ならi番目の山の高さはT[i]以下ということがわかる。青木くんの情報と合わせると、情報が矛盾しているか、矛盾していないなら未確定の山の高さは何通りかがわかる。

・CODEFESTIVAL2016 C Interpretation

人と言語を頂点として、人がある言語を話せるとき頂点間を結ぶと二部グラフになる。このグラフにおいて全ての人が連結かを調べてやればいい。

・CODEFESTIVAL2017予選A C Palindromic Matrix

幅と高さの偶奇によって同じ文字の4文字セット、2文字セット、1文字セットがいくつ必要かが決まるのでそれがとれるかを試してやる。

・DISCO2016予選 C ロト2

B[i]=gcd(A[i],K)とするとA[i]*A[j]がKの倍数⇔B[i]*B[j]がKの倍数。Kの約数の個数は大きくならないので、これならば二重ループが回せる。

・みんなのプロコン予選 C 検索

検索ワードを前から1文字ずつ決定していく。i文字目を決定するとき、検索結果に表示する全サイトのi文字目が一致していなければダメ、表示しないサイトのどれかとi文字目まで一致していたら続ける、そうでないなら終了というように判定する。