Yuulis.log

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

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

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

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

A - September

Difficulty: 11

解答時間: 1:37

英小文字からなる12個の文字列が与えられる。 $S_i$ の長さが $i$ であるような整数 $i$ の個数を求めよ。
S[i].size() == iであるならば答えのカウンターを加算。

B - 1D Keyboard

Difficulty: 54

解答時間: 9:41

26個のキーが数直線上に並んだキーボードがあり、このキーボードの配列はをABC ... Zを並べ替えた文字列 $S$ で表される。文字 $S_x$ に対応するキーが座標 $x$ にある。これから、このキーボードを使ってABC ... Zを順に入力していくことを考える。はじめ、指はAに対応するキーの座標にある。Zに対応するキーを押すまでの指の移動距離の合計として考えられる最小値を求めよ。
今指が座標 $x$ にあって、次に押す文字 $c$ に対応するキーの座標を $x_c$ とすれば、移動距離は $|x - x_c|$ で求められる。したがって、 $x_c =$ B, C, ..., Zに対してこれを足し合わせていけばよい。
$x_c$ を求めるのは普通に線形探索でよさそう。

C - Max Ai+Bj

Difficulty: 75

解答時間: 1:45

長さ $N$ の整数列 $A, B$ が与えられる。 $1 \leq i, j \leq N$ を満たす整数 $i, j$ を選んで、 $A_i + B_j$ の値を最大化せよ。
$\max A + \max B$ が答え。両者を降順ソートするなり、max_elementを使うなりで瞬殺。
本当にこれ250点もあるのか？逆に不安になったわ。

D - Hidden Weights

Difficulty: 765

頂点辺の有向グラフが与えられ、番目の有向辺は頂点からに向かっており、重みを持つ。次の条件を満たす、各頂点に整数を書き込む方法を1つ求めよ。
- 頂点 $i$ に書き込まれている値を $x_i \: (-10^{18} \leq x_i \leq 10^{18})$ とする。すべての辺 $j=1,2,\cdots,M$ について、 $x_{v_j} - x_{u_j} = w_j$ が成り立つ。
1つの連結成分に関して、ある頂点に書き込む数を $0$ として決め打てば、その連結成分のほかの頂点については芋づる式で書き込む数が決まっていく。
DFS などで頂点から探索していけばよいのだが、1方向にしか辺を張らない場合、「を満たす整数について、頂点から頂点を探索する」ときに、頂点が探索済みのため値を更新できないケースが発生する。
- 例えば、サンプルケース1で仮に頂点 $4$ から $1$ に辺が張られていたケースとか。
これがうまく解決できずにバグらせてしまったのだが、結論としては、入力時に $u_j \xrightarrow{w_j} v_j$ と $v_j \xrightarrow{-w_j} u_j$ の2方向の辺を張ればうまく DFS が機能するようになる。

結果

Performance: 629

Rating: 600 → 603 (+3)

B問題をもっと早く処理できていれば、もうちょい伸びたか...? でも今回のD問題は割と楽しめたかも。