Yuulis.log

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

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

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

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

A - Count Takahashi

Difficulty: 10
解答時間: 1:37

文字列が $N$ 個与えられ、それぞれの文字列はTakahashiかAokiのいずれかである。Takahashiである文字列の個数を出力せよ。

各文字列について、ループとifを用いて判定していけばよい。

B - Couples

Difficulty: 27
解答時間: 5:36

$2N$ 人が横一列に並んでおり、左から $i$ 番目の人は色 $A_i$ の服を着ている。ここで、服の色は色 $1, 2, \cdots, N$ の $N$ 色であり、それぞれの色の服をちょうど2人が着ている。各 $i$ について、「色 $i$ の服を着た二人の人の間にはちょうど一人いる」という条件を満たすものは何通りあるか求めよ。

$N$ の制約が小さいので、素直に二重ループして一つずつ $i$ について見ていけばよいだろう。
$i = 1, 2, \cdots, N$ について具体的には、

$A_j = i$ となる $j$ を $j_0, j_1$ とし (制約よりこのような $j$ は必ず2つ存在する) 、 $j_1 - j_0 = 2$ ならば答えとなるカウンターを1増やす。

C - Tile Distance 2

Difficulty: 828

座標平面上に $2 \times 1$ の大きさのタイルが下図のように敷き詰められている。高橋君は、始め点 $(S_x + 0.5, S_y + 0.5)$ にいて、「上下左右の方向と正の整数 $n$ を選ぶ。その方向に $n$ だけ進む」という移動を好きなだけ繰り返す。高橋君が異なるタイルを通るたび、高橋君は通行料を $1$ 支払う。高橋君が点 $(T_x + 0.5, T_y + 0.5)$ にたどり着くために支払わなければならない通行料の最小値を求めよ。

数式で表すとなると結構複雑になる。

(問題文より引用)

まず、簡単のためスタートとゴールはタイルの左側にあるとして考えよう。仮に右側にあったとしても、同じタイルの移動ならば通行料はかからないので問題ない。この処理をした後、 $dx = |S_x - S_y|, \: dy = |S_y - T_y|$ とおく。
サンプルケース1の図をもとに色々な値で実験すると、どうやら $dx \leq dy$ ならば、通行料の最小値は $dy$ に等しくなることが分かる。一方 $dx > dy$ のときは $dy + \lfloor \dfrac{dx}{2} \rfloor$ として計算したが、なぜか WA 。

$dx > dy$ のときは、正しくは $dy + \lfloor \dfrac{dx - dy}{2} \rfloor$ であった。これは公式解説の別解の図を見ると分かりやすい。

結果

Performance: 577
Rating: 634 → 626 (-8)

B -> C が灰 -> 緑という久々の崖回であった。大事故にならずに何とか耐えた格好。