点が移動していく問題
区間を整理する考え方が楽しかった。 問題へのリンク 問題概要 下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。 この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、 番目の赤い区間…
set をちゃんと使えるかを試す問題！ 問題へのリンク 問題概要 高橋くんは最初、体力は であり、二次元平面上の座標 にいる。 高橋くんは今から 回の移動を行う。高橋くんの移動方法は長さ の文字列 で表される。1 回の移動は、上下左右のいずれかであり、そ…
読解がちょっと大変......今の時代の問題文の方がわかりやすいね。 問題へのリンク 問題概要 高橋君は最高速度 で移動することができる。 高橋君は時刻 に地点 を出発し、時刻 に地点 に到達しました。 その過程で 個の地点 , , のいずれかに寄り道した可能…
結構アドホックで難しいと思った！ 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…
最初与えられる文字列が高橋くんの手だと勘違いして、サンプル 2 が無限にわからないとなっていました。 clar でお騒がせいたしました...ありがとうございます。 問題へのリンク editorial 問題概要 高橋くんと青木くんがジャンケンを 回行う。青木くんの出…
累積和の累積 max 問題へのリンク 問題概要 数列 が与えられます。 この数列は負の要素を含むかもしれません。 数直線上の座標 0 に置かれているロボットが、以下の動作を順に行います。 正の向きに 進む。 正の向きに 進み、正の向きに 進む。 正の向きに …
手を動かしてみると、どうなってるかが見えてくる！ 問題へのリンク 問題概要 人がそれぞれ座標 に並んでいる (単調増加、負もありうる、各 は偶数)。そして時刻 0 において、 人はそれぞれ正の方向 ( で与えられる) または負の方向 ( で与えられる) に 1 秒…
11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…
kirika さんの「整数論テクニック集」より。 問題へのリンク 問題概要 二次元平面平面上において から の合計 8 方向に移動できる。今、 個のクエリが与えられる。各クエリは座標 が与えられる。原点から出発して、上述の移動を好きな順序で好きな回数だけ繰…
すごいよくある感じ 問題へのリンク 問題概要 二次元平面上に 個の点 () と、 個の点光源 () がある。今、 個の点に対して以下の操作を行う 個の点を一律に右に動かす 個の点を一律に上に動かす この操作によって、すべての点について「どの点光源の右下側に…
確かに、えでゅふぉのラス問にありそう！ 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …
時刻 に対する面積関数 の最小化問題。 全体で三分探索をするのは嘘。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点は初期位置から出発して秒速 1 の速度で上下左右のいずれかに動いている。 このとき、 点の の値の最小値を求めよ。 制約 考…
すごく典型的な問題。 現代なら企業コンの 800 点問題とかに出そうな雰囲気だね。このころはまだあまり典型じゃなかったのかな。 問題へのリンク 問題概要 一直線上に 個の点 があってこの順に並んでいる。さらに左側に 、右側に がある。 からスタートする …
ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。 それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…
えーーーこれが平方分割的解法って天才すぎでは 問題へのリンク 問題概要 人が一直線上を、初期位置 、速度 で等速直線運動を行う。以下の 個のクエリに答えよ: 秒後に座標 から座標 までの間にいる人数を数えよ 制約 考えたこと が 以下と小さいことが大き…
ひたすらバグってつらかった。。。DP 高速化系。セグ木を使ってもいいが、累積和だけで解ける。 問題へのリンク 問題概要 座標 地点から座標 地点へと移動する。 移動途中に 個のガソリンスタンドがあって、それらの座標は で与えられる。 燃料 の状態でスタ…
問題概要 N 本のろうそくが一直線上に並んでいる。最初は原点にいて、N 本のうち K 本のろうそくに火をつけたい。ろうそくと同じ座標に到達すると火をつけることができる。火をつけるのに要する時間は 0 秒である。移動距離を最小化せよ。 解法 K 個の連続す…
蟻さんぐるぐるなのん 問題へのリンク 問題概要 (AGC 013 C) 長さ の円周上を 匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。 匹の蟻は最初 の地点にいた。どの蟻が最初に…
コンテスト本番における 僕のコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210 tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185 解けたとはいえ、反省点も多い感じですね。。。 問題へのリンク 問題概…
平衡三進法！！！ 問題へのリンク 問題概要 二次元座標平面上で、(0, 0) から出発して へと移動したい。何ステップかの移動を行うことができる。 ステップ目の移動では、上下左右のいずれかの方向を一つ選んで、 だけ移動することができる (いずれかの方向に…
