Toy と帽子と ADP BE

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

トヨタ自動車プログラミングコンテスト2023#8(AtCoder Beginner Contest 333)

5完

各問題

A - Three Threes

こんなかんじで。

for (int i = 0; i < n; i++) cout << n;

B - Pentagon

abs(S[0] - S[1])abs(T[0] - T[1]) を計算して、どちらも 1 or 4 のとき、どちらも 2 or 3 のときは距離が等しいです。

C - Repunit Trio

priority_queue に(符号を逆転させて)入れて、一番大きい(元の値は小さい)ものを取り出してそこに 1, 11, 111 を足して priority_queue に入れる、を繰り返して取り得る値を作っていく典型のやつです。

1の位が3のときが3つの和になのでそれを答えの候補とします。

D - Erase Leaves

頂点1をルートとして、それにぶら下がる部分木のうちでいちばん頂点数が多いものを残して他を削除していくのが最適なので、部分木の頂点数を DFS などで数えます。

E - Takahashi Quest

ポーションはできるだけ持っている期間を短くしたいので、モンスターに一番近いものを拾うようにします。

クエリを後ろからみていくことで、モンスターに対して一番効率のよい(一番モンスターに近い)ポーションがどれかがわかるようになります。ポーションの保持数は、後ろから見た場合だとある時点で倒せていないモンスターの数と同じになります。

クエリを最初までさかのぼった時に生存しているモンスターがいた場合、敗北決定です。

F - Bomb Game 2

数学弱者すぎて、入力例1が 1/3 と 2/3 になるということがそもそもわからないという...。

まとめ

C の実装でまごついてしまった(queue から pop し忘れてただけ...)のでちょっともったいなかったですが、Eまですんなり解けたのでまあまあいい結果になったのではないでしょうか。

あすの AGC に向けていい貯金ができました。