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

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

AtCoder ABC 112 B - Time Limit Exceeded (7Q, 灰色, 100 点)

「線形探索」と「最小値を求める」の組み合わせ技! 問題へのリンク 問題概要 個のペア値 が与えられる。 を満たすような についての、 の最小値を求めよ。そのような が存在しない場合は "TLE" と出力せよ。 解法 for 文を用いて、各 i について t[i] <= T …

AtCoder ABC 265 A - Apple (7Q, 灰色, 100 点)

ちょっと頭を使う系の問題。この時期の ABC-A にはこういうものが多かったね。 問題へのリンク 問題概要 りんごをちょうど 個買いたい 円払って 個買う 円払って 個買う のいずれかによって、ちょうど 個買うための最小コストを求めよ。 解法 以下のいずれか…

AtCoder ABC 265 C - Belt Conveyor (4Q, 灰色, 300 点)

二次元グリッド上を上下左右に動いていくシミュレーション問題。無限ループの判定が少しややこしい。 問題へのリンク 問題概要 のグリッドがあり、各マスには U, D, L, R のいずれかが書かれている。それぞれ、上、下、左、右へと進む指示を表している。 た…

AtCoder ABC 351 B - Spot the Difference (7Q, 灰色, 200 点)

二次元配列を二重 for 文で調べる最低ライン! 問題へのリンク 問題概要 のグリッドにアルファベット文字が書かれたものが 2 つ () 与えられます。 これらは 1 箇所のみ異なっていることが保証されます。 であるような を答えてください。 制約 解法 (C++) …

AtCoder ABC 351 A - The bottom of the ninth (7Q, 灰色, 100 点)

現実世界っぽい題材を扱ったちょっと楽しい問題。 問題へのリンク 問題概要 チーム A とチーム B が野球対戦をし、9 回表まで終了していて、 (チーム A の得点) ≧ (チーム B の得点) となっている。チーム B が 9 回裏で勝利するのに必要な最小追加点を求め…

AtCoder ABC 231 C - Counting 2 (4Q, 灰色, 300 点)

鉄則本 B11 とほぼ同じ問題! 問題へのリンク 問題概要 身長が であるような 人がいる。以下の 回のクエリに答えよ。 【クエリ】 整数 key が与えられるので、身長が key 以上の人が何人いるかを答えよ。 制約 考えたこと 0-indexed で考えます。 最初に、 …

AtCoder ABC 334 D - Reindeer and Sleigh (3Q, 茶色, 400 点)

この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ! 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…

鉄則本 A12 - Printer (3Q, ★3)

「答えで二分探索」のめちゃくちゃいい練習問題! 問題へのリンク 問題概要 台のプリンターがあり、 番目のプリンターは 秒後にプリントする。 合わせて 番目のプリントが行われるのは何秒後か? 制約 答えが 以下] 解法 鉄則本の問題なので、鉄則本参照。 1…

鉄則本 B11 - Binary Search 2 (4Q, ★3)

lower_bound() の練習!! 問題へのリンク 問題概要 長さ の配列 が与えられる。この配列に対して 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、配列 の中に より小さい要素が何個あるかを求めよ。 制約 解法 github.com コード #include <bits/stdc++.h> using</bits/stdc++.h>…

AtCoder ABC 207 E - Mod i (2D, 青色, 500 点)

この手の累積和高速化が半端じゃなく苦手なことがわかった。 問題へのリンク 問題概要 長さ の数列 が与えられる。 この数列をいくつかの区間に分割する方法のうち、 番目の区間に含まれる数列の要素の総和が で割り切れるようなものの個数を 1000000007 で…

AtCoder ABC 207 C - Many Segments (4Q, 灰色, 300 点)

これはちょっと整理が大変な問題。時々問題文に登場する 0.5 という数値がなんなのかを知れる問題とも言える。 問題へのリンク 問題概要 個の区間がある。各区間は 4 タイプあり、 タイプ 1:区間 タイプ 2:区間 タイプ 3:区間 タイプ 4:区間 となってい…

AtCoder ABC 207 B - Hydrate (5Q, 灰色, 200 点)

これ結構難しい! 数式を丁寧に立てよう。 問題へのリンク 問題概要 箱に水色のボールが 個入っている。 「箱に 個の水色のボールと、 個の赤色のボールを入れる」という操作を繰り返すことで、赤色のボールの個数が水色のボールの個数の 倍以上となるように…

AtCoder ABC 205 F - Grid and Tokens (3D, 黄色, 600 点)

これはもう、editorial にある図がすべてなので備忘録程度に! 問題へのリンク 問題概要 のグリッドがある。 個の石があり、石 は、 かつ を満たすようなマス に置くことができる。 ただし、どの行・どの列についても、2 個以上の石が置かれないようにする。…

AtCoder ABC 205 E - White and Black Balls (2D, 黄色, 500 点)

カタラン数をわかっていればできる! 問題へのリンク 問題概要 正の整数 が与えられる。黒いボール 個と、白いボール 個を一列に並べる方法のうち、次の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 【条件】 どの についても、列の左から …

AtCoder ABC 205 D - Kth Excluded (2Q, 茶色, 400 点)

色んな方法があるが、できるだけ楽にやりたい! 問題へのリンク 問題概要 単調増加な 要素からなる数列 がある。この数列について、次の 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、 のどれとも異なる数値 (よい数と呼ぶこととする) のうち、…

AtCoder ABC 205 C - POW (5Q, 灰色, 300 点)

愚直に や を求めようとすると、色んな理由でおかしくなってしまう。数学的に綺麗に処理しよう! 問題へのリンク 問題概要 整数 が与えられる。 と の大小関係を求めよ (大きい、小さい、等しい)。 制約 考えたこと や はまともに計算するとものすごい桁数に…

AtCoder ABC 205 B - Permutation Check (7Q, 灰色, 200 点)

いろんな方法が考えられる! 問題へのリンク 問題概要 1 以上 以下の整数からなる数列 が与えられます。 この数列が を並び替えられることで得られるかどうかを判定せよ。 制約 考えたこと 問題文は「 を並び替えることで に一致させられるか」を問いかける…

鉄則本 A11 - Binary Search 1 (★2)

ここでは、lower_bound() を使って解いてみることにする。 問題へのリンク 問題概要 小さい順に並べられた配列 が与えられる。 値 が の中で何番目の要素の値であるかを求めよ。ただし、 の中に値 の要素は含まれているとする。 制約 考えたこと 実は単純な …

AtCoder ABC 354 A - Exponential Plant (6Q, 灰色, 100 点)

while 文の練習! 問題へのリンク 問題概要 0 日目には 0 cm の植物がある。 日目の夜に植物は cm 伸びる。 朝に植物を観察するとき、高さが最初に を超えるのは何日目か? 制約 考えたこと 「高さが 以下であるうちは反復し続ける」というような while 文を…

AtCoder ABC 354 B - AtCoder Janken 2 (6Q, 灰色, 200 点)

文字列を辞書順にソートする方法を確認しておこう! 問題へのリンク 問題概要 人のユーザーがいて、 人目の名前は 、レーティングは である。 レーティングの総和を で割った余りを としたとき、各ユーザーの名前のうち、辞書順で小さい順に 番目のものを求…

AtCoder ABC 354 C - AtCoder Magics (2Q, 茶色, 350 点)

いろんな方法がありそう。こういうのを工夫して解き切る腕力はいつだって大事になる。 問題へのリンク 問題概要 個のペア値 が与えられる。 ある について かつ を満たすとき、ペア値 を削除する操作を繰り返す。 最後に残るカードの集合を求めよ。 制約 考…

AtCoder ABC 354 D - AtCoder Wallpaper (1D, 水色, 450 点)

周期性をうまいこと活用してなんとかする問題! 問題へのリンク 問題概要 座標平面上で下の図のような白黒模様が与えられる (問題文より)。 左下の頂点が 、右上の頂点が であるような長方形領域内部の黒色部分の面積 (の 2 倍) を求めよ。 制約 考えたこと …

AtCoder ABC 354 E - Remove Pairs (1D, 水色, 475 点)

ChatGPT が問題文コピペのみで解けたと話題になった! 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。 先手と後手が交互にゲームする。交互にまだ残っているカードのうち、表の値が等しいか、裏の値が等しいような 2 枚のカー…

AtCoder ABC 354 F - Useless for LIS (2D, 青色, 525 点)

LIS の応用問題。LIS を分かっていれば、その DP の過程を保存しておくことで、この問題が解けることがわかる! 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、要素 を含むような数列 の LIS が存在するかどうかを判定せよ。 (マルチテ…

AtCoder ABC 354 G - Select Strings (4D, 橙色, 625 点)

Dilworth の定理から、DAG の最小パス被覆!! かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…

鉄則本 A10 - Resort Hotel (2Q, ★4)

左右からの累積和・累積 max を前処理で求めておくのは、よくある典型!! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。 【クエリ】 区間 が与えられるので、数列からその区間を除外した領域について、整数値の最…

鉄則本 B09 - Papers (2Q, ★4)

二次元いもす法の練習問題 問題へのリンク 問題概要 二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。 紙に覆われている部分の面積を求めよ。 制約 考えたこと 二次元いもす法の練習。 github.com コード #incl…

鉄則本 A09 - Winter in ALGO Kingdom (2Q, ★4)

二次元いもす法! 問題へのリンク 問題概要 のグリッドにおいて、 日間雪が降った。 日目には、マス を左上とし、 を右上とする長方形領域に雪が 1 cm だけ降った (溶けないとする)。 最終的な各マスの積雪量を求めよ。 制約 解法 二次元いもす法をします。…

鉄則本 B08 - Counting Points (2Q, ★4)

二次元累積和の練習問題! 問題へのリンク 問題概要 二次元平面上に 個の点がある。 番目の点の座標は である。 「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか?」 というタイプの 回のクエリに答えよ。 制約 解法 x, y 座標の値が…

鉄則本 A08 - Two Dimensional Sum (2Q, ★4)

二次元累積和! 問題へのリンク 問題概要 のグリッドがあり、マス には値 が書かれている。次の 個のクエリに答えよ。 【クエリ】 左上が 、右上が であるような長方形領域が与えられるので、領域内のマスに書かれた整数の総和を求めよ。 制約 解法 鉄則本に…