問題概要 頂点数N( 解法 ハッシュを使って、各ノードについて隣接する頂点集合を計算しておく。何故かローリングハッシュ風なハッシュ関数使ってる人多かったけど、順序関係ないんだし乱数列のxorや+で計算する方が楽だと思う。しかしハッシュを使っても重い…

問題概要 1~10^5の数字が書かれたフラグがある。最初は全てオフになっている。以下のQ( iをオンにする。ただし、既にオンになっていたり、他のオンになっている数字と互いに素でなければ素の旨指摘してオンにしない。 iをオフにする。ただし、既にオフになっ…

問題概要 長さL( 解法 何だか謎の制約があるらしいけど無視してDPで解く。文字列の先頭から考えて、dp[i][j] = (i文字目まで見て、残っている直前の文字がjであるような最小コスト)とすると十分間に合う。

結果。 2/5完。Aを後回しにしてBから解いたのはよくて、Cに飛び込んだのも悪くなかった。いずれも解法は割とすぐに見えたし、実装もそこまで大きくハマることはなかったんだけどCのTLEで死んだ。想定解法が(多分)O(N logN)なのにN=10^6ってちょっとひどいと…