結果。 せっかくunratedなので後ろから解くことにした。Eは脊髄反射で書いたらソート間違ってWA。Dも比較的やるだけなのに大分詰まった。最近書き換えたBITのライブラリにバグが埋まってるのに気づけたのは良かったこととしておこう。

問題概要 ノード数V( 解法 クエリを受ける前に全ての答えを計算しておく。まず、前処理として始点から各頂点への距離と終点から各頂点への距離をdijkstraで求めておく。 また、ついでに始点からのshortest path treeとshortest pathを計算しておく。このとき…

問題概要 ノード数N( 解法 適当な頂点を選んで根付き木にして、LCAを計算しておく。Sの元(v,u)は、lca(u,v)!=u or vのとき(v,lca(v,u)), (u,lca(v,u))と変換してもよいことが分かる。この様な変換を加えておくと、再帰的に計算するとき上手く値をキャンセル…

問題概要 長さL( 解法 Z-algorithmの練習。 Z-algorithmを適用して、Z[i]=L-iならばsuffixにもなっていることがわかる。後はそれより以前に長さL-i以上の値があったかどうかで判定できる。

ここを読んで勉強した。 コメント読むとKMPと等価とか書かれているけどよく分からない。とりあえずパターンマッチングのO(M+N)が使えるのは良い。 原理の解説も元記事にあるけど、とりあえず入力とパターンマッチングへの応用法だけ書いておく。 長さLの文字…

日本だとSpaghetti Sourceが超有名。もちろん他にも探せばいくつかある。 TopCoderのAlgorithm Tutorialsも基本的なのは大体網羅されている。いくつかは和訳されている。 CodeForcesの各参加者が書いているブログも結構面白い。最近読んだのはparadin8さんの…

問題概要 1.オイラーツアーで、根からの距離の増減の列が与えられるのでグラフを復元する。 2.二つの根付き木が同型であるか判定する。 解法 前者はスタックを用いてO(N)で、後者はハッシュを用いてできる(参考)。

問題概要 ノード数V( 解法 まず根付き木の場合を考える。 頂点vを根とした部分木にハッシュ値f(v)を割り振る。f(v)は子の部分木のハッシュ値の集合から生成するようにする。この際ローリングハッシュ的な生成方法だと何故か頻繁に衝突してしまうことに注意。…

問題概要 dat[x][y][z]は0or1の値を持つ。以下のクエリを処理する。0:x1 解法 各座標独立に考える。和のクエリ(x1,y1,z1,x2,y2,z2)が来たときに、([x1,x2]での0の個数)*([y1,y2]での0の個数)*([z1,z2]での0の個数) + ([x1,x2]での0の個数)*([y1,y2]での1の個…

問題概要 f(N) = Σ di μ(di) に対して、|f(N)|>Xとなる最小のNを求める問題。X 解法 この式はn=Π p_i^e_iに対してf(n) = Π (1-p_i)を計算する式である。基本的には元の数より大分小さくなって損してしまい、結局素数が有利になる。X+2以上の最小の素数が答え…

問題概要 ノード数V( σ(0)=0 (v,u) in E ⇒ (σ(v), σ(u)) in E 解法 まず、0を根とした有向木にする。各部分木に対して同型判定が簡単にできれば再帰的に掛け合わせて答えを求めることができる。問題は各部分木に対して同型判定を以下に効率よくやるかだが、…

結果(teamname: hogehoge)。 自分(komiya)と@hasi_t(hasi)と@fura_2(fura2)で24時間マッチ。途中でSRMとか2時間程度の睡眠を挟んで取り組んだ。分担や解法の話し合いについてはskypeのチャットを使った。結構好みの問題が多くて面白かった。あとやっぱりチー…

問題概要 T字型のペントミノをH*W(H,W 解法 2行覚えておくビットDPでもいけるけど復元がとても面倒。普通に探索する。分枝限定法で枝刈りできる。 また、この問題は最大独立集合だとみなすこともできる(ノード数9*9*4)。いつか最大独立集合ソルバができたら…

問題概要 H*W(H,W 解法 同時に置くことができないふたつのマスの間に辺をはると二部グラフになっている。もとめたいものは最大独立集合なので、|V|-|最小点被覆|=|V|-|最大マッチング|で求められる。ただしグラフがそれなりに大きいので最大マッチングはhopc…

問題概要 ある正整数A,B,Cがあり、(A-1)*(B-2)*(C-2)の値が与えられる。A*B*Cの値として考えられる最小値と最大値を求める問題。 解法 全探索する。

結果。 順位としては悪くなくて、レートも上がったんだけどCは解けなきゃいけない気がする。 Aは割とやるだけ、Bは二部マッチングにはすぐ気づけたけどhopcroft書いたことなかったのでちょっと手間取った。Cは2行持ったビットDPか探索だと思ったけど、復元が…

問題概要 N( 解法 一度レストランとつながった家はレストランになると考えれば分かりやすい。コストを昇順に持つプライオリティーキューを用意して、片方がレストランになってるような辺を随時加えていく。この際家がレストランになったならその家を端点に持…

問題概要 グラフの交わらない辺被覆(小さいほど良い)が最大いくつ作れるか求める問題。 解法 グラフだと気づかずに適当にgreedyしたけど割と良いスコアが出た。

問題概要 f(A,B)=max(Aの桁,Bの桁)桁の数で、各位の数はmax(A[i],B[i])(足りないときは0詰めで考える)、f(A,B,C,...)=f(f(A,B),C,..)で定義される関数fがある。N( 解法 fを施した結果が何になるか全通り試す。L=9(=log10(MAX_W))とすると2^(L+1)個程度しかな…

問題概要 +を十にしたようなライツアウトで、解の存在するH*W(H,W 解法 小さいところで実験したら法則性がわかる。後はフェルマーの小定理などを使って計算すればよい。

問題概要 長さnの文字列で、偶数番目+奇数番目と連結した文字列ともとの文字列が一致するのは何通りあるかの和を区間[L,R]について求めよ。L-R 解法 小さいケースについてはunion-findでつなげて親の個数を数えてやればよい。これで試すと偶数項と奇数項の間…

問題概要 N( 解法 区間で扱う。もちろん区間はどんどん細分化されていくので、適当な回数毎に置換を行い区間をまっさらに整備する。整備のタイミングはsqrt(N)くらいにしておけばよさげ。かなり好きな問題。

結果。 よくわからないまま数列辞典と実験で通したのが2問あったけど、通れば正義。タイブレークのは最終日だけ真面目に取り組んだけど満点は難しかった。色々試したいのはあったけど気力が足りなかった。

問題概要 0,1からなる長さN(区間[a,b]に対して、1.全て1にする。2.全て0にする。3.すべて反転させる。4.1の数を答える。というクエリが来るので処理する。 解法 どう見ても適切なデータ構造いじる問題だけど、思いつかなかったのでビット演算で高速化して通…

問題概要 謎のデータ構造Xがある。Xにこの値を突っ込んだ、この値が出てきた、という情報がQ( 解法 シミュレーションして一致するか確かめる。

問題概要 N( 解法 数字5個の集合はソートしてから500進数だと思えば64ビットに収まる。なのでmapで数を簡単に管理できる。

問題概要 素な行列の転置行列を指定されたフォーマットで出力する問題。 解法 行列が素なので全部もたないように気をつければ後はやるだけ。

問題概要 長さN( 解法 ググるとErdős-Gallai の定理というのが出てくる。これを実装した。愚直な実装だと計算量O(N^2)で厳しいけど、累積和とか二分探索を使うとO(N*logN)で判定できる。でもテストケースが弱いのかO(N^2)でも通るらしい。謎。

問題概要 ノード数N( 解法 シミュレーションするだけ。updateを検出するもよし。26ターン回すもよし。プレゼンテーションエラーに注意。

問題概要 解くのにA[i]分必要な問題がN( 解法 簡単な順に解けば良い。証明というほどではないが、小さい方からとれるだけとった方がよいのは相当に自明。順番については、確かに易->難の順序を入れ替えても得することはないように思える(適当)。