旧ABC
文字通り、与えられた数列を座標圧縮する問題ですね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 これらの数列から重複を除外して小さい順に並び直して得られる数列を とします。 各 に対して、 となるような を出力してください。 制約 座標圧…
読解がちょっと大変......今の時代の問題文の方がわかりやすいね。 問題へのリンク 問題概要 高橋君は最高速度 で移動することができる。 高橋君は時刻 に地点 を出発し、時刻 に地点 に到達しました。 その過程で 個の地点 , , のいずれかに寄り道した可能…
最小カットのよい練習問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられます。頂点番号を とします。また、頂点 0 以外の 個の頂点 が与えられます。 今、次の操作を行っていくことで、頂点 0 からは頂点 のいずれにも到達で…
これが ABC の C 問題だったとは...！！！ 典型90問の問 4 が結構近いと思った。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッド (メモリにおさまらない規模) が与えられる。そのうちの 個のマスには飴が置いてある。 次の条件を満たすマスの…
方程式を解くタイプの二分探索の問題ですね。 問題へのリンク 問題概要 正の整数 が与えられます。 秒後のボールの位置 は で表されます。 を満たす実数 の値を十分高い精度で求めてください。 を満たせば正解とみなされます。 制約 解へのアプローチ の解を…
いもす法の典型問題 問題へのリンク 問題概要 サイズ 1000001 の配列 v が与えられる (index は、0, 1, ..., 1000000)。 以下の 回の操作を行う。 回目の操作では、 を満たす について、v[x] に 1 を加算する すべての操作を行ったあとの、配列中の値の最大…
木上のパスに関する問題！！ LCA で解決できる典型問題 問題へのリンク 問題概要 頂点数 の木が与えられる。次の 個のクエリに答えよ。 各クエリでは木上の 2 頂点 が与えられる 木に辺 を仮に追加したとすると、閉路が 1 個形成される その閉路に含まれる辺…
木の直径の求め方を知っていれば解ける！！ 問題へのリンク 問題概要 頂点数 の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。 そのために、以下のクエリを 100 回まで投げることがで…
大昔の ABC の問題ですが、今なお色あせない教育的良問。二分探索の練習問題に。 問題へのリンク 問題概要 個の風船がそれぞれ初期状態では高度 の位置にあり、1 秒ごとに ずつ上昇する。これらすべての風船を射撃によって割りたい。 競技開始時に 1 個風船…
ICPC 系列でよくありそうな雰囲気の問題！ 問題へのリンク 問題概要 二次元平面上で原点から出発し、 回にわたって、以下の動きのいずれかを確率 1/4 で選択して実施する。 回の動き終了後に座標 にいる確率を求めよ (許容誤差は )。 x 座標を する x 座標を…
順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…
