けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

所要時間を求める問題

AtCoder ABC 052 D - Walk and Teleport (2Q, 緑色, 500 点)

この時代は Greedy が多かった。そして、実はすごく単純なことに気がつくかどうかが問われる問題! 問題へのリンク 問題概要 数直線上 (東西方向) に 個の町があり、それぞれの町の座標は である。町 1 から出発して、すべての町を訪れたい。次の 2 つの手が…

AtCoder ABC 129 A - Airplane (7Q, 灰色, 100 点)

この頃によくあった 3 個の入力をどうのこうのする系! 問題へのリンク 問題概要 3 つの空港 A, B, C がある。 A-B 間の移動の所要時間は B-C 間の移動の所要時間は A-C 間の移動の所要時間は 今、これらの空港を順に訪れる (たとえば、B → A → C)。最短の所…

AtCoder ABC 325 E - Our clients, please wait a moment (緑色, 450 点)

少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…

JOI 二次予選 2021 A - 往復すごろく (AOJ 0691, 難易度 5)

結構アドホックで難しいと思った! 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…

JOI 本選 2010 C - つらら (AOJ 0551, 難易度 6)

実装をどうしようかを色々悩んでしまう系 ジャッジページ AOJ の問題文 問題概要 本のつららが一列に並んでいる。それぞれ長さは となっている。各つららは以下のルールに従って長さが変わる。 一度でも長さが 0 になったならば、伸びることはない 左右のつ…

AtCoder ABC 157 F - Yakiniku Optimization Problem (橙色, 600 点)

ABC 151 F 以来の幾何ですね。ABC 151 F の解法のうち「探索候補として交点を考える」というのが今回もいい感じに使える! drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 個の点 が与えられる。それぞれの点に肉が置いてある。このうち…

AtCoder AGC 014 A - Cookie Exchanges (灰色, 300 点)

何回も何回も操作すると同じことになる系 問題へのリンク 問題概要 3 つの整数 があたえられる。以下の操作を行えなくなるまで繰り返す: 3 つの整数の中に奇数が 1 個でもあったら終了 すべて偶数だったら を に置き換える 操作を何回行うか?無限に行う可能…

AtCoder ABC 123 C - Five Transportations (茶色, 300 点)

結構難しい... 問題へのリンク 問題概要 人全員が最初都市 1 にいて、全員を都市 1 -> 2 -> 3 -> 4 -> 5 -> 6 へと順番に進んで、全員が都市 6 にいる状態にしたい。 都市 1 から都市 2 への移動手段は毎秒ごとに提供されているが、同時に 人しか行けない。…