Yuulis.log

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

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

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

コンテスト時間: 2025-09-07(日) 13:10 ~ 2025-09-07(日) 14:50 (100分)

A - Stage Clear

Difficulty: ??? / NoviSteps: ???

解答時間: 2:51

あるゲームにはワールドがつあり、それぞれのワールドにはステージがつずつある。最初のステージは個目のワールドにある個目のステージであり、個目のワールドにある個目のステージの次のステージは、以下のように定まる。
- $j\lt8$ のとき、次のステージは $i$ 個目のワールドにある $j+1$ 個目のステージである。
- $i\lt8,j=8$ のとき、次のステージは $i+1$ 個目のワールドにある $1$ 個目のステージである。
- $i=8,j=8$ のとき、次のステージはない。
- $i$ 個目のワールドにある $j$ 個目のステージの名前は $i$ - $j$ である。高橋くんが現在遊んでいるステージのステージ名 $S$ が与えられるので、次のステージのステージ名を出力せよ。

ステージ名の規則はマリオと同じ。
$i = S_1, \, j = S_3$ として、あとは規則通りに計算していくだけ。

B - Looped Rope

Difficulty: ??? / NoviSteps: ???

解答時間: 3:16

のマス目があり、それぞれのマスは白もしくは黒のどちらかで塗られている。マス目が以下の条件を満たすか判定せよ。
- どの黒で塗られたマスについても、上下左右で隣り合うマスのうち黒く塗られているものは $2$ つもしくは $4$ つである。

制約が小さいので、素直に全探索すれば十分。

ライフゲームの実装で無限にこれをやっているから、もはや呼吸するように書けてしまう()

C - AtCoder AAC Contest

Difficulty: ??? / NoviSteps: ???

解答時間: 7:30

高橋くんは、はじめAを $n_A$ 個、Bを [tex; n_B] 個、Cを $n_C$ 個持っている。高橋くんは、Aを1つ、Cを1つ、さらに任意の1つの文字を使うことで、コンテストを1つ開催することができる。高橋くんは、現在持っている文字を使ってコンテストをなるべく多く開催したい。開催できるコンテストの最大値を求めよ。 $T$ 個のテストケースが与えられるので、それぞれについて答えよ。

開催できるコンテスト回数を $t$ 回とする。
まず、コンテストを開催するごとにA, Cを1個ずつ消費しなければならないので、 $t \leq \min(A, C)$ が必要。
さらに、コンテストを1つ開催するには文字が3つ必要なので、 $t \leq \left\lfloor \frac{n_A + n_B + n_C}{3} \right\rfloor$ も必要。
これらをまとめると、 $t \leq \min(\min(A, C), \left\lfloor \frac{n_A + n_B + n_C}{3} \right\rfloor)$ となる。この $t$ の最大値が答え。

D - Least Unbalanced

Difficulty: ??? / NoviSteps: ???

を正整数として、長さの非負整数列のアンバランスさを次の操作によって得られる非負整数値として定義する :
- はじめ、 $X=0$ とする。
- 次の一連の操作を回行う。
  - $X \leftarrow \max(X, \max(A) - \min(A))$ とする。
  - $A \gets (A_1 + A_2, A_3 + A_4, \dots, A_{\vert A \vert - 1} + A_{\vert A \vert})$ とする。
- 最終的な $X$ をアンバランスさとする。
非負整数 $K$ が与えられるので、長さ $2^N$ の非負整数列であって総和が $K$ であるものの中で、アンバランスさが最小値を取る数列を構成せよ。

操作を行うごとに、数列は長さ $2^{N-1}$ の2つの数列に分割される。
前後の総和をなるべく均等にしたいので、総和を前の数列は $\left\lfloor \frac{K}{2} \right\rfloor$ 、後ろの数列はその残りで考える。
これを再帰的に長さ $1$ になるまで繰り返せば、あとは順次当てはめていくだけ。
...ここまで考察できたは良いものの、時間が足りなくてACできず。悔しい。

ぱっと見で再帰解法を思いつかなくてE, F問題へ行ってしまい、そこで時間を食った形に。

E - Colinear

Difficulty: ??? / NoviSteps: ???

解答時間: 35:00 + WA x2

2次元平面上に $N$ 個(奇数)の点があり、 $i$ 番目の点は $(x_i, y_i)$ にあって、全ての点の座標は相異なる。 $N$ 個の点のうち過半数を通る直線が存在するかを判定して、存在すればそれを出力せよ。

求めるべき直線 $l$ が存在すると仮定するならば、 $N$ 個の点からランダムに選択した点がこの $L$ 上に存在する確率は $\frac{\frac{N+1}{2}}{N}$ 以上であり、これは $\frac{1}{2}$ を超える。
ある2点を通る直線は一意に定まるので、 $N$ 個の点からランダムに選択した2点を通る直線が題意を満たす確率は $\frac{1}{4}$ である。
ランダム選択を $100$ 回程度繰り返せば、誤答を返す確率は $\left( \frac{3}{4} \right)^{100} \approx 3.20 \times 10^{-13}$ となり、ほぼ確実にACできる。

while文を用いて実装してたら、イテレーションを回すのを忘れて無限ループに陥っており2ペナ。

結果

Performance: 1368

1154 → 1177 (+23) Highest更新！

異例の日曜日のお昼開催となったABC。参加者が少ないと Performance が上に引っ張られて良いね。

D問題解ければ入水だったのになー