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

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

コーナーケース

AtCoder ABC 048 B - Between a and b ... (5Q, 灰色, 200 点)

制約が と大きいので、ちゃんと整数論的処理をしないといけない! 問題へのリンク 問題概要 以上 以下の整数のうち、 の倍数は何個あるか? 制約 考えたこと 制約が と極めて大きいので探索手法で解くことは難しい。数学的に求めることを考える。 まず、「 …

AtCoder ABC 173 E - Multiplication 4 (1D, 青色, 500 点)

個から 個を選ぶ設定の問題! 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…

AtCoder ARC 176 B - Simple Math 4 (1D, 水色, 400 点)

というコーナーケースにやられた! 問題へのリンク 問題概要 整数 が与えられる。 を で割った余りの一の位の値を求めよ。 (マルチテストケース) 制約 考えたこと まず最初に考えたのは「全体を で割った世界」で考えれば良いということ。 このことを正当化…

AtCoder ABC 223 A - Exact Price (8Q, 灰色, 100 点)

えぐいコーナーケースに注意! でもサンプルにあるね。 問題へのリンク 問題概要 財布に 円玉が 1 枚以上入っています。 財布に入っている合計金額がちょうど 円であるようなことが、あり得るかどうかを判定してください。 制約 考えたこと 基本的には「 が …

AtCoder ABC 347 F - Non-overlapping Squares (黄色, 525 点)

面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…

AtCoder ABC 175 A - Rainy Season (灰色, 100 点)

ちょっと難しい問題。 問題へのリンク 問題概要 3 文字の 'R' と 'S' のみからなる文字列 が与えられる。 において、'R' が最大で何個連続しているかを答えよ。 解法 ありうる文字列は 通りあることに注意しよう。よって、すべての文字列を調べることができ…

AtCoder ABC 325 D - Printing Machine (水色, 450 点)

とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

AtCoder ABC 308 C - Standings (茶色, 300 点)

伝説の誤差問題!! 誤差について学べる、とても教育的な問題。 問題へのリンク 問題概要 人がコイントスをしました。各人には と番号がついています。 人目は、 回表が出て、 回裏が出ました。 人目のコイントスの成功率は と定義されます。 人 の番号を、…

AtCoder ABC 323 F - Push and Carry (水色, 525 点)

怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…

AtCoder ABC 321 B - Cutoff (灰色, 200 点)

意外とややこしい問題。 ラウンド目の成績によっては、これまでの暫定の最大スコアと最小スコアが変わるかもしれないという点に注意! 問題へのリンク 問題概要 ラウンドの試験が行われる。各ラウンドの得点は 0 以上 100 以下の整数値である。全ラウンドの…

AtCoder ABC 207 D - Congruence Points (黄色, 400 点)

すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…

AtCoder ABC 009 C - 辞書式順序ふたたび (試験管青色)

旧 ABC の C 問題の中でも、個人的に最難だと思う問題! 現代の ABC で出題されても水色 diff になると思う。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の各文字を並べ替えてできる文字列 のうち、 となる が 個以下であ…

AtCoder ABC 299 C - Dango (灰色, 300 点)

「要するに o の最長連続箇所を求めればいい (ただし例外あり)」って感じに、シンプルに整理する力が問われる問題! 問題へのリンク 問題概要 正の整数 に対して、 レベル のダンゴ文字列とは、以下の条件を満たす文字列である。 o と - からなる長さ の文字…

yukicoder No.2066 Simple Math !

floor sum のいい感じの練習問題! 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…

AtCoder ABC 282 D - Make Bipartite 2 (緑色, 400 点)

一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある! その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる!! 問題へのリンク 問題概要 頂点数 、辺数 の単…

DISCO presents 2016 予選 D - DDPC特別ビュッフェ (赤色)

久しぶりに bit ベクター高速化を使った。デバッグがしんどかった。 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。今、次の操作をちょうど 回実行する と を選ぶ と とを swap する 操作実行後の の値の最大値を求めよ。 制約 考えた…

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった! ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…

AtCoder ABC 246 C - Coupon (灰色, 300 点)

ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…

square869120Contest #5 B - Emblem

競プロ典型90問の問題 001 の類題。「最大値の最小化」をする二分探索の典型問題ですね。 問題へのリンク 問題概要 二次元平面上に 個の円が与えられます。またそれらとは別に 個の点が与えられます。円同士は互いに交わることはなく、点が円に包含されるこ…

AtCoder ABC 193 D - Poker (緑色, 400 点)

発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …

Xmas Contest 2020 B - Beterminant

なぜか埋め込みにこだわってしまい、本番 AC できなかった... 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす最大の正の整数 を求めよ (存在しない場合は -1、無限個存在する場合は -2)。 確率 % で表が出るサイコロを 回振るとする 表が出…

AtCoder ABC 185 D - Stamp (茶色, 400 点)

番兵を入れるとかすれば、怖いケースをあらかじめ除去できそう 問題へのリンク 問題概要 左右方向一列に 個のマスが並んでいます。 この 個のマスのうち、マス の 個のマスは青色で、それ以外のマスは白色です。 あなたは一回だけ、正整数 を一つ選んで幅 の…

AtCoder ABC 184 C - Super Ryuma (茶色, 300 点)

これ難しいと思った! あと、どうやら (1, 1, 1, 6) を 3 回にする嘘解法が AC になったらしい 問題へのリンク 問題概要 以下の動きのできる駒がある。駒をマス からマス へ移動させるのに必要な手数の最小値を求めよ。 制約 考えたこと まず、スタートとゴ…

AtCoder AGC 049 C - Robots (黄色, 800 点)

11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…

AtCoder AGC 048 C - Penguin Skating (黄色, 700 点)

想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは,次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…

AtCoder AGC 041 A - Table Tennis Training (灰色, 300 点)

若干注意力ゲーだった。端で折り返してこれることに注意。 問題へのリンク 問題概要 正の整数 が与えられる。2 つの整数 に対して毎回以下のような操作を行う。2 つの整数が一致させられるまでの最小回数を求めよ。 整数 が でも でもないとき、 と のいずれ…

AtCoder AGC 037 A - Dividing a String (灰色, 300 点)

意外とすぐにわからなかったんやけど... 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。以下の条件をみたす最大の正整数 を求めよ。 を空でない 個の文字列へと分割したとき、連続する文字列は相異なる 制約 Greedy は嘘 パッと思い浮かぶ …

AtCoder AGC 034 A - Kenken Race (茶色, 400 点)

場合分けやコーナーケース回避がエグい問題! 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …

AOJ 2295 Power of Power (JAG 夏合宿 2011 day2-F) (550 点)

コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…

Codeforces Round #681 (Div. 1) C. Graph Transpositions (R2400)

AOJ-ICPC みを感じる! 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。頂点 1 から頂点 へとたどり着きたい。以下の 2 種類の操作ができる。 頂点 上にいるとき、辺 をたどって、頂点 へと移動する 移動に要するコストは 1 任意の頂点に…