AtCoder Regular Contest 067 E. Grouping

もしかしてなんですけどmaroon君が苦手ですか？maroon君がセッターの時は出ないようにします。

 

問題

読めばええ: E - Grouping

 

解法

まあどう見てもDP。

初め人を区別しないと思っていて(どうして？)、詰んだ。

というより全然違う立式をしていた。

人を区別しない時の式はかなりシンプルで、

f:id:potetisensei:20180327021324j:plain

になるので、dp[i][j]をdp[i][j-i]から計算できてO(N^3)からO(N^2)に落ちるねとなる。

これで書き上げてサンプルを試した所で人を区別することに気づく、頭が悪い。

そこから式を書き直した。

f:id:potetisensei:20180327021901j:plain

前の方針に引きずられて、同じ感じでO(N^2)に落としてやろうとしたんだけど、上手くいかない。というのは、どうしても、dp[i][j-i]を使いまわそうとした時に、Σの中の項に掛けるべき定数にkが残るから。

辛いなあと思っていたんだけど、よくよく考えると、「1/(k!) Π ~」の部分は、P(n+ik-j, ik) /(k! * (i!)^k)で書き換えられるなあという気持ちになって(P(n, k)はn個からk個選択して順列を作る場合の数)、その上「C ≦ k ≦ min(D, j/i)」だなあと思って、あれシグマの中身の計算O(NlogN)回で抑えられるじゃん(よくある区分求積を考えれば自明な奴)となってO(N^2logN)になって終わった。

引きずられたのもどうかと思うし流石にこういう典型が解けないのは反省したい....

AtCoder Regular Contest 083 D. Restoring Road Network

結構面白かった。

 

問題

読んで: D - Restoring Road Network

 

解法

Warshall-Floyd法を考えれば、与えられたテーブルが条件を満たしているかは、Warshall-Floyd法内で行う更新を行っても値が変化しなければ良いことが分かるので、こっちは自明。

問題はグラフの復元で、初め、incrementalに、つまり、辺が1つもない状態から、長さが最小の辺から順に、追加するか決めていこうとしたんだけど、毎回全点間最短経路の更新にΘ(N^2)掛かりそうで、辺はΘ(N^2)個あることを考えるとΘ(N^4)になるなあと思っていた。

ここで面白いのは、逆にdecrementalに、つまり全ての頂点対間に、最短経路長と同じ辺が張ってあるようなグラフを元にして、そこから長さ最大の辺から順に消していくことを考えるとうまくいく。

辺を追加することによって最短経路が更新され得る点対の個数はO(N^2)であり、「辺を追加すべきか」の判定に必要な情報を保持しておくにはΘ(N^2)掛かってしまうが、「辺(u, v)を削除すべきか」を考慮する際に必要な情報は常に変わらない。しかも、見るべきはu, v間の最短経路長が変わるかどうかのみであって、これはO(N)で判定できる。これもWarshall-Floyd法を想像すればすぐ分かる。

AtCoder Regular Contest 072 D. Alice&Brown

すんなり解けた割に納得がいかなかった。今日結構500点問題色々見たけど、安定しないなあと思うし本当によくこれで赤色目指すみたいな気持ちでいれましたねみたいな感じ。

問題文

読んで: D - Alice&Brown

 

解法

正直なんで解けたのか分かっていない。なんで解けたのかというのは、別に解法自体を理解していないということではなくて、解法を思いつくまでの考察の仕方が分からないという意味で、つまり今後同じ系統の問題が出題された場合にちゃんと考察を順に詰められる気がしない...

とりあえず考察するに当たってやったのは図示で、結局、変なベクトルを基底にした格子みたいなのを、一方向に好きなだけいけるので、ゴールに辿りついた人の勝ちみたいなイメージになる(下図)。

f:id:potetisensei:20180323230556j:plain

この時、書いた図がたまたまとても運が良くて、(4, 4)スタートだったのがかなり功を奏してる気がする、まぐれで解いてしまった。

一応ゲームの定石としてまあ「後手が先手を真似る奴」というのがあるわけですが、(4, 4)とかはまさにそのままになっていて、先手がここからどう動こうと、それとy=xで対称な動きを後手は必ず出来て勝てるなあという気持ちにはなった。

ちょっと一般化すると、a < bであるような(a, b)について、「a < i ∧ b ≧ 2i」でない限りは、先手が(a+i, b-2i)に動いたら、後手は(a-i, b-i)に出来て、y=xに平行に動ける。

で後は、(4, 4)スタートの場合はゴールは(0, 1)なわけですが、(0, 0), (1, 0), (1, 1)もゴールになりえて、かつこれらの内1つしかゴールにはなりえない(つまり例えば(0, 1)にも(1, 1)にも行けるという状態はありえない)ということも自明な考察としてした。

ここで問題になるのは、「a < i ∧ b ≧ 2i」が成り立つ時、例えば(0, 8)みたいなスタートでは、真似が出来ないだろという気持ちになったんですが、よくよく考えると(0, 8)からは(3, 2)に動けて、ここからはさっきと同じことになるなということに気づき、結論としては初めから|a-b| ≦ 1なら後手が勝つし、そうじゃなければ必ず初手で|a-b| ≦ 1になるように動かせるから先手が勝つという結論になって、まあ実際正しかった。

 

正直どういう風に考えればシステマチックに解けるのか分からん

 

追記:

grundy数見たら結構自明だね。便利。

00 00 01 01 02 02 03 03
00 00 00 01 02 02 03 03
01 00 00 00 01 01 04 03
01 01 00 00 00 01 02 02
02 02 01 00 00 00 01 01
02 02 01 01 00 00 00 01
03 03 04 02 01 00 00 00
03 03 03 02 01 01 00 00 

 

AtCoder Grand Contest 013 B. Hamiltonish Path

頭が悪すぎて絶望したので反省に書いておく。

この問題の概要を読んだのは3週間前とかで、今まで普通に解けていなかったし、結局 さっきAcceptはしたものの嘘解法であることに気づいたし最悪。

500点問題もまともに解けないとかもはや、やってる意味はあるんだろうか.

 

問題概要

読んで: B - Hamiltonish Path

 

(嘘)解法

とりあえずDFS-treeか関節点辺りが大事なんじゃないかなと思える(まあ解説を読むとその時点で間違ってるんですけどね)。

特に、DFS-treeに関しては

  • 任意の方向付けされた後退辺(u -> v)について、vはuの祖先

という結構良い性質があるわけなので、DFS-tree上の葉を端点として、rootを通るようなpathを考えれば、絶対に問題の条件を満たせることが分かって嬉しい。

ということで、初めの内は、本当に任意のDFS-tree上で解く方法を探していたんだけど、全くうまくいかなかった。

これもめちゃくちゃ頭が悪いポイントで、わざわざ任意の状態を考えて一般化しようとしなくても、constructiveな問題なのだから、恣意的に考えるDFS-treeを決めて良いわけだし、直感的に関節点が大事そうという気持ちになったのにその考えを捨ててしまっている...

 

DFS-treeの根vに関して以下は同値である。

  • vは関節点
  • 後退辺を除いた上で、vの次数が2以上

つまり、上の考察も合わせて考えると、与えられたグラフに関節点が含まれるならば、それを根としたDFS-treeを作れば、必ず根を通り葉同士を繋ぐようなpathをtree上から持ってこれて、それを回答すれば良い。

 

従って、後考えなければならないのはグラフが1つも関節点を含まない状態ということになる(つまり二重連結なグラフ)。

この状態においては、DFS-treeの根の、(DFS-tree上の)次数は1である。

当然、後退辺が引かれている可能性があるから、元のグラフ上においても次数が1とは限らない。

逆に元のグラフ上においても次数が1であれば、これは自明なケースとして処理できる。理由は、DFS-treeの適当な葉から根へのpathは全て条件を満たすから。

 

従って、これから考えるケースは、根への後退辺があるものとして仮定して良い。

ここで突然異常な嘘が発生するんだけど、何故か暗黙に以下を仮定してしまった。

  • 必ず、根への後退辺を持つ葉が存在する

今思うと頭がおかしすぎるんだけど、この仮定の元では確かに以下のような構成で解ける。

  1. 上記の条件を満たす葉sを見つける。
  2. sの先祖であって、子を2つ以上持つ(すなわちDFS-tree上で次数が3以上の)頂点tが存在するか調べる。ただし、そのような頂点が複数存在する場合は、葉から最も近いものとする。
  3. tが存在しなければ、sから根へのpathが答え。
  4. tが存在するならば、tの子であってsの先祖であるような頂点u(これはs自身である可能性もある)を始点として、「u -> s -> 根 -> t -> sのt以外の子 -> 適当な葉」というpathが答え。

図示するとこんな感じ。

f:id:potetisensei:20180323162102j:plain

何故かこれで解けたつもりになって、実装を初めてしまった。

結果としてはバグりまくったけど、このままの方針でACしてしまった。

まあテストケースがそもそも16個で少ないし、問題の性質上、正直複数のヒューリスティクスを入れたコードとか、乱択とかを落とすのが大変そうだし、仕方ないかなという気はする。

ちなみにACしたコードは以下のようなグラフを与えると普通に落ちる。

f:id:potetisensei:20180323162633j:plain

まあ「根への後退辺を持ってる葉」が存在しないから当たり前ですね。

ただ、前述のように、根の選び方とか、DFS-treeの構築を乱択にすると、「根への後退辺を持ってる葉」が発生しそうな気もしている(逆にどのように構築しても、そのような葉が存在しない二重連結なグラフって存在しますか？)。

こればっかりは分からないし、本番でもしもっとテストケース強かったらペナルティ覚悟でそういう乱択試すとは思うけど、ちゃんと素直に解きたかったなあ...

 

想定解法は、めちゃくちゃシンプルなんだけど、正直思いつける気が今でもしていないし、ここまで頭が悪いと人生やめた方がいいですかという気持ちになる

AOJ 0581 お土産購入計画 (Gifts)

2012年の情報オリンピック予選の6問目。当時解けなかったのは当然としても、今見ても結構つらい問題で、5年越しにようやくACしたのでなんとなくブログに書いておく。

 

問題文

まあ日本語なので読みましょう

お土産購入計画 | Aizu Online Judge

 

解法

流石にbitDPはしたくなって当然。

単純に考えると

dp[y][x][k][hash] := 「地点(x, y)におり後k回遡れる状態で、マンハッタン距離が3以下であるような周りの点の内辿ったことのある点の集合がhashで表される時の、それまでに買えたお土産の最大個数」

というdpを立てたくなる。

本質はその計算量で、この状態では、S = {マンハッタン距離が3以下であるような周りの点}としてO(HWK * 2^|S|)であり、|S|=24であることを考えると、概算としてこれは50*50*3 * 2^24 = 125829120000であって到底間に合わない。

ただこれには相当な無駄があって、例えば以下のような状態というのは考えなくて良い。

　　　　　　　　　　　f:id:potetisensei:20171204101457p:plain

 

ここで、黒は今自分がいる点であり、オレンジは既に辿った点を表している。

このような状態になるためには、下と右のオレンジのラインの両方を辿り、黒に戻ってくるという遷移が必要で、これはKが6以上じゃないと不可能。

もっと変なケースを考えると一瞬怖い気持ちになるが、そもそもhashで持つのは既に辿った点の集合であるということに注意すると、更に考えなくていい状態が多いだろうと考えられる。

逆に考えなくてはならない状態の内、最もオレンジの個数が多いものは、こんな感じになる。

　　　　　　　　　　f:id:potetisensei:20171204102540p:plain

 

これは例えば右下下左上上と動くことによって達成できる状態で、この時点でk=0となる。

本当に最大か？？もうちょっと増えない？？という気持ちに一瞬なるが、まず、遡る動きをすると、kの数が減り、記憶しておかなければならないオレンジの位置が減ってしまうので、出来るだけオレンジは右下に来るようにしてよい。で、この状態になるまでの動きには無駄がない(黒に戻ってくる動き以外の全てで、オレンジの数が増えている)。そして、仮にここから下や右に移動したとすると、オレンジの丸が増える時には、少なくとも1つ以上の元々あるオレンジがフェードアウトするので、これ以上増えることはない(はず(本当か？(一応__builtin_popcountでhash計測したら5が最大だったょ)))。

したがって、大きく見積もっても、2^24通りの内、考え無くてはならない状態の上界は

Σ[i=0..5]24Ci = 55454であって、55454 * 50 ** 2 * 3 * 4 = 1663620000 = 1.7*10^9な時点で、JOI予選本番中であれば、普通にGOサインを出す判断ができる。

また、この上界はかなり余分めに見積もっているのは明らかで、本当に発生しうる状態のみを計算するように真面目に書けば、普通に少なくとも10分の1ぐらいにはなりそうに思える(そもそもオレンジが5個あるケースというのは、さっきの2x3の長方形しかないはずで、24C5どころか8通りしかないように見える)。実際、適当に書いても1秒以内でAC出来た。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2632622

ちなみにJOIの公式の解説には「考えなければならない近傍は高々12個で状態は2^12なので余裕です」と書いてあるが、正直これはまだ理解できていない。仮に考えなければならない近傍が12個だったとして、その近傍の位置が固定されていればそれは当然2^12だが、実際には固定されていないはずでコンビネーションが出てくるべきなわけで、2^12という見積もり方は嘘なんじゃないかと思うのだけど、誰か分かる人おしえてほしい。

 

 

 

符号でバグってそうだったら-Wsign-conversionも使おうねという話

TL;DR的にはタイトルまんまです。

CodeForcesでまあこんな感じで激冷えしてしまったんですが、

f:id:potetisensei:20170712054419j:plain

原因の一端に、自分がコンパイラオプションを正しく認識していなかった事もあった上、ほとんど日本語でも英語でも、似たような現象に悩まされてそうな人がいなかったのでブロガーしちゃう。

さて、本質的に何が原因でバグっていたかというと、

vector<int> a(3);
int i = -1;
a[(a.size() + i%a.size())%a.size()] = 1;

こういうコードがあったとして、これがa[2]=1になることを期待してしまっていたことに起因している。

バグった時点で、薄々signedからunsignedとかの暗黙な変換が起きてるんだろうなーとは思っていたので、-Wconversionオプションをつけてコンパイルとかしてみたものの、一切なんのwarningも出なかった。そのせいで、思い過ごしかと思って全然違うところの修正をしてしまったりした挙句9ペナぐらい食らってしまった。もちろん上のコードに対しても、少なくとも僕の環境(Ubuntu16.04デフォルトのg++ (GCC) 6.3.0)では-Wconversionオプションではwaningが出ない。

どうすればいいのかなあと思って検索してみた所、-Wsign-conversionなるものがあるらしいということに気がつき、試してみた所ちゃんと検出されてwarningが出た。

まあどうせ100行ぐらいのコードだから暗黙な変換が起こりそうな場所ぐらい覚えておけよという話なんだけど、変にコンパイラオプションに頼ろうとして痛い目を見た経験は中々ないし覚えておかないとまたやってしまいそう。

 

ちなみに、clangだと-Wconversionつければ勝手に-Wsign-conversionも有効になるっぽい。ただ-Wsign-conversionは-Wsign-conversionで、競プロだとsignedな値で配列参照することがあるだろうから、vector::atに対してsignedな添え字で参照することに対して毎回怒られるのはちょっと面倒かもなあという気もする。まあバグってそうだったらつけて見て、配列参照の部分は無視すればそこまで大変でもないかな？

 

MP法とKMP法の違い

大学生なのでデータ構造とアルゴリズムという授業を取っているんですが、今まで自分がKMP法だと思い込んでいたものがMP法だった上、ネット上の記事が無限にバラバラなのでメモしておく。

 

MP法

MP法はMorris-Pratt algorithmと呼ばれるもので、Knuthが登場しない。

MP法では、パターン文字列に対してborderと呼ばれる値を計算することにより、シフト量を定める。

ある文字列Sのborderとは、Sの部分文字列であって、Sの接頭辞かつ接尾辞であるような文字列Wのことである。

MP法では、i=0..|S|に対して、S[0:i-1]の最長border(の長さ)をO(|S|)で求め、それを元にシフト量を決める。具体的な最長borderの求め方については、snukeのこの記事が一番分かりやすいのでこれを見るといいと思う。

snuke.hatenablog.com

 

さて最長borderが求まれば、1-originとして、j文字目で不一致した場合のシフト量はj-border[j]とすればよい(配列インデックスと何文字目を表すかのoriginの違いによって、±1となる可能性があるので気をつけること)。

結局、MP法とはどちらかというと、borderを計算することの出来る線形アルゴリズムという側面が強く、別に文字列検索にだけ使うようなものではない。

例えば検索文字列自体を検索する用途以外でMP法を使う例としては以下の問題などがある。

codeforces.com

 

KMP法

KMP法はMP法にKnuthがくっつくやつで(は？)、上記のborderによるシフト量の決定には、まだ定数の改善余地があるため、それを改善する。

ある文字列Sの、接頭辞Pを考える。

すなわち、S = P + Xである(ここで+は文字列のconcatenate)。

ただし、 PやXが空文字列であるとちょっと困るので、P' = P + '_', X' = X + '_'というように、末尾に番兵があることとする。

Pのtagged border(あるいはstrict border、strong borderともいう) Wとは、Pのborder Wであって、かつP[|W|] != X[0]であるものを指す。

MP法におけるシフトの何に無駄があるかというと、S[i:i+j]が、pat[:j]までのj文字が一致していて、S[i+j]とpat[j]で初めて不一致が起きた時、当然シフトが発生して、次は、pat[border[j]:]とS[i+j:]が一致しているかを比較し始めるわけだが、仮にpat[j] == pat[border[j]]であったとすると、このシフトはまだ不十分であるということになる。

なぜなら、今、不一致が起きたからS[i+j] != pat[j]であって、かつpat[j] == pat[border[j]]であるから、明らかにpat[border[j]] != S[i+j]となって、pat[border[j]:]とS[i+j:]は先頭からして一致しない。

よって、borderの中でも、P[|W|] == X[0]を満たすようなborderは文字列検索においては考えなくて良いことが分かり、そうでないようなborderの中で最長のものをシフト量の決定時に使えば、少し検索の定数が減ることが分かる。

実装はMP法からほとんど変わらないため、コストのかかる改善ではない。

例えば上記のsnukeのコードを、以下のように変更するだけでいい。

A[0] = -1;
int j = -1;
for (int i = 0; i < S.size(); i++) {
  while (j >= 0 && S[i] != S[j]) j = A[j];

  j++;
  // 元のコードでは A[i+1] = j;
  if (S[i+1] == S[j]) A[i+1] = A[j]; 
  else A[i+1] = j;
}

elseの部分は、元のコードと変わっていないので当たり前に受け取れる。

問題はif文の後のA[i+1] = A[j]という処理で、何故これでいいのかというと、

まず、帰納的に考えれば、j < i+1より、A[j]は既に正しく計算された値である。

したがって、S[A[j]] != S[j]が成立しており、S[i+1] == S[j]ならば、明らかにS[i+1] != S[A[j]]が成り立ち、MP法と同じ議論からこれは最長tagged borderでもある。

初め僕は「なんでwhileじゃなくてifなんだ？？」と思ってたけどまあこういう理由から、「A[i+1] = j; while (A[i+1] > -1 && S[i+1] == S[A[i+1]]) A[i+1] = A[A[i+1]];」とかしなくても良いということが分かる。

終わり。