面白かった！ カタラン数的なものが登場する。 問題へのリンク 問題概要 制約 考えたこと まずすぐにわかったことは、 の中に、1 が 2 個以上あってはダメ の中に、1 が末尾以外の場所にあってはダメ ということだった。そうすると、 は次のいずれかの形にな…

辞書順最小と言われたら......！！ 問題へのリンク 問題概要 文字 'd', 'p' からなる長さ の文字列 が与えられる。 この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。 こうしてできる文字列のうち…

この時代、この手の Greedy はたくさんあったのね！ 問題へのリンク 問題概要 長さ の数列 が与えられる。「数列の要素を 1 つ選び、+1 するか、-1 する」という操作を行うことで、次の状態を達成したい。ただし、 とする。 すべての に対して、 である すべ…

ちょっとした算数的な考え方が必要になる問題 問題へのリンク 問題概要 JOI 君は以下の行動を行動 A → 行動 B → 行動 A → ⋯ のように交互に繰り返す。 行動 A：3m 前に進む 行動 B：2m 後ろに戻る 行動を合わせて 回行うとき、何m進むか？ 解法 このような問…

整理するのが大変な問題 問題へのリンク 問題概要 3 つの相異なる整数 がある（値は与えられない）。 これらの 3 つの整数の大小関係を表す 3 つの文字 が与えられる。たとえば が '<' であるとき、 であることを表す。 が '>' であるとき、 であることを表…

で場合分けする系！ 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす最小の整数 （）を求めよ。(存在しない場合は -1。） 【条件】 を 進法表記したときの桁の和が である 制約 考えたこと が小さい範囲は愚直に調べればよさそうだ。 があ…

上手に場合分けして解いていこう。 問題へのリンク 問題概要 1 が書かれたカードが 枚、0 が書かれたカードが 枚、 −1 が書かれたカードが 枚ある。 これらのカードから、ちょうど 枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最…

ややこしいけど、落ち着いて考えればできる！ 問題へのリンク 問題概要 AtCoder 王国の住民は 時になるとたこ焼きへの愛を叫ぶことになっている。 AtCoder 王国に住む高橋君は毎日 時に就寝し 時に起床する。 高橋君はたこ焼きへの愛を叫ぶことができている…

確率を考えるための基礎となる問題！ 問題へのリンク 問題概要 コンテストに 1000 人が参加した。 上位 位は、確実に T シャツがもらえる 上位 位から 位までは、その中からランダムに 人が選ばれて、T シャツがもらえる それ以外は、T シャツをもらえない …

落ち着いて整理していこう！ 問題へのリンク 問題概要 以上の最小の 4 で割って 2 余る整数を求めよ。 制約 考えたこと を 4 で割った余りによって場合分けして考えよう。 が 4 で割り切れるとき：2 足すことで「4 で割って 2 余る整数」になるので、 が答え…

「ギリギリを考える」という考察の基本形と言える問題 問題へのリンク 問題概要 整数 が与えられるので、 を満たす整数 についての の最大値を求めよ。 制約 考えたこと この手の問題で考えることは、「端点のみ考えれば良いのでは」などと疑うこと。つまり…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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