Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 407(Promotion of AtCoderJobs)

3完

各問題

A - Approximation

答えは A / B か A / B + 1 になります。

A % B が B / 2 以下であれば、端数が 1/2 よりちいさいので A / B で、そうでなければ A / B + 1 です。

B - P(X or Y)

全探索すればよいです。

C - Security 2

後ろの数字を変えると前の数字にも影響しますので、後ろから確定させていきます。

一番後ろはいいとして、それ以降は「それより後ろの数を確定させるために何回ボタンBを押す必要があるか(の mod 10)」を保存しておいて、それを加味してどの数字で止めて次の数字に行けばよいかをもとめます。

D - Domino Covering XOR

全探索可能っぽいので全探索したのですが、なぜか答えが合わず。全探索の仕方が間違っているのかロジックにバグがあるのか...。

まとめ

全探索できる問題が全探索できると分かっているのに落としたらいかんだろ...。

パナソニックグループ プログラミングコンテスト2025(AtCoder Beginner Contest 406)

4完

各問題

A - Not Acceptable

  • A > C
    • Yes
  • A < C
    • No
  • A = C
    • B > D
      • Yes
    • B < D
      • No

分に換算して比較の方が速い(早い)と今気づきました。

B - Product Calculator

やることは簡単ですがオーバーフローがありえるので、多倍長整数を使ったり、丁寧に桁数を計算(X桁の数にY桁の数を掛けると、積は少なくともX+Y-1桁になる)したりして回避します。

C - ~

極大、極小の場所を求めて、いい感じに計算します。

D - Garbage Removal

(787 ms かかったので多分想定解ではないのですが)行ごとにどの列にごみがあるか、列ごとにどの行にごみがあるかを、map<int, set<int>> でもっておいて、捨てられたごみは実際にそこから erase するで十分間に合います。

E - Popcount Sum 3

上の桁から場合分けでいい感じにできそうでできずじまいでした。

あと、残り5分まで、popcount の値がちょうど K である x の 個数 を求めてました。(ちゃんと読め

まとめ

実はがっつり飲酒した後だったのですが、なんと3か月ぶりの水パフォ復帰ですってよ。競プロは飲酒して参加すべし!!(うそ

AtCoder Beginner Contest 405(Promotion of AtCoder Career Design DAY)

4完

各問題

A - Is it rated?

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

B - Not All

Aの先頭から見てはじめてM種の数値が揃ったところを削除した時点で「条件」が満たされなくなるので、その位置を特定すればよいです。

C - Sum of Product

Σを展開して式変形するとA_1(A_2 + A_3 + ... + A_N) + A_2(A_3 + ... + A_N) + A_3(A_4 + ... + A_N) + ... A_(N-1) * A_N となるのでそれを計算すればよいです。かっこの中の部分は累積和などで前計算できるので、都合 O(N) で処理可能です。

D - Escape Route

すべての非常口から同時に BFS して経路を特定すればいいです。ちょっと前も多点スタート BFS 出てたような?

E - Fruit Lineup

それぞれが存在できる領域は

リリリババババババ
オオオオオオブブブ

リンゴとオレンジの位置の組み合わせ、バナナとブドウの位置の組み合わせ、バナナとオレンジの位置の組み合わせを、O(BC) で計算することは可能ですが(コンビネーションを求めるための前計算はあらかじめやる)、それだと間に合いません。

間に合わせる方法が最後までわかりませんでした。

まとめ

もうひとおしがたりない。

AtCoder Beginner Contest 404(Promotion for Engineer Guild)

4完2WA

各問題

A - Not Found

含まれているかどうかのフラグを26個用意しておいて、まず S を見てフラグを立てて、最後にフラグが立っていないものをどれか一つ出力すればよいです。

B - Grid Rotation

回転は先に3回までやってしまえばよく、回してから色をそろえればよいです。揃えるべきマスの数は純粋にグリッド同士を比較すればよいです。

というわけで、グリッドを回転させられるかどうかが試される問題です。回転後のグリッドを U として、U[i][j] = T[n - 1 - j][i] みたいなことをやればよいです。

グリッドが右にしか回せないことをうっかりして1WA。グリッドの回転方向を間違えて1WA。結構痛かった。

C - Cycle Graph?

N = M かつすべての頂点の次数が 2 かつ連結成分が 1 つだけならそのグラフはサイクルグラフです。

1つ目の条件は見ればわかり、2つ目の条件は頂点ごとにそこから伸びる辺の数をカウントすればわかり、3つ目の条件は dsu を使えばわかります。

D - Goin' to the Zoo

一つの動物園について最大2回まで訪れる必要があるので、訪れる回数の組み合わせは 3N です。各組合せごとに、どの動物園にどの動物がいるかは たかだか N * M 回の検索でわかるので、全体の計算量は O(3N * M * N) で実は全探索が可能です。

E - Bowls and Beans

公式解説にあるような『「ひとつ前の豆が存在する茶碗」まで到達』をやったつもりなんですが答えが合わず。うーむ...。

まとめ

B で変なはまり方をしたのでパフォちょっと損してしまった。

AtCoder Beginner Contest 403(Promotion of AtCoder Career Design DAY)

3完

各問題

A - Odd Position Sum

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

B - Four Hidden

短い文字列なので全探索可能です。つまりTの1文字目から|U|文字目までがUと一致するか('?' の部分は一致するとみなす)、2文字目から|U|+1文字目までがUと一致するか、... を順次確認していけばよいです。

C - 403 Forbidden

各ユーザーごとに set でどのページの権限が与えられたかを管理、それとは別にすべての権限付与が行われたかどうかを管理、とすればよいです。

D - Forbidden Difference

各値がいくつ出現したかを保持しておいて、差がDで連続している部分を一つおきに削除していけばよいと思いました。

つまり D=3 で、(3 3 3 6 6 9) とあったら、個数は (3, 2, 1) で、6 を 2 個削除する、(3 6 6 6 6 9) とあったら、個数は (1, 4, 1) で、3 と 9 を 1 個ずつ削除する、とすればよいと思ったのですが、結構 WA がでる。

そして、終了 3 分前に (a, b, c, d, e) で a, c, d とか b, c, e とかを消すパターンがありうるんじゃね?と気がつきました。全然ダメじゃん。

まとめ

最初に浮かんだ方針に頭が固定されすぎた...。

東京海上日動プログラミングコンテスト2025(AtCoder Beginner Contest 402)

4完

各問題

A - CBC

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

B - Restaurant Queue

待ち行列を管理するキューを用意して、1 のクエリの時 X をキューに入れ、2のクエリの時キューから一つ取り出して表示、とします。

C - Dislike Foods

各食材ごとに、どの料理がそれを使っているかを管理します。

1日目から順に、克服された食材についてそれを使っている料理のKを一つ減らしていき、0になったらその料理は食べられるので答えに1加算します。その日の対象となるすべての料理について処理が終わった後に、その時点での答えを出力すればよいです。

D - Line Crossing

1 と A_i の差分と、B_i と N の差分の、差分(つまり(A_i - 1) - (N - B_i) 負の数になることがあるのでその場合 + N する)が一致するものは平行なので交わりません。

というわけで、上記の差分ごとに直線の個数を集計して、あとは簡単な組み合わせの問題です。

E - Payment Required

おそらく DP らしいということはわかったのですが、漸化式がわからず...。正解した問題と所持金の組に対する得点の期待値、というのは間違ってなかったらしく、あとは漸化式だけだった模様...。

まとめ

そんなに難しくなさそうなのに最後まで漸化式がわからないとはなぁ...。というわけで緑パフォ継続中。AtCoderを始めた最初期を除いて、8回連続緑パフォは自己新記録らしい。そんな新記録いらんねん!

AtCoder Beginner Contest 401

4完2WA からの?

各問題

A - Status Code

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

B - Unauthorized

ログイン状態を記憶しておき、ログインしていない状態で private が来た回数を数えます。

C - K-bonacci

累積和を取りながら A を埋めていけばよいです。(以下 sum[i + 1] に i までの累積和が入っているとする)

i < K の時は A[i] に 1 を入れます。i >= K の時は sum[i + 1] - sum[i - k] です。

都度 109 で割ったあまりをとるのを忘れずに。

D - Logical Filling

まず S に存在する o の数が K と一致する場合は、残りの ? はすべて . です。(これを忘れていて 1WA)

X が空集合でないことが保証されているので、o と隣接する ? は必ず . としてよいです。

あとは ? が連続する部分のそれぞれについて、 o が最大いくつ置けるかを数えていきます。その最大数が、K からすでにある o の数を引いたものより大きかった場合、o の位置は特定しないので残っている ? はそのままにせざるを得ず、それが最終的な答えとなります。

一致した場合、o はおけるだけおけばいいのですが ? の連続数が偶数個の場合は .o.oo.o. が決められないので ? のままになります。奇数個の場合は o.o.o のように確定します。

E - Reachable Set

1 <= k <= Nについて、頂点 k までの頂点から伸びる辺で構成されたグラフで 1 から k までが連結であるかどうかと、グラフ上で k 以下の頂点が繋がっている k より大きい頂点の数を記憶することで答えが導き出せます。

前者は dsu を使って、接続先の頂点 x が k 未満の辺はマージして、k より大きい辺はいったんプールしておいて x が k 未満になった段階で改めてマージするとすればよいです。後者は各頂点について接続済みかどうかのフラグを持っておけばよいです。

解けたんですが、最初無駄に set を複数使ってしまい TLE を出し、set を使わなくて済む実装を残り 20 秒で思いつき、10秒くらいで慌てて提出したらバグがあって RE でゲームセットでした。そして終了 2 分後に AC を得ました...。

まとめ

緑パフォストリーク継続中ですが、E が通せていれば水色だったので復活の兆しがある、と信じたい。