Yuulis.log

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

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

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

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

A - Misdelivery

Difficulty: 14 / NoviSteps: ???

解答時間: 1:33

$N$ 個の部屋があり、各 $i$ 号室には $S_i$ さんが1人で住んでいる。 $X$ 号室の $Y$ さん宛に荷物を届けたいので、宛先が正しいかどうかを判定せよ。

$S_X = Y$ であるかを判定してやればよい。

B - Fibonacci Reversed

Difficulty: 55 / NoviSteps: ???

解答時間: 8:01

正整数に対し、を以下のように定義する。
- $x$ を十進表記して得られる文字列を $s_x$ 、 $s_x$ を反転して得られる文字列を $\text{rev}(s_x)$ とおくとき、 $f(x)$ の値は、 $\text{rev}(s_x)$ を整数の十進表記としてみなすことで得られる整数である。
正整数が与えられる。正整数列を以下のように定義するとき、の値を求めよ。
- $a_1 = X$
- $a_2 = Y$
- $a_i = f(a_{i-1}＋a_{i-2}) \quad (i\geq 3)$

をどのように実装するかがポイント。C++ では以下のように実現できる。
- まず $x$ をto_stringで文字列に変換し、reverseで反転。
- その後、stollでlong long型として返す。
long long型を使わないと、サンプルケース3のような場合にオーバーフローする(1敗)。

C - Alternated

Difficulty: 378 / NoviSteps: ???

解答時間: 17:00 + WA x1

長さ [tex 2N] の文字列 $S$ が与えられる。 $S$ はA, Bを $N$ 個ずつ含む。 $S$ に対して隣り合う文字を入れ替える操作を0回以上行って、同じ文字が隣り合う箇所がない状態にするために、必要な操作回数の最小値を求めよ。

重要な考察として、最終的な文字列 $T$ の状態はABAB ... ABかBABA ... BAの2パターンしかない。
したがって、 $S$ の先頭から $i$ 番目にあったAは、 $T$ でも先頭から $i$ 番目の位置にあるはずである。
こうするための最小操作回数はABAB ... ABなら $\displaystyle \sum_{i=0}^{N-1} |A_i - 2i|$ 、BABA ... BAなら $\displaystyle \sum_{i=0}^{N-1} |A_i - (2i + 1)|$ で求められるので、これらの小さい方を答えとすればよい。
...と思っていたんだが、なぜかこれだと WA 。なんかバグらせてた...？
本番中は、Bの方の操作回数も計算してその平均を取ることにしたらなんか通った。謎。

D - RLE Moving

Difficulty: 1321 / NoviSteps: ???

解答時間: 57:22

無限に広いグリッドがあり、最初、高橋君はマス $(R_t,C_t)$ に、青木君はマス $(R_a,C_a)$ にいる。二人はそれぞれU, D, L, Rからなる長さ $N$ の文字列 $S,T$ に従って $N$ 回移動をそれぞれ同時に行う。 $N$ 回の移動の中で、移動直後に高橋君と青木君が同じマスにいた回数を求めよ。ただし、 $S, T$ はランレングス圧縮された形で与えられる。

二人の位置の相対座標を管理することにする。この座標が $(0, 0)$ であるとき、二人は同じマスにいることになる。
移動はランレングス圧縮された形で指示されるので、二人の連続部分が重なっている間は、相対座標の変化量も一定になる。
この間に相対座標が $0$ になるかどうかを、連立方程式を解いて判定することができる。
ただし、変化量に $0$ の成分が含まれている場合はその都度場合分けが必要なので、かなり実装が重い。

結果

Performance: 1356

1129 → 1154 (+25) Highest更新！

D問題が解かれていなすぎて、かなり Performance が上に引っ張られてた。