AtCoder Beginner Contest 349

4完

各問題

A - Zero Sum Game

何度ゲームを行っても全員の持ち点の合計点は 0 で変わらないので、1 から N - 1 までの得点を合計して符号をひっくり返したものが N の得点になります。

B - Commencement

各文字が何度現れるかを集計して、現れた回数ごとに何種類あるかを集計すればよいです。

C - Airport Code

以下、T を事前に小文字に変換したものとします。

S を前からみていって T が作れるかを確認すればよいです。ただし 2 文字目までしか作れなかった場合でも T の 3 文字目が X であれば Yes となります。

D - Divide Interval

未証明ですが、i を貪欲に取れるだけ大きくとると通ります。

入力例 1 の場合、3 は 2^0 * 3 以外できないのでこれと組になるのは 2^0 * 4 になります。

続いて 4 は S(2^0 * 4, 2^0 * 5), S(2^1 * 2, 2^1 * 3), S(2^2 * 1, 2^2 * 2) が考えられますが、i が一番大きい最後のものを採用します。

続いて 8 は S(2^3 * 1, 2^3 * 2) です。

16 は S(2^0 * 16, 2^0 * 17) , S(2^1 * 8, 2^1 * 9) があり得るので、後者を採用します。なお、i が 2 以上になると後ろが 19 を超えてしまうので使えません。

E - Weighted Tic-Tac-Toe

なんもわからん。

まとめ

どうにかこうにか水色復帰したっぽい。

トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）

4完

各問題

A - Penalty Kick

for で回すだけですが、[0, n) でなく [1, n] で回すとちょっと実装が楽になります。

for (int i = 1; i <= n) cout << (i % 3 ? "o" : "x");

B - Farthest Point

全探索するだけ。ちなみに平方根はとる必要がありませんし制約の範囲内だと int でおさまります。

C - Colorful Beans

map<int, set<int>> とかで色ごとにまとめて、色ごとに最小値をもとめてそれの最大値を答えればよいです。

set<int> にはせず最小値だけ保存でもいいですが、実装がほんのちょっとだけ面倒...。

D - Medicines on Grid

D は DP の D。なのかな？

ということで、各マスごとにそこに到達したときのエネルギーの最大値を保存し。それを超えているときだけ遷移できるとする BFS をすればよいです。

E - Minimize Sum of Distances

全方位木DPをすればよさそうというのはわかって、類題の ABC222F も見つけたのに、C の扱いをどうしていいのかわからずで解けず...。

まとめ

D までかなり早く解けたので、これは水復帰は固いなと思ったのに、結局ちょっと届かなかったっぽい。木DPできなかったのはいただけない...。

AtCoder Beginner Contest 347

5完4WA

この 4WA があることに大きく響くことに...

各問題

A - Divisible

いわれたとおりやりましょう。

B - Substring

すべての部分文字列を set に入れて、set の要素数が答えです。

最初連続しない部分列の問題を考えていてパニックになってました。

C - Ideal Holidays

実装をわかりやすくするため、0 日目から (A + B - 1) 日目までが一週間と考えます。以下、D は与えられたものを -1 したものとして考えます。

D % (A + B) を set に入れていきます。これで 0 日目を基準として何日目に予定があるかがわかります。

すべての予定が休日にあるということは、平日に予定がないということなので、各予定間の間が B 日より大きいところがひとつでもあればよいとなります。

あとは set の隣り合う要素の差が B より大きいかどうかを確認すればよいとなります。（先頭と末尾の組をチェックすることを忘れずに）

D - Popcount and XOR

まず C の popcount を求めてこれを c とします。c > (a + b) , c < abs(a - b), c % 2 != (a + b) % 2のとき構築不可能です。

あとは構築できるので、C の下位の桁から解決していきます。

C に 1 が立っている場合 (0, 1) か (1, 0) です。a, b の余っている方を当てればよいです。

C に 1 が立っていない場合 (0, 0) か (1, 1) です。X, Y それぞれについて ((a + b) - c) / 2 分の popcount が余ることになるので、このあまり分があるうちは (1, 1) として、そうでないときは (0, 0) とすればよいです。

あとはそのビット情報を 10 進に直して終了です。

E - Set Add Query

各番号についていつ S に追加されたかを保存する配列を用意しておきます。（追加されていないときは -1 などを入れておきます）

また、|S| が各クエリを処理した時点でいくつであるかを区間和を取得するセグメントツリーで管理しておきます。

各クエリごとにその配列の x 番目の要素を確認し、-1 ならばクエリの番目を入れ、-1 でなければセグメントツリーから [配列に入っている番目, 現在の番目) の和を取り出して、x 番目の答えに加算します。

クエリが終わった後に S に含まれている番目（配列に -1 以外が入っている番目）について、セグメントツリーから [配列に入っている番目, Q) を取り出して加算すれば最終的な答えが得られます。

F - Non-overlapping Squares

重ならないようにどうやって効率よく選べばいいのかわからず...

まとめ

パフォが 1648 以上なら水色復帰だったのですが、4WA のせいで届かず。（1WA までなら届いていた模様）

むねんなりー。

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）

5完

各問題

A - Adjacent Product

いわれたとおりやりましょう。

B - Piano

いろいろ考え方はある気がしますが、自分は S を充分な数（200 もあればよい）つなげた文字列を作って、W + B の幅に w と b がいくつあるかを一つずつずらしながら数えていきました。

制約が小さいので毎回いちいち数えても間に合いますが、新しく範囲に含まれた文字の分を足して範囲外になった文字の分を引いていけば効率よくできます。

C - Σ

最初に仮の答えとして K * (K + 1) / 2 と置きます。これはいうまでもなく、A の中にどれも現れなかった場合の答え（1からKまでの和）です。

あとは A の要素を一つずつみていって、K 以下のまだ現れていない数があれば仮の答えから引いていけばよいです。

D - Gomamayo Sequence

隣接する二文字のパターンは i 文字目と i + 1 文字目 がそれぞれ 00 になるときと 11 になるときの (N - 1) * 2 通りなので、それらをすべて調べます。

隣接する以外の場所は、i が偶数で 0 の時、その左については偶数文字目が 0、右については奇数文字が 0 、など一意に決まりますので、あらかじめ偶数文字目が 0 のときと偶数文字目が 1 のときのコストの累積和を求めておけば、O(1) で取り出すことができます。

E - Paint

最後に塗ったものが優先されるので、操作を後ろからみていって、どの行とどの列が塗られたかに注意して色の数を数えていけばよいです。

行を塗るときはまだ塗られていない行について W - （すでに塗られた列） 分塗ることができ、列についてはまだ塗られていない列について H - （すでに塗られた行） 分塗ることができます。

色 0 は初期値を H * W として、塗られるたびにこれを引いていく必要がありますが、0になった時に答えの出力に含めてしまわないよう注意です。

F - SSttrriinngg in StringString

二分探索で行けそうなのですが、行ききれず...。

まとめ

D の方針が固まるまでがめちゃくちゃ時間がかかってしまったのがあれなんですが、また一発で水色復帰できた（っぽい）のでよしとするか。

AtCoder Regular Contest 174

B のみ 1完

各問題

A - A Multiply

（C が正数の時）非負とそれ以外のものをまとめて、絶対値の小さい負数と大きい正数もまとめて、一番大きいところに C をかけるとよい、のような方針でやったんですが、テストケース半分くらい WA。

第一感は累積和だったんですが、それをどう使えばいいのか全く見当がつかなかった...。

B - Bought Review

平均が初手で3以上なら何もする必要がないので 0 を出力して終了です。

平均が3未満の時、星3以下をいくつ足しても平均が3以上になることはないので、4 と 5 をいくつ足せばよいかだけを考えればよいです。

星 5 だけを足すとしたとき、最低いくつ必要かは算数で求められます。あとは、0 から その最低必要数の間でもっとも費用が少ないものを探せばよいです。ここで（たぶん）「最適な状態から離れるほど費用が増える」が成り立つ（と思う）ので、二分探索的なことをすれば求めることができます。

まとめ

惨敗でまた緑落ち。そういえば 3 年ほど前にも、落ちて戻ってを 3 回繰り返したことがあったな...。いやでも今回かなり落ちたので次は青パフォくらいとらないと一発では戻れなさそうなんですが。

モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

3完

各問題

A - Leftrightarrow

文字列の左端が <、右端が >、中がすべて = であることを確認すればよいです。

B - Integer Division Returns

c++ では整数型の割り算 N / M は切り捨てになりますが、(N + M - 1) / M とすることで切り上げた結果を得ることができます。

というわけで X が非負の場合 (X + 10 - 1) / 10 とすればよいです。X が負の時は切りあがる方向の問題で同様の方法が使えませんが、実は単に X / 10 がほしい答です。

C - One Time Swap

それぞれの文字の個数を数えて、25 * 25 通り掛け算をして足し合わせれば、異なった文字を入れ替えたときの組み合わせの数が求められます。

もし、同じ文字が文字列中に複数個ある場合は同じ文字を入れ替えて S と同じ文字列を得ることができるので、上記の数に 1 を加える必要があります。

D - Tiling

回転も含めて最大 14 個中の 7 個を選び（もちろん同じものの回転形は重複して選ばないように注意して）、それを並び替えすると全探索になりますが、組み合わせの数が多すぎて間に合わず。

公式解説を見ると全探索で方針としては間違っていないようなのですが、探し方の効率が悪すぎた？

まとめ

D が解ききれず。C までが割と速かったのでかろうじて水色復帰はしたもののすっきりしない。

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）

5完6WA

各問題

A - Spoiler

与えられた文字列を前から読んで出力ですが、最初の | が出た時点で出力をやめ、次の | が出た次から出力を再開とすればよいです。

B - Delimiter

入力した整数を配列に入れていき、0 が出現したら入力をやめて、配列を逆順で出力すればよいです。

C - A+B+C

N, M, L がたかだか 100 なので、A + B + C のすべての組み合わせを先に計算して set に入れておき、X がその set に含まれるかどうかを確認していけばよいです。

D - String Bags

つまるところ、dp[l] = l 文字目まで一致させるために必要な最小の金額 とした動的計画法をすればよいだけではあります。

いわゆる配るDPでやる場合、文字列の後ろの方から確定させなければならないことに注意です。これで 6WA だしました。on_

E - Insert or Erase

（もっと効率のよい管理方法があるかもしれませんが）、数列の各要素について、後ろに何があるかと前に何があるかを管理しておけば、各クエリごとに要素 x の周りだけを操作すればよいのでいけます。

まとめ

D ではまらなければ青パフォまであったのか...。現実は緑パフォ。厳しい。