自分がこれまでに解いたICPC国内予選の過去問をまとめてみた。古いのもあって今見返すと妙に気恥ずかしい。問題全体を眺めてみると他のコンテストに比べて実装重めな気がする。記事書いてない問題や解いてない問題もあるので解決し次第追加していく方向で。 …

keyword 平面幾何 C++ 問題概要 レーザー光を上手く反射させて最短距離で目標物に当てる問題。 解法 鏡の枚数が少なく、反射の回数に制限があるので全ての反射の場合を総当たりする。反射をまともにシミュレーションするのは大変なので、鏡にぶつかる度に鏡…

解法 x座標、y座標それぞれについて最大値と最小値を覚えておくだけ。

keyword 動的計画法 Java 問題概要 整数N( 解法 前からDPで計算量O(N^(4/3))程度。メモ化再帰だと書き方によってはスタックオーバーフローするかもしれない。 感想 ソースコード失くしたので書き直した。

keyword Dijkstra 文字列 C++ 問題概要 ノード数N( 解法 後ろからベルマンフォードとか1文字ずつ分解とかいろいろ頭の良い解法があるのは知っているけど適当に前処理をかけた後普通にDijkstraっぽく解いてみた。ただしDijkstraをそのまま適用するのはダメだ…