問題概要 W*H(W,H 解法 幅優先探索をN回やるので十分。もう少し賢いやり方があるかもしれない。

問題概要 頂点数N( 解法 クエリiの後にクエリjを処理できるかどうかで辺を張ってDAGを構成し最小パス被覆を求めればよい。

問題概要 [0,H)*[0,W)の中に軸に平行な長方形をN( 解法 座標圧縮してflood fillすればよい。長方形を配置するのはいもす法を使う。

問題概要 今1を持っている。今持っているものから重複ありで二つ選んで(a,bとする)、新たにa+bまたはa-bを得る(ただしa-b>0に限る)。X( 解法 基本アイデアは反復深化。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int X; int ANSWER; bool exists[1</algorithm></cstring></cstdio>…

問題概要 t = a^(1/m) + b^(1/n) (a,bは異なる素数,n*m多項式で、次数最小で最高次の係数が1になるようなものを求める問題。そのような解が存在することが知られている。 解法 問題文にヒントが書いてあって答はn*m次の多項式になると決め打ちして良さげ。最…

問題概要 H*W(H,W 解法 ゴールが一つ+遷移が双方向なので両側探索でも解けそうだったけどA*でやった。推定値はそれぞれのゴールへの距離の最大値とする。このときそれぞれが最も対応するゴールに近かったらそのまま終了判定してよい。

問題概要 (1,1)から(N,M)(N,M 解法 全てのワープホールをトポロジカルソートしておく。ways(k,t)を「[0,k)までのワープホールが機能しているときの(1,1)からt番目のワープホールの入り口までの経路の個数」とする。ways(k,t)は除原理を用いることによりO(1)…

問題概要 0,1がかかれたH*W(H 解法 各行についてどこを反転するか全探索する。各列に対しては反転するか反転しないかは大きくなるようなのを選べば良い。愚直にやるとO(2^H*H*W)だけど、前処理かけてxorで求められるようにしておくとO(2^H*W)に落ちる。

問題概要 10*10マスの中にカエルがいる。カエルは周囲のある12箇所に移動できる。訪ねるべき3*3の範囲がいくつか与えられるので、それをすべて順番に訪ねることができるか判定する問題。 解法 簡単なDP。

問題概要 4近傍に関する連結成分の個数を求める問題。 解法 flood fill。union-findでもいいけど普通は流す。

問題概要 10個のボールがあり、番号がついている。順序を保ったままボールをふたつの集合に分けるとき、どちらも番号が昇順になるようにできるか判定する問題。 解法 10個しかないので全探索。ボールの数が増えてもDPで解ける。

問題概要 10*10の盤面があり、各マスは黒か白である。任意の大きさの正方形で全ての黒いマスを被覆する。このとき、はみ出したり白のマスに重なってはいけない。最小枚数を求める問題。 解法 基本方針はBBだけど、下界は相当緩くてよい。正方形を考えるとき…

問題概要 ノード数N( 解法とか コンテスト直後に解説放送を見ていたので打ち切り+FFTで解くことは知っていた。とはいえDPの式立てるのにも大分苦労したけど(高さh以下、というのを状態にするのに中々気づけなかった)。 D言語の標準ライブラリにFFTが入ってい…

問題概要 ノード数N( 頂点vにマークする。 頂点vから順に親をたどって最初にマークされている頂点を答える(頂点vがマークされてるときはvを答える)。 解法 クエリをまず全て読み込む。各ノードに対して最初にマークされた時刻と質問を受けた時刻を記録してお…

問題概要 ノード数V( 解法 Dijkstraした後距離の近い順にソートして確定させていく。

問題概要 ノード数N( 解法 (直前に居た頂点、今いる頂点)を組にしたグラフを考える。後は行列累乗で計算するだけ。最初見たときはM

問題概要 ノード数V( 解法 Introduction to Algorithmsとかにも載っている問題。増加のクエリに答えるのは簡単。減少のクエリに対しては、該当する辺を含む閉路があればそれを除去して、閉路が無ければそれを通るようにsinkからsourceへ流量1を押し戻す。そ…

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

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

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

問題概要 H*W(H*W 答え 二次元RMQのライブラリ確認用にちょろっと投げるつもりだったけど、メモリ制約が非常に厳しく(普通にsegment treeでRMQを実装したら微妙に足りない)想定解法以外を許さない強い意志が感じられた。でも自分がやりたいのはライブラリの…

問題概要 N(有理数で、分母がN以下であるようなものが何通りあるか求める問題。テストケース10^6くらい。 考えたこと 即数列検索。 ヒット。何かΦ関数が見える。 言われてみればそれは自明。漸化式a[1]=2, a[i] = a[i-1] + card({x in [1..i] | xとiは互いに…

問題概要 A[i] = (e[i], s[i]), B[i] = (ee[i], ss[i])が与えられる(N 考えたこと DP臭がする。あとこれ入力で名前読み取る意味ないよね…。 シークレットとスタンダード(概要中のA, B)を別個に考えてよい気がする。 それぞれ、費用いくらのときの最大の満足…

問題概要 二次元ボード(W,H 考えたこと また随分と入力が読み取り辛いですなあ。 こんなん毎回幅優先すればいいでしょう。基本的には数字の大きいところからDP。 TLE。 幅優先するまでもなくマンハッタン距離でいいのか。修正。無事AC。 今考えると別に後ろ…

問題概要 頂点数N(B->Cという経路の最短路を求める問題。 考えたこと どう見てもただの最短路。途中によるとかはdist(A,B) + dist(B,C)を答えるだけでよい。 入力がやたら面倒くさい。頂点は文字列で与えられるしコストはx/40+yという辺な形になってるし…。 …

問題概要 [0,M]内におけるA[i](i 考えたこと 問題文が長くてうげー。 最初入力勘違いしていて一人が受け持つ問題が複数あると思ってた。 それでも整数の分割でサイズが小さければ解けそう。 ひとり一問なら単なるシミュレーションでよい。 最後の一人を特別…

問題概要 長さL( 暗号化の手順 a, b(0 b-aだけスワップさせた文字を逆方向にrotする。 考えたこと 後ろからシミュレーションするだけ。 何かサンプルの最後が合わない…。 アスキー記号だと後ろに大文字があるからオーバーフローは起きないはずなんだけどなあ…

問題概要 1000桁以下の数が与えられる。数が2桁以上の時、連続する2つの数字をその和で置き換える。数が1桁の時自分の番だと負け。先手が勝つか後手が勝つか判定する問題。 解法 実は戦略関係ない。なので適当に戦略を決め打ちしてシミュレーションしてやれ…

問題概要 3次方程式が与えられるので、正の根と負の根の個数を求める問題。 解法 変曲点はすぐに求まるので3分探索して極大値や極小値を求める、とかだと誤差が怖い。なので判別式使って全部整数で処理する。場合分けゲーになって甚だ不本意だけど数学系の問…

問題概要 演算子の間に優先順位がないとき、計算結果は何通りに解釈できるか求める問題。演算子の個数は10以下。 解法 基本的にはただの構文解析だけど、返り値をsetにしておいて区間DPで求める。