こんにちは、yukad2です。
この記事では私がAtCoderでRating:400になるまでに勉強したことをまとめています。
0.初めてのコンテスト前
中学生の頃にC++ゲームプログラミングに挑戦しましたが、if, forが理解できる程度の知識でした。
大学1年で学習したRubyが(Cと比べて)非常に書きやすかったので、プログラミングの練習も兼ねて競技プログラミングを始めました。
- chokudaiさんの記事を読んで、就活まで(2年以内)に緑～水色を目標にしました。
- コードテストで入出力の確認をしました。
- 過去問を何度か解きました。
1. コンテスト
- 1回目
- 3完 Perf:681
- 2回目
- 2完 Perf:244
- 3回目
- 2完 Perf:196
全然できない、と焦りを感じて過去問でアルゴリズムとデータ構造の基礎を勉強しました。
2. 勉強したこと
for 2重 3重
h = 3; w = 3;
arr=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
h.times{|i|
w.times{|j|
puts arr[i][j]
}
}
勉強したわけはないですが、必須なので。RubyなのでArray#eachの方をよく使っていました。
bit全探索
RubyではArray#combinationを使って実装しました。ベンチマークは取っていませんがABCの300点相当だとそこまで時間がキツイ問題は無いと思うので...
n = 5
arr=[1, 2, 3, 4, 5]
(n+1).times{|i|
arr.combination(i){|item|
p item
}
}
最大公約数(GCD)
a = 3
b = 6
p 3.gcd(6)
最大公約数を求めるメソッドが標準にあります。(2020/11/21 追記)
約数列挙
n = 30
ans = []
(1..Math.sqrt(n).to_i).each{|i|
if n % i == 0
ans << i
ans << n / i
end
}
p ans.uniq.sort
$O(log(n))$
上記のコードは$\sqrt n$が整数の場合は$\sqrt n$が重複するので注意が必要です。（uniqで重複を消して出力）
Hash(連想配列)
all = Hash.new
all["hoge"] = 1
all["huga"] = 3
p all
知らなかったので全く戦えなかった問題がありました。
その他過去問
6問になってからのC問題を確実に解けるように練習しました。
過去問を解く際に、AtCoderProblemsを参考に上から順番に解いてました。
AtCoder Problems
3. 結果
9回目のコンテストで茶色になりました。間のブランクは大学とバイトが忙しすぎてほとんど問題は解いていなかったです。
次は緑目指してガンバリマス！
