ICPC
問題概要 今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*でやった。推定値はそれぞれのゴールへの距離の最大値とする。このときそれぞれが最も対応するゴールに近かったらそのまま終了判定してよい。
問題概要 10*10の盤面があり、各マスは黒か白である。任意の大きさの正方形で全ての黒いマスを被覆する。このとき、はみ出したり白のマスに重なってはいけない。最小枚数を求める問題。 解法 基本方針はBBだけど、下界は相当緩くてよい。正方形を考えるとき…
問題概要 ノード数V( 解法 Dijkstraした後距離の近い順にソートして確定させていく。
問題概要(適当) 少しルールが複雑なNimで先手勝ちか後手勝ちか判定する。 解法 典型的なゲーム木探索。特に計算量を落とす必要もない。オンラインRMQとか使えば計算量落とせる。
問題概要 演算子の間に優先順位がないとき、計算結果は何通りに解釈できるか求める問題。演算子の個数は10以下。 解法 基本的にはただの構文解析だけど、返り値をsetにしておいて区間DPで求める。
解法 ビットDP。この手の、状態遷移でビットが立つだけ、みたいな問題は何も考えずに0から順に回してよい。集合をビットで表現したとき、包含関係が成り立つなら数値としての大小関係も満たされるから。
解法 タイトル通りにBFSする。Javaで配列をHashSetに突っ込もうとして引っかかった。
解法 やるだけ。入れ替わりとかはxorとってやればよい。
解法 間に合うので全探索で。
問題概要 最初に順番に積まれたトランプがある。ある方法でシャッフルを繰り返した時に、一番上にどれがくるかを求める問題。 解法 普通にシミュレーションしても通る。この手のシャッフルする問題を解くテクニックに、逆向きにシミュレーションして、終了時…
問題概要 配置された直方体の箱に触れないようにある線分上で玉を転がしたい。最大半径を求める問題。 解法 一目でわかる二分探索。2線分間の距離を求めるライブラリさえもっておけば楽勝。問題文やサンプルがとにかく親切。
keyword BruteForce C++ 問題概要 覆面算を解く。 解法 特に工夫せず全探索で通った。出現する文字数をMとすると、{0,..,9}のうちサイズMの部分集合を列挙しながらnext_permutationで全ての割り当てを作る。その割り当てが正しいかどうかは先頭の文字になっ…
自分がこれまでに解いたICPC国内予選の過去問をまとめてみた。古いのもあって今見返すと妙に気恥ずかしい。問題全体を眺めてみると他のコンテストに比べて実装重めな気がする。記事書いてない問題や解いてない問題もあるので解決し次第追加していく方向で。 …
keyword 平面幾何 C++ 問題概要 レーザー光を上手く反射させて最短距離で目標物に当てる問題。 解法 鏡の枚数が少なく、反射の回数に制限があるので全ての反射の場合を総当たりする。反射をまともにシミュレーションするのは大変なので、鏡にぶつかる度に鏡…
解法 x座標、y座標それぞれについて最大値と最小値を覚えておくだけ。
keyword 動的計画法 Java 問題概要 整数N( 解法 前からDPで計算量O(N^(4/3))程度。メモ化再帰だと書き方によってはスタックオーバーフローするかもしれない。 感想 ソースコード失くしたので書き直した。
keyword Dijkstra 文字列 C++ 問題概要 ノード数N( 解法 後ろからベルマンフォードとか1文字ずつ分解とかいろいろ頭の良い解法があるのは知っているけど適当に前処理をかけた後普通にDijkstraっぽく解いてみた。ただしDijkstraをそのまま適用するのはダメだ…
keyword 動的計画法 経路復元 C++ 問題概要 よくある携帯電話の入力方式の問題。打ち込んだ数字列と辞書が与えられるのでマッチングする文章を全て出力する問題。 解法 前からDPしていく。経路復元は定石どおりDPテーブルにどこから来たのか情報を付記してお…
解法 さすがにこれはやるだけ。計算時間に余裕がある時は一番分かりやすく書くのがポリシー。累積和とか尺取り法で計算量落とせるけど無理しない。
keyword シミュレーション Java 問題概要(適当) レーンが2本あって泳ぐときは前の人を追い越せない。全ての人が満足行くまで泳ぎきるのにかかる時間を求める問題。 解法 配列を2本使ってシミュレーションするだけ。とはいえ、時間を1秒ずつ進めたりすると誤…
keyword 動的計画法 C++ 問題概要 日程[i,j]( ⊆[1,365]), 金額wという予約がN( 解法 D=365とする。素朴に、dp[i日目][1つ目のホールが使い終わる日][2つ目のホールが使い終わる日]とすれば計算量O(D^3)位(本当はもう少し多いか?)で解ける。でも、2つのホール…
keyword 反復深化 Java 問題概要 あるルールα→βというルールがN(JavaでいうところのreplaceAll(α、β)という作用である。文字γをδにするのに必要な最小回数を求める問題。できなければ-1を出力する。1 解法 何か数字がやたら小さいし探索臭がするので反復深化…
問題概要 原子量と分子式が与えられるので分子量を求める問題。 解法 構文解析するだけ。BNFは := | ε := | | '(' ')' 厳密にはこれだと元のBNFと異なる( ()2などが有効と判断される )けど、入力が正しいと保証されてるので問題はない。実装時間約20分。
keyword 幾何 平面走査法 誤差 数値計算 Java 問題概要 中心が整数座標 in [1,30]*[1,30]、半径1の円柱がある。影の幅が最も大きくなるときの値と最も小さくなるときの角度を誤差EPS=1e-10以下で求める問題。 解法 まず、角度を決めたときの影の幅は比較的簡…
keyword 動的計画法 Java 問題概要 風船がN( 解法 見た瞬間にDP。多分一番楽なのは状態をdp[i番目の風船][搭載している風船の個数]とする。計算量O(N)。dp[座標][時間][風船の個数]とやっても解けるかもしれない。意味ないけど。実装時間17分。
keyword 探索 Java 問題概要 ノード数V( 解法 探索するだけ。グラフを構成する部分が面倒くさい。実装時間13分。
keyword ハッシュ 定数倍最適化 C++ 問題概要 長さM( 解法 ICPC的には、編集距離2以下の文字列を全部作って、カバーされるかどうか確かめればよい。カバーされるかどうか確かめる部分は、Lが一定なことを利用してRabin-Karpっぽくローリングハッシュでハッシ…
keyword Rabin-Karp ハッシュ Java 問題概要 W*H(W,H 解法 気分的にはRabin-Karpに近いことをする。ただし、Rabin-Karpを真面目に実装すると、全て一致するときに計算量がO(W*H*p^2)となってさすがにこれは間に合わない。なので手抜きでハッシュ値の一致だけ…
