次の日>2013-09-019月に解いた問題8月試してみてモチベ向上につながったので続けます。自由に置ける数字と、そうでない数字に分けて考える。大きなbitを諦めると、下位のbitを任意に調整できることを利用する。左のヘッドから貪欲に進めていく。左に行ってから戻るパターンと、その逆のパターンがある。自分を含む子と、それ以外の頂点でそれぞれ最も遠い感染地を管理。どの頂点をどの子につけるかで全探索。素因数はなるべく細かく分解したほうがオトク。条件を読み解くと、限られた形のグラフしか許可していないことが分かる。各頂点の次数させ分かれば答えが出る。グラフは作らなくて良い。アリスでもボブでも作れない三角形は、アリスの方にある辺が1つか2つと考える。出現順に同じ数字を区別する。人間を半分に分け、それぞれチームを組ませると問題が半分になる。後ろから考えて、なるべく同じ向きが連続するように重ねていく。辺の重みでソートし、同じコストの辺をまとめて考える。dp2[i][k]2.は一見O(N*5000)かかるようだが工夫するとO(N+L)に落ちる。(O(n^3))に思えるが実は罠が。ウイルス文字列と不一致の場合、どの位置まで戻る必要があるかを前計算。貪欲にmodを取ったとき大きい数を使う。prefixとsuffixのハッシュを計算し、prefix=suffixとなる長さを探す。右上or左上から操作していく。10^18以下のフィボナッチ数は90ぐらいしかない。数を貪欲にフィボナッチ数に分解し、更にそれらをDPして分けていく。座標圧縮して二分木を作る。(1,2,4)と(1,3,6)を先に使い、残りで(1,2,6)の組を作ると考える。回路をほどくとは、隣り合う+か-をなくして、空きを詰める操作に相当。1)bを満たす最大のnを見つける問題になる。最終的に現れる数字のセットは、操作の仕方に寄らない。第二問(550点)カウンター296980。