keyword Dijkstra C++ 問題概要 ノード数V( 解法 DijkstraするだけなんだけどTLEが異常に厳しいので細々とした高速化をして通った。Forum見てるとSPFAという方法があるらしく、ちょっと調べてみたけどBellman-Fordとの違いがよく分からなかった。priority_qu…

keyword 有向グラフ トポロジカルソート 辞書順最小 C++ 問題概要 ノード数N( 解法 辞書順最小はGreedy。まず前処理として、DAGの判定も込めてWarshall-Floydしておく。ノード数の小さい順に次の処理をしていく。 下流にある未処理のノードの数だけ小さい番…

問題概要=解法 全てのマスについて、ある特定のマスについて距離が等しくなるような部分は任意に置換できる。全ての場合の数を求める問題。 感想 自分が参加していたSRMのMediumの中では1番か2番目に簡単だった問題(もう一つは高校数学の確率の問題)。実際に…

問題概要 ある数列が^-^な形をしているか確かめる問題。 解法 実装するだけとしか言いようがない。階差数列作ってからやると楽になるけど本質的にはやってることに変わり無し。 感想 ある問題が解けなかったとき、悔しいと感じるならまだ良い方で、落ちたと…

参加していました。 自分が解いた問題の中には、前回の店長の様なトラップは無かったように思う。 AとFは蟻本で勉強したのがほぼそのまま出ていたっぽい。蟻本さまさまである。 GとFはデバッグに大分時間をとられてしまった。しかし多次元のBITを書いたのは…

keyword 幅優先探索 C++ 問題概要 3次元の迷路の最短距離を求める問題。ただし下方向への移動はできず、上方向には特定のマスからしかいけない。また、上に登る前に上の層を任意に回転させることができる。 解法 定石通り幅優先するだけ。サンプルが珍しく親…

keyword BIT C++ 問題概要 3次元のBIT。 解法 やるだけ。蟻本に載ってるし。

keyword 動的計画法 BruteForce C++ 問題概要 M(過半数以上の議員を買収しなければならない。各議員には時間の上限( 解法 M人全ての議員について買収するのに必要な最小コストを前処理で計算しておけば後はBruteForceで解ける。各議員について買収する最小コ…

keyword 平面幾何 C++ 問題概要 2次元平面上に、M( 解法 M=1, M=2の場合はコーナーケースなので分けて解く(簡単なので略)。M>=3のときは、3点あれば円が決定できる(or円が無いことがわかる)ので後はやるだけ。もしかしたら入力には同じ点が与えられているの…

keyword 尺取り法 C++ 問題概要 長さM(区間の最小幅を求める問題。 解法 蟻本に載ってる尺取り法の例題とほとんど同じ。なので詳細は蟻本参照のこと。

大抵のプログラミングコンテストやオンラインジャッジではC/C++が選択できる。しかも大体gccである(もしくは、選べる)ことが多い。なので、gccで書くときに覚えておくと便利、かもしれないことを書いておく。そもそもgccのバージョンやコンパイルオプション…

解法 二分探索するだけ。 感想 int ans=Lとしていたせいでかなりはまった。ソースはいろいろ手抜きをしていてかなり汚い。

解法 やるだけ。指は交互に絡めなくてもよいことに注意。 感想 問題自体はA問題としては良問だと思うけど、余計なストーリーが多かったり問題文に不備があったりしたのが残念(前者は単に自分の好み)。

keyword 動的計画法 C 問題概要 長さN( 解法 範囲が狭いのがとても怪しい。もしGreedyで上手くいくならRはもっと大きく設定するだろう。 というわけでDPで考える。別にそういう本筋でない考え方を抜きにしても、情報をたくさん捨てても困らないときにはDPが…

keyword 動的計画法 C 問題概要 長さN,M( マッチングに使われた数字が同じである様な辺は交わってはならない(1-1と3-3などは交わっても良いということ)。 全ての辺は丁度1本の辺と交わる。 解法 図がないと相当説明しづらい。多分ソースコード読めばやってる…

こんなに面倒なはずがない、という問題だったのでいつもより丁寧に書く keyword 反転数 Greedy BIT 二分探索 C++ 問題概要 [1..N](N 素朴な解法 辞書順最小という問題が出たら解法は大体2つ。 条件を満たすものは全部作り出すことができる。つまり辞書順最小…

keyword BIT C++ 問題概要 (x,v) in [1..X]*[1..V] (X,V 解法 maxとか処理が面倒なのでvをキーにして昇順にソートする。求めるのはΣ_{∀i with v[i] 感想 最近構造体を使いたい病にかかっているので何故かpairを使うという発想が出なかった。

keyword ライツアウト BruteForce C++ 問題概要 ルールの少し変わったサイズ4*4のボードでのライツアウト。最小手数を出力する問題。 解法 16マスしかないのでBruteForceでもギリギリ間に合いそう。このルールだと計算量はO(2^22)で間に合いそうだと思ったら…

keyword 素因数分解 問題概要 N(素数ならその旨判定し、そうでないなら最小の素因数を求める問題。 解法 まずは2^19(この数字は適当)以下の素数を列挙してNの因数であるかどうか試す。続いてMiller-Rabinで素数判定する。合成数だと判定されたらPollard's rh…

keyword 二分探索 C++ 問題概要 区間[-10^9, 10^9]上にN( 解法 答えについて二分探索する。ただし、二分探索の繰り返し回数とかが結構多いので、時刻を決め打ちしたとき衝突するかどうかの判定はO(N)でやらないと落ちる(O(N * logN)も駄目だった)。 感想 入…

keyword 整数 素数 Java 問題概要 長さN(素数Q( 解法 文字列をa[0]a[1]..a[N-1]とする。b[i] = a[i]a[i+1]..a[N-1] (10進の数値として解釈)とすると、b[i]=b[j] (mod Q)ならb[i]-b[j]=a[i]a[i+1]..a[j-2]a[j-1]0..0 (10進の数値として解釈)はQの倍数。ここで…

keyword ライツアウト 掃き出し法 Java 問題概要 W*H(W,H 解法 マンハッタン距離云々は本質に全く関係ない。連立一次方程式をmod 2の世界で解くだけ。計算量はO( (W*H)^3 )。計算量は係数に1/6だか1/3だかがつくけど割と厳しい。でも問題なく通った。 感想 …

解法 各操作に対して逆の処理はすぐ分かるので、やるだけとしか言いようがない。

解法 ただの最小全域木。誤差死することすらまずない親切設計な問題。

keyword 反復深化 シミュレーション Java 問題概要 5*5の盤面でライフゲームの初期値が与えられる。ただし、ある一つのマスには謎の物体Xがいて、Xは周囲のマスに対しては生きている様に振る舞い、しかし自分の存在するマスは回りの状態によらず死んだままと…

keyword Greedy Java 問題概要 W*H(W,H 解法 各数列はソートしても大丈夫だと分かる。 あとは、図の様に右上から左下に向かってGreedyに置いていく。計算量O(W*H)。

keyword 反転数 BIT C++ 問題概要 長さN(a[j]>a[k]を満たす組がいくつあるか求める問題。 解法 反転数に似た概念の問題。解き方も普通の反転数を求めるときとかなり似通っている。まず前処理として座標圧縮っぽい方法で数列aを[1..N]のpermutationにする。数…

keyword 木 C++ 問題概要 ノード数V( 解法 基本的にどの辺も2度通る。例外的に始点から終点までの辺は1回だけで良い。なので終点までの辺の長さが最も長くなるように終点を選べば良い。

解法 基数変換するだけ。ローマ数字じゃないときは入力に0があることに注意。

解法 3!通り全部試すだけ。泥臭く書いた。