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

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

AtCoder

AtCoder ABC 307 E - Distinct Adjacent (1Q, 水色, 475 点)

共通テスト数学 IA にも似た問題が出ていた! 問題へのリンク 問題概要 頂点数が のサイクルグラフが与えられる。このグラフの各頂点を色 のいずれかの色で塗る。 どの隣接する頂点対も異なる色で塗られるようにする方法の個数を 998244353 で割った余りを求…

AtCoder ABC 307 D - Mismatched Parentheses (3Q, 茶色, 400 点)

カッコ列に関連してシミュレーションしていく問題! 問題へのリンク 問題概要 英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。 「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含ま…

AtCoder ABC 307 C - Ideal Sheet (1Q, 水色, 300 点)

とても面倒な全探索問題 問題へのリンク 問題概要 サイズが等しいとは限らない 3 つの白黒のグリッド が与えられる。 ある巨大なグリッドに、2 つのグリッド を重ね合わて (黒色部分について OR をとる)、そこから適切に長方形領域を切り出すことで、グリッ…

AtCoder ABC 357 D - 88888888 (1Q, 緑色, 350 点)

面白かった! 問題へのリンク 問題概要 整数 が与えられる。 整数 の十進法表記を 個 concat してできる整数を 998244353 で割った余りを求めよ。 制約 考えたこと まず、整数 が 桁だとしよう! このとき、求めたい値は次のように表現できる。 よって、 と…

AtCoder ABC 357 C - Sierpinski carpet (4Q, 灰色, 250 点)

いろんな方法で実装できそう! 問題へのリンク 問題概要 非負整数 に対して、レベル のカーペットを再帰的に定義する。 レベル のカーペットは、"#" からなる 1 × 1 のグリッドである に対して、レベル のカーペットは のグリッドであり、 このグリッドを の…

AtCoder ABC 357 E - Reachability in Functional Graph (1D, 水色, 450 点)

久々! Functional Graph のサイクル検出と DP 問題へのリンク 問題概要 頂点数 の functional graph が与えられる (出次数 1 の有向グラフ)。 このグラフの 2 頂点 からなる順序対 であって、頂点 から頂点 へと至るウォークが存在するものの個数を求めよ (…

AtCoder ABC 357 B - Uppercase and Lowercase (7Q, 灰色, 200 点)

文字列の大文字・小文字変換もできるようにしていきたい。 問題へのリンク 問題概要 英大文字または英小文字からなる文字列 が与えられる。 大文字の個数が小文字の個数よりも多い場合は、すべて大文字に変換し、そうでない場合はすべて小文字に変換して出力…

AtCoder ABC 357 A - Sanitize Hands (7Q, 灰色, 100 点)

意外とミスりやすいかもしれない。慎重に for 文を書こう。 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 に対して、 を順に引いていく。このとき、 が負にならずに引ける最大個数を求めよ。 解法 実際に順番に から引いていって、 で…

AtCoder ABC 357 F - Two Sequence Queries (2D, 青色, 550 点)

maspy さんの次のツイートがすべて!! F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…

AtCoder ABC 356 A - Subsegment Reverse (7Q, 灰色, 100 点)

整数値に対する for 文の練習!! 問題へのリンク 問題概要 数列 がある。 この 項目から 項目までを反転させてできる数列を出力せよ。 解法 for 文を用いて次のようにすればよい。 から までを順に出力する から までを逆順に出力する から までを順に出力…

AtCoder ABC 356 B - Nutrients (6Q, 灰色, 150 点)

二次元配列の練習問題! 問題へのリンク 問題概要 種類の栄養素があり、 番目の栄養素を g 以上摂取したい。 そこで、 個の食品を食べる。 番目の食品を食べると、栄養素 を g 摂取できる。 この 個の食品を食べることで、 種類すべての栄養素を必要量以上に…

AtCoder ABC 356 C - Keys (2Q, 茶色, 300 点)

問題の意味を理解するのが難しいが、理解してしまえばビット全探索で解けることは比較的分かりやすいと思う! 問題へのリンク 問題概要 本の鍵 があり、それぞれ本物であるか、ダミーであるかのいずれかである。ドア X があり、鍵のうちの 本以上の本物が使…

AtCoder ABC 356 D - Masked Popcount (1Q, 緑色, 400 点)

すごく教育的問題! 問題へのリンク 問題概要 非負整数 が与えられるので、次の値を 998244353 で割った余りを求めよ。 & 制約 考えたこと この手の問題は「主客転倒」して、上記の総和を各桁ごとに考えればよいと相場が決まっている!!! 具体的には、次の…

AtCoder ABC 356 E - Max/Min (1D, 水色, 475 点)

面白かった! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい!!! きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…

AtCoder ABC 356 F - Distance Component Size Query (3D, 黄色, 525 点)

苦手系の問題だけど、解けてよかった。 問題へのリンク 問題概要 正の整数 が与えられる。はじめ空である集合 が与えられるので、次のクエリに答えよ。 クエリタイプ 1 x:集合 に整数値 がない場合は挿入し、ある場合は削除する クエリタイプ 2 x:集合 に…

AtCoder ABC 356 G - Freestyle (5D, 赤色, 575 点)

この見た目で「幾何」になるの、面白い! 問題へのリンク 問題概要 高橋君は 種類の泳ぎ方ができる。 種類目の泳ぎ方では、1 秒間に体力を だけ消費して、 メートル進むことができる。このとき、次の 回のクエリに答えよ。 【クエリ】 正の実数 が与えられる…

鉄則本 B13 - Supermarket 2 (2Q, ★4)

しゃくとり法の練習問題! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 この数列の連続する区間であって、総和が 以下であるものの個数を求めよ。 制約 解法 (1):しゃくとり法 editorial に詳しく書かれている。 github.com コー…

鉄則本 A13 - Close Pairs (3Q, ★4)

しゃくとり法の基本! 問題へのリンク 問題概要 個の整数 が与えられる。これらの整数から異なる 2 個を選ぶ方法のうち、2 個の値の差が 以下であるものの個数を求めよ。 制約 解法 (1):しゃくとり法 鉄則本の問題なので、鉄則本を参照 #include <bits/stdc++.h> using nam</bits/stdc++.h>…

鉄則本 B12 - Equation (3Q, ★4)

方程式を解くのに二分探索が使えることが多々ある! 問題へのリンク 問題概要 正の整数 が与えられる。 を正の実数 を求めよ。ただし、相対誤差または絶対誤差が 0.001 以内であれば正解とみなされる。 制約 メモ editorial にとても解法が書いてある。 gith…

AtCoder ABC 309 C - Medicine (3Q, 灰色, 350 点)

はじめての「〜が 以下になる瞬間」を捉えるというシミュレーション問題。 問題へのリンク 問題概要 高橋君は 種類の薬を処方された。薬 は、 日目まで、毎日 錠ずつ飲むこととなる。 1 日に飲む錠剤の個数がはじめて 錠以下になる日を求めよ。 制約 考えた…

AtCoder ABC 355 B - Piano 2 (6Q, 灰色, 200 点)

ソートの練習! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。なお、これら 個の値はすべて互いに相異なる。 これらをすべて混ぜた 個の値を小さい順に並べたとき、数列 の要素が 2 個以上連続する箇所があるかどうかを判定せよ。 制…

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

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

AtCoder ABC 355 D - Intersecting Intervals (2Q, 茶色, 400 点)

ものすごく教育的な典型問題! 色んな方法が考えられるが、ここでは区間ソートで解いてみる。 問題へのリンク 問題概要 数直線上に 個の区間が与えられる。 番目の区間は である。 これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。 制…

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

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

AtCoder ABC 052 B - Increment Decrement (7Q, 灰色, 200 点)

文字列の動きをシミュレーションしながら最大値も更新していく! 問題へのリンク 問題概要 整数 を持っていて、最初は 0 である。 長さ の文字列 に従って、これを使って [tex] N] 回の操作を行った。 回目の操作では、文字 が 'I' ならば を 1 増やし、'D' …

AtCoder ABC 275 B - ABC-DEF (5Q, 灰色, 200 点)

mod 998244353 の練習! 問題へのリンク 問題概要 非負整数 が与えられる。 を 998244353 で割った余りを求めよ。 制約 考えたこと 「足し算・引き算・かけ算」をした計算結果を 998244353 で割った余りを求める方法論については、次の記事に詳しく書いた。 …

AtCoder ABC 052 C - Factors of Factorial (3Q, 緑色, 300 点)

素因数分解を上手に活用しよう! 問題へのリンク 問題概要 正の整数 が与えられる。 の正の約数の個数を 1000000007 で割った余りを求めよ。 制約 考えたこと 「約数の個数」をまともに考察する場合には、素因数分解が役にたつことが多い。一般に正の整数 が…

AtCoder ABC 048 C - Boxes and Candies (2Q, 茶色, 300 点)

とても教育的な Greedy 問題! 問題へのリンク 問題概要 個の非負整数からなる数列 が与えられる。この数列に対して、 「正の整数である要素を 1 つ選び、-1 する」 という操作を繰り返すことで、どの隣接する 2 個の要素の和も 以下となるようにしたい。 こ…

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

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

AtCoder ABC 049 B - たてなが (7Q, 灰色, 200 点)

二次元グリッドの基本問題 問題へのリンク 問題概要 のグリッドが与えられる。各マスの文字は '.' か '*' である。 このグリッドを縦方向に 2 倍に引き伸ばして出力せよ。 解法 個の文字列の入力を受け取り、各行ごとに 2 回ずつ出力していけば OK。 #includ…