「二項係数の和」は結構なんとかなることを学んだ！ 備忘録程度に書く。 問題へのリンク 問題概要 下の図のように、 グリッドを、レベル の L 字で隙間なく埋め尽くす (レベル の L 字の定義は問題文参照)。 マス を指定したとき、次の 回のクエリに答えよ。…

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

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

順列をどうのこうのする系、最近多いかもしれない。 問題へのリンク 問題文 考えたこと 操作の内容を解釈するのに少し苦労した。 順列 から誘導される Functional Graph を考えた。このグラフ上で、頂点 から出発して頂点番号が大きくなる限り進んでいったと…

面白かった！ 問題へのリンク 問題概要 以上の整数 と非負整数 が与えられる。 の正の約数の総積が で最大何回割れるかを 998244353 で割った余りで求めよ。 制約 考えたこと 一般に、2 以上の整数 の正の約数の総積は、 の約数の個数を とすると となる。た…

これ系は好き！ これに近いのを ABC-D で最近よく見かける気がする。 問題へのリンク 問題概要 整数 が与えられる。 3 つの整数の組 であって、 がすべて 以下であるようなものの個数を 998244353 で割ったあまりを求めよ。 ケース与えられる。 制約 考えた…

「決めてから、整合性を確認する」というタイプの問題の典型例ですね！ 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…

本番 14 分かけたのは反省。 問題へのリンク 問題概要 "110" という文字列を 10000000000 個連結してできる文字列を とする。 長さ の文字列 が与えられる。 の中に が連続する部分文字列としていくつ含まれるかを求めよ。 制約 考えたこと こういう、端の処…

二分探索でやればよさそう。本当は でもできるのかも。 問題へのリンク 問題概要 正の整数 が与えられる。 整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。 選んだ整数はいくつかの…

カッコ列系の問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…

半分全列挙した！ 問題へのリンク 問題概要 正の整数 と整数 が与えられる。以下の条件を満たす正の整数 の組の個数を求めよ。 制約 考えたこと 愚直な方法としては、次のように 4 重ループをする解法が考えられるかもしれない。しかしこれでは の計算量を要…

問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。各頂点 には値 が書かれている。以下の操作を好きな順序で好きな回数だけ行うことで、各頂点 の数値が であるような状態にすることが可能かどうかを判定せよ。 辺 を選んで、以下のいずれ…

操作が「Euclid の互除法」っぽくなっている系の問題！！！そういう系の問題は次の一覧で示してる drken1215.hatenablog.com 問題へのリンク 問題概要 個の正の整数 に対して次の操作を繰り返し行う。 個の整数の最大値を 、最小値を とする。 なら手続きを…

Zero-Sum Ranges だった！！！ 問題へのリンク 問題概要 'A', 'G', 'C', 'T' からなる文字列 が相補的であるとは、 を並び替えてできる文字列 が存在して、 T[ i ] = 'A' ならば T'[ i ] = 'T' T[ i ] = 'T' ならば T'[ i ] = 'A' T[ i ] = 'G' ならば T'[ i…

こういう全探索、意外と思い浮かぶようになるまでが遠いよね。 そして のケースが結構厄介 ^^; 問題へのリンク 問題概要 二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、 最初の点では +1 そ…

これと大体一緒かな。 むしろ合計枚数に関する制約がない分、やや難しくなっているかもしれない。 問題概要 を正の整数とする。 を満たすような 0 以上の整数 の組が何通りあるか求めよ。 制約 考えたこと 愚直に探索しようと思うと int res = 0; for (int r…