Yuulis.log

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

【AtCoder】HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388) - 参加記 | 緑コーダーが解くAtCoder

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

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

A - ?UPC

Difficulty: 8

解答時間: 3:33

文字列 $S$ が与えられるので、 $S$ の1文字目とUPCをこの順に結合した文字列を出力せよ。

S[0]とUPCをこのまま続けて出力すればよい。
最近 Python を触っていたこともあって、最初S[0] + "UPC"と書いてしまった(1敗)。

B - Heavy Snake

Difficulty: 30

解答時間: 4:34

$N$ 匹のヘビがいて、 $i$ 匹目のヘビの太さは $T_i$ 、長さは $L_i$ である。ヘビの重さを太さと長さの積とするとき、 [tex 1 \leq k \leq D] を満たす各整数 $k$ について、すべてのヘビの長さが $k$ 伸びたときの最も重いヘビの重さを求めよ。

$i$ 匹目のヘビの重さは $T_i (L_i + k)$ と表されるので、各 $k$ に対して $\underset{1 \leq i \leq N}{\max} T_i (L_i + k)$ を求めればよい。

C - Various Kagamimochi

Difficulty: ???

解答時間: 6:31

$N$ 個の餅が小さい順に並んでおり、 $i$ 番目の餅の大きさは $A_i$ である。2つの餅 $A,B$ の大きさをそれぞれ $a,b$ としたとき、 $a \leq \frac{b}{2}$ であるときに限り、餅 $A$ を餅 $B$ の上に乗せて鏡餅を1つ作ることができる。 $N$ 個の餅から2つの餅を選び、一方をもう一方の上に乗せることで鏡餅を1つ作るとき、何種類の鏡餅を作ることができるか求めよ。ただし、鏡餅を構成する餅の大きさが同じでも、少なくとも一方が異なる餅であれば別の種類の鏡餅として数える。

大きさ $A_i$ の餅は、大きさ $2A_i$ 以上の餅の上に乗せることができる。餅は小さい順に並んでいることから、各 $A_i$ に対して $A_j \geq 2A_i$ となるような $j$ を二分探索により求める。その後、答えに $N - j$ を加算する。

D - Coming of Age Celebration

Difficulty: 659

解答時間: 14:04

$N$ 人の未成年の宇宙人がいる。 $i$ 人目の宇宙人は現在 $A_i$ 個の石を所持しており、ちょうど $i$ 年後に成人する。ある宇宙人が成人するとき、石を1個以上所持している成人全員が、成人する宇宙人に成人祝いとして石を1個渡すとき、 $N$ 年後に各宇宙人が所持している石の個数を求めよ。

成人時に、「自身より左の宇宙人から石をもらう」のではなく、「自身より右の宇宙人に石を渡す」と読み替えると、 $i$ 人目の宇宙人が石を渡せるのは、成人時に持っている石の数を $c_i$ とすれば、 $i+1, i+2, \cdots, i+1+c_i$ 人目である。これを1個ずつ加算していくと TLE してしまうので、 imos 法により左右端だけ加 / 減算して累積和を取ることにより一気に処理する。
問題の読み替えからの imos 法による高速化がきれいに思いつけたのは、自身の成長を感じた。想定解通りの考察ができると気持ちいい。

結果

Performance: 958

Rating: 842 → 854 (+12) Highest更新！

緑Perfを安定させていきたい。