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

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

場合分け

AtCoder ABC 355 A - Who Ate the Cake? (7Q, 灰色, 100 点)

ちょっと算数チックな問題 問題へのリンク 問題概要 人 1, 2, 3 が容疑者に挙げられている。次の証言がある。 「人 は犯人ではない」 「人 は犯人ではない」 犯人を特定できるかどうかを判定し、特定できるならば犯人を答えよ。 制約 は 1, 2, 3 のいずれか …

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

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

AtCoder ABC 352 A - AtCoder Line (7Q, 灰色, 100 点)

算数系の問題! 問題へのリンク 問題概要 解法 入力の中に が含まれるが、これは結局使わない。こういう変数に惑わされないようにしよう。次の 2 つの場合に分けて考える。 のとき (上りのとき) のとき (下りのとき) 前者の場合は、"Yes" となる条件は と書…

JOI 一次予選 2024 (第 1 回) B - 和の判定 (8Q, 難易度 1)

上手に場合分けしよう! 問題へのリンク editorial 問題概要 3 個の整数 が与えられる。 これらのうちの 1 個が、残りの 2 個の和として表せるときは 1 を出力し、そうでないときは 0 を出力せよ。 解法 「3 個の整数 のうちの 1 個」が残りの 2 個の和とし…

AtCoder ABC 225 A - Distinct Strings (7Q, 灰色, 100 点)

これ結構難しいと思う! 数学 IA の「場合の数」をやると、よく出て来るやつですね。 問題へのリンク 問題概要 英小文字のみからなる長さ 3 の文字列 が与えられます。 の各文字を並び替えて得られる文字列は、何種類ありますか? 解法 「3 個のものを並び替…

AtCoder ABC 190 A - Very Very Primitive Game (灰色, 100 点)

これは整理するのが大変!!! 問題へのリンク 問題概要 高橋君は 個のアメを持っていて、青木君は 個のアメを持っている。 交互に自分のアメを食べていき、先に食べられなくなった方が負けである。 ならば高橋君が先手、 ならば青木君が後手。 どちらか勝つ…

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

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

AtCoder ABC 135 A - Harmony (灰色, 100 点)

これは難しい! 問題へのリンク 問題概要 2 個の整数 が与えられる。 を満たすような整数 が存在すればそれを答えて、存在しない場合には "IMPOSSIBLE" と答えよ。 解法 これは難しい。結論から言えば、 は整数でなくてもよいならば、 の平均値 となる。下図…

AtCoder ARC 167 E - One Square in a Triangle (銅色, 800 点)

天才構築ゲー。これ完全自力で一発 AC できて嬉しかった!! 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。 頂点がすべて格子点であり、座標値は 以上 以下である すべて…

AtCoder ARC 171 A - No Attacking (茶色, 400 点)

慎重に解いた。ノーペナで解けたのは収穫。 問題へのリンク 問題概要 のグリッドに、以下の条件を満たすように 個のルークと 個のポーンを配置することが可能かどうかを判定せよ (ルークとポーンを合わせて駒と呼ぶ)。 どのルークについても、それと同じ行・…

AtCoder ABC 079 A - Good Integer (灰色, 100 点)

これは難しい! 問題へのリンク 問題概要 4 桁の整数 が与えられる。この整数が「同じ数字が 3 つ以上連続しているか」を判定せよ。 解法 を文字列として受け取る方が楽だと思われる。このとき、同じ数字が 3 つ以上連続するのは次の 2 パターンがある。 N …

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

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

AtCoder ABC 323 E - Playlist (水色, 450 点)

よくある区間分割の DP だけど、それでよいことに思い至るのが難しいかもしれない。 問題へのリンク 問題概要 曲あって、それぞれの曲の長さは である。 今、時刻 0 から開始して「曲を一様ランダムに流し、それが終わったらまた一様ランダムに曲を選択して…

AtCoder ABC 047 A - キャンディーと2人の子供 (8Q, 灰色, 100 点)

これも「まずソートして考える」が効く系。でも、そうしなくても解ける。 問題へのリンク 問題概要 3 つの正の整数 が与えられる。 これらを 2 つのグループに分けて、各グループの数値の総和が等しくなるようにできるかどうかを判定せよ。 解法 (1):場合分…

AtCoder ABC 046 A - AtCoDeerくんとペンキ (7Q, 灰色, 100 点)

3 つの整数についてあれこれ問う問題はこの時代多かった 問題へのリンク 問題概要 3 個の整数 がある。これらは 1 以上 100 以下の整数である。 これらの整数の種類数を求めよ。 コード この手の問題は、「配列として受け取ってソートする」テクニックが使え…

AtCoder ABC 322 G - Two Kinds of Base (赤色, 600 点)

コンテスト後に解いた。なんとか詰め切った。 問題へのリンク 問題概要 非負整数 と整数 に対して、関数 を次のように定義する。 正整数 が与えられて、次の条件を満たす非負整数列 と正の整数 の組の個数を 998244353 で割った余りを求めよ。 () 制約 考え…

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

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

AtCoder ABC 321 G - Electric Circuit (橙色, 600 点)

除原理! 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…

AtCoder ABC 321 E - Complete Binary Tree (青色, 450 点)

この問題をキッカケに準完全二分木のライブラリを拡充した! 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。頂点番号は である。各頂点 (> 2) について、親頂点は である。 この根付き木において、頂点 からの距離が であるような頂点の個数を求…

AtCoder ABC 313 E - Duplicate (青色, 600 点)

こういうの詰めるの時間かかる。サンプルも弱いので、愚直シミュレーション解も実装して、それとの一致を確かめたりなどした! 問題へのリンク 問題概要 '1'〜'9' のみからなる文字列 が与えられる。この文字列に対して文字列を返す関数 がある。 は次の操作…

AtCoder ABC 272 C - Max Even (灰色, 300 点)

ちょっと面白い問題! 競プロ始めたばかりの方々に、計算量のことを意識させるのに良い問題かもしれない。 問題へのリンク 問題概要 どの 2 つの値も互いに相異なるような、長さ の数列 が与えられる。 この数列 の異なる 2 要素の和として表せる値の中に偶…

AtCoder ABC 259 Ex - Yet Another Path Counting (橙色, 600 点)

opt さんとのスペースで解いた! いくつか典型を見落としていたのでメモ!! 問題へのリンク 問題概要 のグリッドがあって、マス には値 が記されている。 いずれかのマスから始めて右または下に隣接するマスへの移動を 0 回以上繰り返すことで得られる経路…

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

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

AtCoder ARC 050 D - Suffix Concat (試験管橙色)

めっちゃ面白い問題だった! Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…

DISCO presents 2016 予選 C - アメージングな文字列は、きみが作る! (橙色)

とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…

AtCoder ABC 280 G - Do Use Hexagon Grid 2 (赤色, 600 点)

ハニカムにそんな性質があるなんて!!! 45 度回転する技術のアナロジーが炸裂する。 あと、x 座標が最小となる点で場合分けする際に、同一の x 座標を持つものに対してダブルカウントを除去する工夫が大変だった。 問題へのリンク 問題概要 2 次元平面上に…

JOIG 2021 C - イルミネーション 2 (AOJ 0703, 難易度 4)

落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね! 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…

AtCoder ABC 213 G - Connectivity 2 (橙色, 600 点)

面白かった!! より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…

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

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

Xmas Contest 2020 B - Beterminant

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