Yuulis.log

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

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

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

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

A - 369

Difficulty: 28

解答時間: 4:25

整数 $A, B$ が与えられるので、 $A, B, x$ を適切に並べたときに等差数列を作ることができるような整数 $x$ が何通りあるか求めよ。
状況は以下の3つの場合に分けることができる。
- $A = B$ のとき、 $x = A = B$ とするしかないので1通り。
- $|A - B| = 1 \: \mathrm{or} \: |A - B| が奇数$ のとき、 $x = 2A - B, 2B - A$ とすることができるので2通り。
- $|A - B| が偶数$ のとき、上の場合に加えて $x = \dfrac{A+B}{2}$ とすることができるので3通り。

B - Piano 3

Difficulty: 62

解答時間: 4:56

100個の鍵盤が並んだピアノがあり、左から $i$ 個目を鍵盤 $i$ とする。今から $N$ 回にわたってこのピアノの鍵盤を一つずつ押すことにする。 $i$ 回目に押す鍵盤は鍵盤 $A_i$ であり、それを押す手は $S_i =$ Lのとき左手、Rのとき右手である。演奏を始める前、両手はそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は $0$ とする。演奏中、片方の手を鍵盤 $x$ の上から鍵盤 $y$ の上へと動かすと疲労度が $|y - x|$ 増加する。演奏が終了した時点での疲労度の最小値を求めよ。
演奏開始後、「最初に $S_i =$ L, Rとなる鍵盤」の上にあらかじめそれぞれの手を置いておく。あとは指示の通りに手を移動させていくことで、疲労度を最小化できる。

C - Count Arithmetic Subarrays

Difficulty: 323

解答時間: 49:14

長さ $N$ の正整数列 $A$ が与えられるので、数列 $A_l, A_{l+1}, \cdots, A_r$ が等差数列となるような整数組 $(l, r)$ の個数を求めよ。ただし、長さ $1$ の数列も等差数列とみなす。
まず初めに $l = r$ と $r - l = 1$ の場合は常に条件を満たすことに注意して、答えに $N + (N - 1)$ を加算しておく。
続いて、2項間の差 (絶対値ではない) を配列に格納しておき、これをランレングス圧縮の要領で $(差, その差を作る項の個数) = (\mathrm{diff}, \mathrm{cnt})$ と表していく。サンプルケース3なら、 $(45, 2), (22, 3), (-14, 5)$ となる。
あとは各組み合わせについて、 $\mathrm{cnt} \lt 2$ の場合に限り答えに ${}_{\mathrm{cnt}} \mathrm{C}_{2} - (\mathrm{cnt} - 1)$ を加算していく (最後の減算は $r - l = 1$ の場合を除いたもの) 。
$\mathrm{diff}$ が同じ部分を分けて考えないと、 $A = (1, 3, 3, 3, 5, 7)$ みたいなときに落ちます (1敗) 。

結果

Performance: 446

Rating: 625 → 608 (-17)