Yuulis.log

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

【AtCoder】トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384） - 参加記 | 茶コーダーが解くAtCoder

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

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

A - aaaadaa

Difficulty: 11

解答時間: 1:28

長さ $N$ の英小文字からなる文字列 $S$ と英小文字 $c_1,c_2$ が与えられる。 $S$ の文字のうち $c_1$ であるもの以外を全て $c_2$ に置き換えた文字列を求めよ。
for文で $S$ の先頭から走査していき、 $S_i \neq c_1$ ならば $S_i = c_2$ とすればよい。

B - ARC Division

Difficulty: 30

解答時間: 3:12

高橋くんは、これから回の ARC に参加することにした。 ARC は以下の2つの division に分けられている。はじめ、高橋くんのレーティングはであり、回目の ARC は Div. で、高橋くんが取った成績は整数で表される。参加した ARC がレーティングの対象ならば、終了時にレーティングにが加算される。回の ARC を終えたとき、高橋くんのレーティングがいくつになっているか求めよ。
- ARC Div.1 では、コンテスト開始時のレーティングが 1600$ 以上 2799 以下の参加者がレーティング更新の対象である。
- ARC Div.2 では、コンテスト開始時のレーティングが 1200$ 以上 2399 以下の参加者がレーティング更新の対象である。
ARC 各回についてレーティング対象か判定し、その都度高橋君のレートをシミュレートしていけばよい。

C - Perfect Standings

Difficulty: 187

解答時間: 7:24

あるプログラミングコンテストは A ~ E 問題の5問からなり、それぞれの配点は $a$ 点、 $\cdots$ 、 $e$ 点である。コンテストには31人が参加し、全員が1問以上解いた。参加者は名前に含まれる文字に対応する問題をすべて解き、それ以外の問題は解かなかった。参加者の名前を、取った点数が大きいほうから順に出力せよ。ただし、同じ点数を獲得した参加者については、名前が辞書順で小さいほうを先に出力せよ。
参加者31人全員の名前と点数の計算式をプログラム中に埋め込んでしまってもいいのだが、少々時間がかかるし漏れも起きやすい。
ここで、ある集合の部分集合は bit 全探索で全列挙できることを利用すると、漏れなく参加者とその点数を列挙できる。
あとは、列挙した要素を「点数 → 名前」の順でソートしてやれば OK 。

D - Repeated Sequence

Difficulty: 666

周期 $N$ をもつ無限数列 $A$ の先頭 $N$ 項が与えられる。この数列の空でない連続する部分列のうち、和が $S$ となるものが存在するか判定せよ。
1周期分の $A$ の総和を $\mathrm{cycle}$ として、 $S \mod \mathrm{cycle}$ を改めて $S$ とする。
こうすることで、長さ $N$ 以下の $A$ の連続部分数列であって、その総和が $S$ になるものがあるかを判定すればよいことになった。
ここから $A$ の2周期分の累積和を取ればよいことが分かったのだが、その後どのような処理をすればよいか詰まってしまった。
結論としては、 $A$ の2周期分の累積和を格納した配列 $v$ に対して、 $1 \leq i \leq N$ で開始地点を選び、 $v_i + \mathrm{cycle}$ の要素が $v$ に存在するかどうかを二分探索等で判定すればよいようだ。

結果

Performance: 677

Rating: 782 → 772 (-10)

D問題みたいな、周期的な配列で累積和を取るような問題が苦手なので要復習したい。