【AtCoder】AtCoder Beginner Contest 424 - 参加記 | 緑コーダーが解くAtCoder

atcoder.jp

コンテスト時間: 2025-09-20(土) 21:00 ~ 2025-09-20(土) 22:40 (100分)

A - Isosceles

Difficulty: ??? / NoviSteps: ???

解答時間: 1:13

面積が正である三角形 ABC があり、三辺の長さはそれぞれ $a,b,c$ である。三角形 ABC が二等辺三角形であるか判定せよ。

$a = b = c$ なら正三角形なので Yes 。
そうではなく、 $a = b$ または $b = c$ または $c = a$ なら Yes 。そうでなければ No 。

B - Perfect

Difficulty: ??? / NoviSteps: ???

解答時間: 3:24

人が問からなるプログラミングコンテストに参加した。このコンテストでは個のイベントが順番に起き、番目のイベントは以下の通り。
- 人 $A_i$ が問題 $B_i$ に正解した。
すべての問題に正解した人の番号を全員出力せよ。そのような人が複数いる場合は、すべての問題に正解したタイミングが早い順に出力せよ。

各参加者がどの問題を解いたかをシミュレーションしていき、イベントが起きるごとにその人が全問正解しているかをチェックすればよい。

C - New Skill Acquired

Difficulty: ??? / NoviSteps: ???

解答時間: 12:13

$1$ から $N$ の番号がついた $N$ 個のスキルがある。 $N$ 個の整数の組 $(A_1,B_1), \dots,(A_N,B_N)$ が与えられ、 $(A_i,B_i)=(0,0)$ のときスキル $i$ を習得済みである。そうでないとき、スキル $A_i,B_i$ の少なくとも一方を習得済みのときに限りスキル $i$ を習得することができる。既に取得済みのスキルも含め、最終的に習得することができるスキルの個数を求めよ。

スキル習得のための依存関係は有向グラフで表すことができる。
すでに習得済みのスキルを始点として、このグラフに対して BFS / DFS を行えばよい。

D - 2x2 Erasing 2

Difficulty: ??? / NoviSteps: ???

解答時間:25:30

$H \times W$ のマス目があり、各マスは白または黒に塗られている。高橋君は $0$ 個以上の黒く塗られたマスを白に塗り替えることで、マス目が黒く塗られたマスのみからなる $2\times 2$ の部分を持たないようにしたい。高橋君が目標を達成するために、白く塗り替える必要のあるマスの個数の最小値を求めよ。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めよ。

$H, W$ の制約が非常に小さく、頑張れば全探索できそうな気もする。
「各マスを黒に塗るか白にするか順番に決めていく」という愚直な方法では $2^{HW}$ の場合があり、そのままでは TLE してしまう。
しかし、以下のような枝刈りができるので実際の探索量はそれほどでもなさそう。
- 元々白のマスを黒にすることはできない。
- 探索途中に暫定最小コストよりもコストが大きくなったら探索を打ち切る
- 黒に塗ると決め打ったときに、 $2 \times 2$ の領域ができたら探索を打ち切る
これを基に、左上のマスから色を決めていくという再帰全探索(DFS)を行うことができる。

実は答えの最大値が $9$ なので、この枝刈りが間に合いそうだということも考えることができる。

#ABC424 お疲れさまでした～
遅めの4完で微冷え

C: 有向グラフを作って、修得済みのスキルから多始点BFSをする。
D: DP苦手なので、全探索DFSを全力で枝狩りする。↓のような最大ケースでも9マス塗り替えればよい（未証明）ので、塗り替え回数が9になったら打ち切るのが強力。 pic.twitter.com/fkEwqi8uAe
— kurig (@kurig15) 2025年9月20日