問題概要 長さL( 解法 愚直だとO(N^2 * L)かかるが、DPの状態をあまり時間のみにすることで計算量をひとつ落とせる。

問題概要 N( 解法 全探索。

問題概要 長さL( 解法 rotateさせる系の問題は同じものをつなげるのが定石。このときsuffix arrayを構築してやればよい。複数あるとき最小のものを答えたいので末尾に大きい値を加えておく。

問題概要 N( 解法 真面目にDFSで書く。ビット演算を使って多少高速化してやる。手元だとN=14で1秒以上かかっているのでアウトっぽいけどテストケースが弱いらしく制限時間ギリギリで通った。

問題概要 幅Dの川がある。途中には大きな石と小さな石がある。小さな石は1回乗ると壊れる。意志を中継して川を往復したい。利用する石の間隔の最大値の最小値を求める問題。 解法 二分探索+最大流。小さい石は対応する頂点に容量制限を付け加える。INFをあま…

問題概要 N*N(N 解法 典型的ゲーム木探索。どの行、列を使用済かを組にしてminmaxする。

問題概要 配列Xと配列Y(長さはともにN(

問題概要 8クイーンの正しくないかもしれない配置が与えられる(ただし、各行はちがうことが保証されている)。正しい状態にするには最低幾つ動かす必要があるか求める問題。 解法 n=8だったらnクイーンの全探索は余裕を持って間に合うので解を全て生成して距…

問題概要 ノード数N( 解法 二分探索+二部グラフチェックする。

問題概要 a + b^2 = c^3 (mod K( 解法 bをNから1に減らしながらやる。BITのb^3 (K)のindexに1を加えて、[b^2+1, b^2+b]までのBITの区間和を足し上げる。このとき、K

問題概要 ノード数N( 解法 まず星グラフを考える。その後辺数が余っていたら頂点を一つ選んで既にあるクリークにその頂点を含むクリークになるように辺を追加する。First Acceptだったっぽい。

問題概要 山が3つあって、それぞれの山には石がx, y, z個置いてある。先手と後手の人が交互に以下のいずれかの処理をする。 xの石をひとつyの山に移す。 yの石をひとつzの山に移す。 zの石をひとつ取り除く。 xの石をひとつyの山に移し、zの石をひとつ取り除…

問題概要 ノード数N( 解法 まず、適当な点を根にしてLCAを持ち、オイラーツアーを計算しておく。また、始めて訪ねたタイミングと出て行くときのタイミングを記録しておく。このとき、10種類のBITを用いて入るときに+1、出ていくときに-1を加えるようにすると…

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

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

問題概要 サイズ10*10のライツアウトを解いて最小手順を答える。 解法 このサイズなら全探索。(サイズが大きくなったら連立一次方程式を考える)

問題概要 区間[0,1]で単調減少な関数が与えられるので根を求める問題。 解法 二分探索。浮動小数点数のせいで端点の処理が面倒くさい。

問題概要 長さN( 解法 全探索。タイブレークのルールをよく理解していないけど要素数の多い方を優先するようにしたら通った。

問題概要 長さN( 考えたこと 答えに関して二分探索。判定は貪欲でやる。

問題概要 ノード数V( 解法 頂点、偶奇を組にしてDijkstraするだけ。

問題概要 子供がK( 解法 W個の指定されたものによって円ができてよいのはK個全てが出現したときだけ。それ以外のときは直線が集まったものなら残りを適当につなげて円を作ることができる。連結なグラフが直線である条件は最低次数が1で最高次数が2以下である…

問題概要 x,y,z(いずれも値はsigned intに収まる)が与えられるのでx^y (z)を求める問題。 解法 いわゆるバイナリ法を使って計算する。

問題概要 [0,10^6(=:L))でのスケジュールを考える。[a,b)というスケジュールがN( 解法 長さLの配列を塗りつぶしていく。計算量が危ないように錯覚したけどダブった時点で処理を止めれば計算量はO(L)で抑えられる。

問題概要 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ターン回すもよし。プレゼンテーションエラーに注意。

問題概要 ある2つが繋がったという情報や、ある2つは繋がっているかどうかというクエリが来るので処理する。 解法 入力の制限がかかれてなかったり、入力の終了読み取りが面倒だがunion findするだけ。