問題概要 グラフに辺が加わったり削除されたり連結判定をしたりする。ノード数、クエリ数は40000以下。 解法 夏合宿で全然解けなかった問題。クエリの平方分割というのを初めて知った問題でもある。 クエリを平方分割すると、当該バケット内でずっとくっつい…

問題概要 ノード数V( 解法 DAGなのでDP。スタックオーバーフローするので再帰は避ける。

問題概要 2^62以下の整数を素因数分解する。 解法 ポラードローした。

問題概要 スライド最小値。定数倍厳しい。

問題概要 線分の交差判定と連結性判定。蟻本で紹介されている問題。

問題概要 カードを交互に引いて和が31をこえるかどうかで勝負したときどちらが勝つか判定する。 解法 典型的なゲーム木探索。

結果。 virtual participateした。4/5完。最後の一問は寝落ちした。

問題概要 VとUの二部マッチング(サイズN,Mは20以下)の個数を求める問題。 解法 既に使用したグラフの集合を持ってビットDPする。 ビットカウントがひとつずつ増えることに着目するとビット演算を用いたコンビネーション列挙で計算量はO(2^M*M)となる。

問題概要 文字列をあるルールで置換した後回文になっているかどうか判定する問題。

問題概要 数独を解く。 解法 蟻本の解説通り分岐の少ないものから決定する。

問題概要 平面上にN( 解法 ICPCの国内予選に似た問題が出てた気がする。幾何の定石に従って2点が円上に動くまで動かす。

問題概要 牛がC( 解法 何も考えずにDinicで通したけど(ギリギリ)、後になって蟻本を見たらプライオリティーキューがヒントになっているらしい。

問題概要 フラクタルな図形が表すグラフ上でのパスが与えられる。元の位置に戻っているかどうかを判定する問題。 解法 同じ文字が続いたらキャンセルしあう。5/8回転は3/8回転に置き換える。の2点だけで解けた。証明はしていない。

問題概要 既に埋めこまれたノード数N( 解法 夏合宿で解いた問題。懐かしい。 要は閉路を作らなければよいので、最大全域森をつくって使わなかった辺の長さを足し合わせれば良い。

問題概要 ノード数N( 解法 始点からの距離を求めておく。求めるのは、コストの和をTとするとmin{2*T+v[0], 2*T-dist[i]+v[i]}となる。

問題概要 幅L( 解法 見た瞬間に二分探索+貪欲。

問題概要 ノード数N( 解法 ビットDP。計算量が怪しくても大きいケースだけ埋め込めば通る。 個数制限なしナップザックみたいにやるとO(N*M*K^2*2^K)で解ける、と思ったけどまだ落ちてO(N*M*K*2^K)でいける。

問題概要 数字と.が書かれた長さ3のピースがN( 解法 左端と右端をどれにするか全探索する。全部数字なパーツも左端、右端の候補に入れた。そっちのほうが場合分け減らせてよい。 ピースが連結しない場合とかもあるので注意。

結果。 300だけしか解けずに残念な感じだった。450は計算量が結構怪しい解法を思いついて、しばらく他の解法ないかなーと考えたのち怪しい方法を実装した。ところがK=8のケースで一部TLEした。結局修正できずに終了してしまったけど、後から考えると埋め込み…

問題概要 ある二次元ボードが調和的であるとは自分を含む5近傍の和がmod 2で0となるときにいう。H*W(H,W 解法 mod 2での連立1次方程式を解けばよい。このままだとMAX_W^6でTLEするがビット演算を使って高速化すれば通る。埋め込みはファイルが大きくなりすぎ…

問題概要 山の数N( 解法 よく知られているし、問題文にも書いてあるがNimはA[i]のxorが0なら負け、そうでなければ勝ちである。つまり自分の手番ではxorが0になるように取らなければならない。X=A[0]^A[1]^..^A[N-1]とする。このとき、A[i]からm個の石をとっ…

問題概要 01の二次元配列が与えられる(N*N, N 解法 サイズに関して二分探索+累積和で前処理をかけておくことによりO(N)で判定できる。

問題概要 二つの完全グラフ(サイズ200以下)の間にいくつか辺がはられたようなグラフがある。最大クリークを求める問題。 解法 元のグラフのcomplementを考えると二部グラフになっていて最大独立集合を求めれば良いことが分かる。なので|最大独立集合|=|V|-|…

問題概要 進数変換するだけ。

問題概要(適当) 少しルールが複雑なNimで先手勝ちか後手勝ちか判定する。 解法 典型的なゲーム木探索。特に計算量を落とす必要もない。オンラインRMQとか使えば計算量落とせる。

問題概要 N個のノードが連結されていくので、その度に連結成分の個数を出力する問題。 解法 union-findするときにサイズの情報も持っておく。

問題概要 X[i], Y[i], Z[i]が与えられる。各iについて、初項X[i]、公差Z[i]、末項Y[i]以下の最大のもの、について出現回数を数えると、全て偶数orどれかひとつだけ奇数になっているという。ひとつだけ奇数のものがあればその数と出現回数を求める。 解法 出…

結果。 virtual participation。4/5問解いた。Dで累積和の計算間違えて1時間消費して、続いてBで進数変換間違えたときはひどい気分になった。最後の問題はビット演算で無理やり高速化して通したけど綺麗に解けるんだろうか。

結果。 5/5完できた。易しめの難易度だったと思う。

問題概要 1*N( 解法 状態を(左端は空かどうか、右端は空かどうか、真ん中に空きがいくつ連続しているか)としたときのゲームの重ね合わせになっている。.xxかxx.かx.xしかつくれない状況が負けである。後はよくある分裂するgrundy数を求めてやれば良い。