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

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

入力が定数個

AtCoder ABC 208 A - Rolling Dice (灰色, 100 点)

「この数からこの数の間の数はすべて作れる」という考え方をする問題。この考え方は、より高度な問題では頻出! 問題へのリンク 問題概要 1〜6 の目が出るサイコロを 回振った。 出た目の総和が になることがありうるかどうかを判定せよ。 解法 これは難しい…

AtCoder ABC 065 A - Expired? (灰色, 100 点)

これはちゃんと整理するの大変だと思う! 問題へのリンク 問題概要 ある商品は、賞味期限を過ぎてから 日後まではお腹を壊さずに食べることができる。一方、賞味期限を過ぎてから食べると美味しくありません。 その商品を、賞味期限の 日前に購入し、その日…

AtCoder ABC 326 B - 326-like Numbers (灰色, 200 点)

整数 が 326-like 数かどうかを判定する処理が書ければ、この問題は解ける。 問題へのリンク 問題概要 整数 が 326-like 数であるとは、3 桁の正の整数であって、百の位と十の位の積が一の位に等しいことをいう。 与えられた整数 以上の、最小の 326-like 数…

AtCoder ABC 326 A - 2UP3DOWN (灰色, 100 点)

落ち着いて整理しよう! 問題へのリンク 問題概要 100 階のビルで 階から 階へと移動したい。 2 階分までの上り、または、3 階分までの下りであれば移動には階段を使い、そうでないときエレベーターを使う。 階段を使うかどうかを判定せよ。 コード 落ち着い…

AtCoder ABC 319 B - Measure (灰色, 200 点)

問題文で書かれた通りに実装するだけなのだが、問題文の内容を理解するのが大変で、戸惑った人も多いかもしれない。 問題へのリンク 問題概要 正の整数 が与えられるので、次のようにして定まる 文字の文字列 を出力せよ。 に対して、1 以上 9 以下の の約数…

Yosupo Library Checker - A + B

Yosupo Judge で最初に解くであろう問題 問題へのリンク 問題概要 2 つの整数 が与えられるので、 を出力してください。 制約 考えたこと 10Q 相当の問題。標準入力ができる人なら解けるはず。 コード #include <iostream> #include <vector> using namespace std; int main() </vector></iostream>…

TTPC 2023 E - R-Connected Components

大好き!!ガウス整数の問題リストがまた 1 個増えた! 問題へのリンク 問題概要 1 つの正の整数 が与えられる。 二次元平面上の任意の格子点を頂点としたグラフにおいて、距離の平方が であるような 2 点間に辺を張っていく。 こうしてできたグラフの連結成…

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

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

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

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

AtCoder ABC 321 A - 321-like Checker (灰色, 100 点)

入力を文字列として受け取ってしまうのが楽だと思う! 問題へのリンク 問題概要 各桁の値が単調減少 (等しいはダメ) になっている数を 321-like 数と呼ぶことにする。 たとえば、971 や 5 は 321-like 数であるが、978 や 988 は 321-like 数ではない。 与え…

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

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

Codeforces Round 539 (Div. 1) D. Sasha and Interesting Fact from Graph Theory (R2400)

また一つ、プリューファーコードの練習問題が増えた! 問題へのリンク 問題概要 正の整数値 が与えられる。 頂点数 の重み付き木であって、以下の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 各辺の重みは 以上 以下の整数値である 2 頂点 …

AtCoder ABC 318 Ex - Count Strong Test Cases (橙色, 650 点)

コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…

競プロキャンプ2023関西 L - (sum)mer

FPS + 負の二項係数 問題へのリンク 問題概要 長さが で総和が であるような、正の整数のみからなる数列 すべてについての の総和を 998244353 で割ったあまりを求めよ ( ケース)。 制約 解法 (1):FPS 求めたいものは である。これはちゃんと計算すると、 …

M-SOLUTIONS プロコンオープン A - Sum of Interior Angle (灰色, 100 点)

算数の知見がないと、案外難しいかもしれない。 問題へのリンク 問題概要 以上の整数 が与えられます。 正 角形の内角の和を求めてください。 制約 解法 多角形の内角の和の公式を使います。知らない方も、「多角形 内角の和」などと検索すると出て来ると思…

AtCoder ABC 201 A - Tiny Arithmetic Sequence (灰色, 100 点)

意外と頭がこんがらがるかもしれないですね。100 点問題で必須となるテクニックではないですが、ソートすると考えやすいと思います。 問題へのリンク 問題概要 個の整数 が与えられる。 これら 個の整数を適切に並び替えることで、等差数列にすることが可能…

AtCoder ABC 235 D - Multiply and Rotate (緑色, 400 点)

最小回数を求めるには BFS!!(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…

AtCoder ABC 254 D - Together Square (緑色, 400 点)

なんかユーザー解説の数がすごいことになっててビビる! 問題へのリンク editorials 問題概要 以下の正の整数 の組であって、 が平方数であるようなものの個数を求めよ。 制約 考えたこと この手の問題では「ある変数を固定して考える」という常套手段がある…

AtCoder ABC 292 C - Four Variables (茶色, 300 点)

これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね! 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…

AtCoder ABC 296 D - M<=ab (緑色, 400 点)

「ある量を固定して考えるとよい」「 まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。 以上の整数のうち、 以上 以下の 2 つの整数 の積 として書ける最小の整数を求めよ。 そのよう…

AtCoder ARC 160 D - Mahjong (橙色, 700 点)

FPS による考察はやっぱり強力ですね! 問題へのリンク 問題概要 長さ かつ総和 である非負整数列 のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 「以下の操作のうちどちらかを選んで行うことを繰り返して、 の全ての要素を 0…

AtCoder ABC 266 G - Yet Another RGB Sequence (黄色, 600 点)

すごく楽しかった。解析的に式で求められるのね。 問題へのリンク 問題概要 個の文字 R、 個の文字 G、 個の文字 B を並べてできる文字列のうち、部分文字列として含まれる RG がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…

AtCoder ABC 256 G - Black and White Stones (黄色, 600 点)

opt さんの得意系って感じだった! 問題へのリンク 問題概要 一辺の長さが整数 の正 角形がある。 頂点から始めて、周上に距離 1 ごとに黒い石か白い石を置いていく。 石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものの個数を 998244353 …

AtCoder ABC 281 Ex - Alchemy (赤色, 600 点)

この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…

yukicoder No.2066 Simple Math !

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

yukicoder No.2032 Let's Write Multiples!!

floor sum の練習! 問題へのリンク 問題概要 以上 以下の の倍数をすべて十進表記で 1 回ずつ書き出した時、数字 が書かれる回数を求めよ。 (テストケースが 個与えられる) 制約 考えたこと 各桁ごとに考える。整数 の右から 桁めが である条件は を で割っ…

AtCoder ABC 281 G - Farthest City (黄色, 600 点)

残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…

AtCoder ABC 250 D - 250-like Number (茶色, 400 点)

緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね! 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…

AtCoder ABC 213 A - Bitwise Exclusive Or (100 点)

XOR は 2 回やると元に戻る!!!(素振り!) 問題へのリンク 問題概要 非負整数 が与えられます。 ^ = を満たす整数 を求めてください。 制約 XOR とは XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事…

JOIG 2021 A - 金平糖 (AOJ 0701, 難易度 1)

入出力の練習をしましょう。 問題へのリンク editorial 問題概要 3 人の生徒がそれぞれ 個、 個、 個の金平糖をもらいました。 これからそれぞれの生徒たちに何個かの金平糖を追加で渡すことで、3 人の生徒がもらった金平糖の個数が等しくなるようにしたいと…