AtCoderを初受験した
受験した経緯
高橋直大 様
AtCoder（競技プログラミング）の色・ランクと実力評価、問題例
http://chokudai.hatenablog.com/entry/2019/02/11/155904
の記事を読んでAtCoder、競技プログラミングの世界を知り挑戦してみたいと思いました。
受験までの取り組み
2019/9/15の朝にAtCoderの存在を知り、その夜にAtCoderに初挑戦しました！
当日の取り組みとしては、過去問であるABC140を回答し、ABCは完答、D問の途中で時間切れとなりました。
このときはまだ手応えを感じていました…。
実際に受験した
ABC141を実際に受験しました。
https://atcoder.jp/contests/abc141
A問、B問は問題なく解答できました。
ただC問で大きくつまずきました。
C問
https://atcoder.jp/contests/abc141/tasks/abc141_c
実行時間制限: 2 sec / メモリ制限: 1024 MB
問題文
高橋君は早押しクイズの大会を開くことにしました。スコアボードの作成を任されたキザハシ君は、次のルールを持つ> ラウンドのポイントを管理するプログラムを書くのに苦戦しています。
このラウンドの参加者はN人であり、1からNまでの番号がついています。
ラウンド開始時点では全員がKポイントを持っています。
誰かが問題に正解すると、その人以外のN−1人のポイントが1減ります。これ以外によるポイントの変動はありません。
ラウンド終了時にポイントが0以下の参加者は敗退し、残りの参加者が勝ち抜けます。
このラウンドではQ回の正解が出て、i番目に正解したのは参加者Aiでした。
キザハシ君の代わりに、N人の参加者のそれぞれが勝ち抜けたか敗退したかを求めるプログラムを作成してください。
制約
入力はすべて整数
2≤N≤10^5
1≤K≤10^9
1≤Q≤10^5
1≤Ai≤N(1≤i≤Q)
問題に対するアプローチ
問題文を素直に解釈してQ-K回以上正解していれば勝ち残ることができると考えました。
（これはテスト中のメモ書き）
提出したコード
/入力を受け付ける/
n, k, q = gets.to_s.split.map(&:to_i)
a = []
q.times do
a << gets.to_i
end
/putsの処理を一回にまとめれば軽くなる…？悪あがき/
putting = []
if k > q
n.times do
putting << "Yes\n"
end
elsif
/ここが元凶 10,000回×10,000回で計1億回の処理が行われている/
n.times.with_index do |i|
/countで解答者配列aに含まれているプレイヤーの登場数を計算/
if a.count(i+1) > q - k
putting << "Yes\n"
else
putting << "No\n"
end
end
end
puts putting
結果
解答自体は通ったようです。
ただTLE、実行時間制限超過で不正解になりました。
AtCoderは2秒以内での処理を制限として設けられているため、先程のような1億回の処理が発生するコードは解答として認められていません。
なんとか処理速度を改善しようと、countメソッドの処理回数を減らしたり、indexメソッドを利用したりしました。
またJavaでの書き換えに挑戦してみるなど（複数行の標準入力がわからず断念）を行いました。
ただし大幅な速度改善には至りませんでした、1億回の処理回数からしたら上記の改善は些細なものだったようです。
テスト後の取り組み
AtCoder ABC141解説 PDF
https://img.atcoder.jp/abc141/editorial.pdf
こちらの公式解説ドキュメントを参考にさせていただき再度自分でのコーディングを行いました。
改善したコード
n, k, q = gets.to_s.split.map(&:to_i)
score = []
/すべてのプレイヤーのスコアをK-Qと設定する/
n.times do
score << k - q
end
/解答者の入力を受け付けながら、解答者の点数を＋1とする/
q.times do
score[gets.to_i - 1] += 1
end
/スコアが0点を超える場合、勝ち抜きとなる/
score.each do |s|
puts s > 0 ? "Yes" : "No"
end
処理回数は最大3万回まで落ち着きました。
その結果、100msで処理を終えることができました。
今後の目標
初挑戦のAtCoderで不甲斐ない結果(300点)となってしまい非常に悔しい思いをしています。
今回の敗因は、一つの解き方にこだわってしまい、プログラム上の悪あがきで処理速度を改善しようとしたことです。
時間は多くあったため、解き方自体を変更し、N^2的解答からNの解答へのアルゴリズムの変更が必要でした。
今後も過去問等にあたり、ABCDまでは解答できるようなコーダーになりたいと思っています。
そして水色コーダーを目指したいと思います！