競技プログラミングを始めた
タイトルの通り、競技プログラミングに手を出してみました。理由としては色々ありますがとりあえずでかかったのは今までプログラミングについてサボりすぎて大学の単位がやばかったことが一番なのかな、と。
ただし大学のプログラミング言語はCだけどPythonで頑張っていきたい。
理由としては、最近よく通話しているメンツのなかにこーちゃんというソ廃ガチプロがいるのですが、通話中にある問題を
https://t.co/YiKC23tcaV
— こーちゃん (@fl_cl_sk) April 27, 2019
Kagami Mochiを55byteで攻略しました
こんな短さで攻略しやがった、すげえ。これについて解説してもらった中でPython便利だなー頑張りたいなーって思ったので頑張り始めました。
(ほぼ)初体験の競技プログラミングコンテストが4/27なのでこの日を競プロ始めた人してやっていきます。目標は夏休みまでに緑レートです。(目標は大きくするタイプ)
GW中にやったこと
1, Paizaラーニングの『Python入門編』を一通り学習する
無料でPythonの基本が一通り学べます。左枠で動画を見ながら右枠でコードが打てるので今までずっと実践しながら覚えてきた自分にピッタリだった。
2, Paizaのスキルチェックでいろいろと確認していく。
ランクD～Sまで一通りそろっていて、GW中はC,D問題を使ってPythonの使い方を確認、B問題をC言語を使ってアルゴリズムの理解とかしていました。B問題解けるといい感じの時給のプログラミングバイトに応募できるらしいわね。
将来的にA,Sまで解けるようになりたいなあと。
爆発的にモチベが出て驚愕のスピードでモチベがしぼんでいくタイプの人間なのでこんな感じでモチベがあるうちにハイペースで進捗を進めていきました。
あと大学の方で競プロの授業的なものをとったのでその中で触れた問題について少しだけ。
与えられた数の約数の和を出力する、特段難しいわけではない問題だったけどめちゃくちゃてこずった。(1時間以上費やした)
というのは、競プロには必ずある制限時間がネックになってしまった。この問題だと制限時間は3秒でその中で最大200000個の数について同じ処理をしなければならない。
だいたい、1秒間で処理できる計算量は10^7個らしい。それを考えずに最初に提出したコードがこれ。
これだとfor文が2回重なってしまう+if文が中にあるのでo(n^2)となってしまい、n=2*10^5とすると余裕で10^7を上回ってしまう。
それを踏まえて修正したのがこれ
これだと計算量が減るけどまだ10^7を上回ってしまった。そこで範囲を与えられた整数の半分から平方根まで縮め、例外処理をきっちりしてACが出たのがこれ。
コード長は長くなってしまったが計算量はぐっと縮まった。こういう風に正しいだけじゃなくて速さまで求められるのも競プロの面白さなんだなと思った。めんどくさいからはてなブログでプログラミングのことについて書くのやめてQiita登録しようと決意した。
授業の最後に蟻本と呼ばれる競プロの教本を貸していただいたのでそれを使って勉強してプログラミングを人並みにできるようになって単位が欲しいなあと思いました。頑張ろう。
ht
tps://twitter.com/fl_cl_sk/status/1122016157098070017
