Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】ユニークビジョンプログラミングコンテスト2025 春（AtCoder Beginner Contest 398） - 参加記 | 緑コーダーが解くAtCoder

AtCoder-ABC-コンテストまとめ AtCoder-ABC AtCoder ABC コンテストまとめ競技プログラミング

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

A - Doors in the Center

Difficulty: ???

解答時間: 3:46

以下の条件を全て満たす長さの文字列を求めよ。
- 各文字は-または=である。
- 回文である。
- 文字列中に=は $1$ 個または $2$ 個含まれる。 $2$ 個含まれる場合、それらの=は隣接している。

の偶奇で場合分け。
- $N$ が偶数なら、 $\frac{N}{2}$ 個の-と、 $2$ 個の==と、 $\frac{N}{2}$ 個の-をこの順に出力すればよい。
- $N$ が奇数なら、 $\lfloor \frac{N}{2} \rfloor$ 個の-と、 $1$ 個の=と、 $\lfloor \frac{N}{2} \rfloor$ 個の-をこの順に出力すればよい。

B - Full House 3

Difficulty: ???

解答時間: 3:30

$7$ 枚のカードがあり、 $i$ 番目のカードには整数 $A_i$ が書かれている。これらのカードから $5$ 枚を選び、フルハウスとできるか判定せよ。

各カードの枚数をmapを使って管理する(keyはカードの数、valueは枚数)。
$i, j = 1, 2, \cdots, 13$ に対して全探索を行い、 $\mathrm{map}_i \geq 3$ かつ $\mathrm{map}_j \geq 2 \: (i \neq j)$ なる [(i, j)] の組が存在すればYes、そうでなければNo。
想定解 bit 全探索なのマジか...
過去の Full House :
- ABC 263 A
- ABC 386 A

C - Uniqueness

Difficulty: ???

解答時間: 10:32

$1$ から $N$ の番号がついた $N$ 人の人がいて、人 $i$ は数 $A_i$ を持っている。「自分と同じ数を持っている人が自分以外に存在しない」という条件を満たす人のうち、持っている数が最大である人の番号を求めよ。

ある数を持っている人の人数をmapを使って管理する(keyは数、valueは人数)。
$i = 1, 2, \cdots, N$ について、 $\mathrm{map}_{A_i} = 1$ であるならば、数 $A_i$ を持つ人は条件を満たす。
あとはこの $A_i$ を最大化すればよい。

D - Bonfire

Difficulty: ???

解答時間: 37:15

2次元グリッドの座標に焚き火があり、時刻ではマスにのみ煙が存在する。 N, W, S, Eからなる長さの文字列が与えられ、時刻では、以下の現象が順に発生する。
- 風が吹いて現時点で存在する全ての煙が風下側に移動する。
- マス $(0,0)$ に煙が存在しない場合、新たな煙がマス $(0,0)$ に生成される。
高橋君はマス $(R,C)$ に立っている。整数 $1 \le t \le N$ について、時刻 $t+0.5$ においてマス $(R,C)$ に煙が存在するか判定せよ。

南北方向と東西方向のそれぞれの移動量の累積和( $\mathrm{dr}, \: \mathrm{dc}$ とした)を時刻ごとに計算しておく。
二次元ハッシュマップを用意して、 $(\mathrm{dr}_i, \mathrm{dc}_i) = i$ を格納する(時刻 $i$ に煙が生成されることに対応)。
「時刻 $t$ に $R, C$ に煙がある」ということは、「 $(\mathrm{dr}_t - R, \mathrm{dc}_i - C) \leq t$ である $(\mathrm{dr}_t - R, \mathrm{dc}_i - C)$ が存在する」ことに等しい。
「とびだせどうぶつの森」の南の島で遊べる「バルーンハントツアー」のシミュレーションをしたときに、似たような処理をしたことがある気がする。分かる人いるかなぁ...
想定解みたいに、焚き火と高橋君を動かした方が圧倒的にラク。

結果

Performance: 901

987 → 978 (-9)

E問題で珍しくインタラクティブ問題が出たみたい。

E : 奇閉路を持たないグラフは二部グラフ
F : Manacher のアルゴリズム

どちらも知らなかったので精進します。