問題概要 H*W(H,W 解法 基本的には分裂するgrundy数なんだけど、斜めのチョコレート割の扱いに困った。y+xとy-x(+W)の下限と上限を持っておけばうまく処理できる。

問題概要 H*W(H,W 解法 行or列の和が負になっているところを見つけてはフリップを繰り返す。フリップの度に全体の和は増加するのでこの手順は高々2*10^6回程度で終了する。ただし最大性についてはまだ理解できていない。そんな直感に反しているわけではない…

問題概要 フィボナッチ数列の第L~R項までの中から異なるK個を選んでGCDをとる。GCDのとりうる最大値を求める問題。0 解法 まず、gcd(F[i],F[j])=F[gcd(i,j)]が成り立つ。したがって、[L,R]内に倍数をK個以上含むような最大のTについてF[T]が答となる。 [L,R]…

問題概要 山がN( 解法 問題をほどくと、K分木の頂点に番号を降って(深さ*値)の和を最小化する問題だと読み替えられる。こう読み替えるともう解けたも同然で、自明に貪欲が最適となる。

問題概要 N(ハノイの塔で、3つある柱のうち隣接する柱にのみ移動することができる。最小手順を求める問題。 解法 f(n+1) = 3*f(n) + 2なので、これを解いてf(n)=3^n - 1

結果。 2/5完。Bで、「これは間違えようがないだろう」と思っていたのに5WAも出してしまった。これに尽きる。残り時間で取り組んでいたCはAC率の低い難問だった。

問題概要 H*W(H,W 解法 状態数が少ない(15*15*4^8で抑えられる。頭の位置+前からの差分)のでBFSで間に合う。これで十分なんだけどBBでも解ける。ゴールから各マスへの距離を事前にBFSで計算しておき推定値にする。これだけだとTLEするけど、スネークの頭が他…

問題概要 H*W(H,W 解法 列を全部0or1にするコストを前計算しておく。後は今見ている列と今の列の色と直前の連続する長さを状態にとって簡単なDPに落ちる。W

問題概要 十分長い0の後に1がある。これから、直前k( 解法 sを作るには貪欲でやってよい。まずsを越えるまで数を列挙し、後は大きいものから選べるだけ選んでいく。また、部分和が2以上でないといけない制約があるのでそのときは0を利用する。

問題概要 サイコロ(2種類ある)のタワーがある。見えている2面とてっぺんの面が与えられるので矛盾がないか判定する問題。 解法 てっぺんの数とその7の補数が側面で見えたらダメ。見えている2面の和が7になったらダメ。

結果。 3/5完。最後の一問は仕方がないとして、Cで無駄なWAを出したのはよくない。DのWAは、惜しかったといえば惜しかったのだけど状態数が少ないという事実に気づけなかったのは不味い。しかも最近似たような問題解いたばかりなのに。

問題概要 数列Aに対して、f(A)[i] = sum_{j 解法 ひっくり返して考えると上三角Toeplitz行列なので、巡回行列と同じように行列を圧縮して持つことができる。よって積がO(N^2)で計算できるので後はバイナリ法で累乗を計算すればよい。

問題概要 文字列S,T(長さ 解法 Sの各文字について、その文字は部分列Tのk番目になれる、の最大のkを計算しておく。ついでに、後ろから見たものも計算しておく。後は前から見たときと後ろから見たときでその文字を含む部分列=Tが存在するかどうかが判定できる…

問題概要 丸括弧と角括弧の列(L 解法 丸括弧と角括弧をそれぞれスタックに積んでいく。途中で括弧が足りなくなったり、対応してないものに当たったりしたら全部クリアすればよい。

結果。 遅い1完でひどい出来な回だった。しかし普通に実力不足な気もする。Cの方が簡単だったにも関わらず読まずにBに飛び込んだのも問題だった。とはいえ結局は実力不足。

問題概要 サイズM( 解法 末尾の文字を状態にして行列累乗でDPする。

問題概要 長さN( 解法 Aを降順にソートして、BからA[i]+B[j]>=Xなる最小のjを求める。しゃくとりっぽくやってもよいけど、どうせソートでO(N*log N)なので二分探索でよい。

問題概要 長さN( 解法 A,Bの各要素をそれぞれ素因数分解してどちらに分配するか求める。このとき、適当に分配すると長さ10^5以下などを満たさなくなる可能性があるので、元の数列を修正するような形で行う。素因数分解は素数表を作っておいて高速に行う。

問題概要 H*W(H,W i行目とj行目をスワップする。 i列目とj列目をスワップする。 i行j列の要素を出力する。 解法 実際に全ての要素を置換せずにindexの示す先だけをスワップすればよい。

問題概要 長さN( k番目の要素を末尾に追加する。 先頭の要素を消す。 を何回繰り返したら全てが同じ要素になるか求める問題。同じにならないなら指摘する。 解法 dequeを使ってシミュレーションする。収束するとしたら高々Nくらいなのでその程度回して無理な…

結果。 5/5完。全体的に易しめなセットだった。

問題概要 長さN,M( 解法 全探索。

問題概要 長さN( 解法 独立な問題をN個解く。各点での最適解は全部まとめるかペナルティを得ない範囲で可能な限り詰め込むかの2択なので小さい方を選べばよい。

問題概要 1~N(N 解法 max-heapに区間を突っ込んでいけば良い。ただし、heap内の区間を削除したりすることがある。pairing heapなどのheapを使ってもよいが、ポインタを利用して直接中身をいじることでも対応できる。

問題概要 頂点数V( 解法 適当に根を決め打ちしてDFSなどで各部分有向木について向きが逆になっている辺の個数などを求めておく。 この情報があると、各頂点について根に選んだとき入れ替えなければならない辺の本数を求めることができる。 図の青で囲んだ部…

問題概要 AからK文字のアルファベットを使用した長さN( 解法 多分貪欲でも行けるはず。何だけどコンテスト中はDPに走った。dp[i][j]={i-1文字目がjであるときのそれまでの最適値}とすればよい。なぜか愚直なDPの計算量O(N*K)だと勘違いして、書いてる途中でO…

結果。 C,Dを解くのに時間がかかってしまったのと、Eで賢い実装方法を思いつかなかったのがよくない。最初に良くない実装方法を思いついてしまったときの修正能力が低いというのは前から気づいている問題点なんだけど、一度解ける解法が見えてしまうと中々そ…

問題概要 3つの文字列がある。全ての文字列を部分文字列に含むような最小の文字列の長さを求める問題。文字列長 解法 まず他の文字列に含まれる文字列は消す。その後、Z-algorithmでA-B, B-Cについてlongest prefixを求め、その分をA+B+Cから引く。順番につ…

問題概要 X=0, Y=1が初期状態である。今、X:=X+YかY:=X+Yという操作を繰り返す。ただし初手はX:=X+Y。今、N( 解法 TwoRegisters。によく似た問題。互除法っぽく計算する。長さが丁度Nになるかは、もう一方のレジスタの値がどうなってるか全探索する。このと…

問題概要 平面上にN( 解法 一つの点を置くことによって3つ以上の連結成分をつなげることはできないので、追加前の連結成分の個数を数えるだけでよい。