読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

競技プログラミングを始めて1年間でやったこと

この記事は Competitive Programming Advent Calendar 2016 3日目の記事として書かれました。

競技プログラミングを始めてちょうど1年くらいになるので、今までやってきたことをまとめてみようと思います。

これから競技プログラミングを始める人の参考や、既に競技プログラミングをやっている人の昔を思い出す材料にでもなれば幸いです。

と言いつつほとんど日記なので、お正月によくある1年をまとめた特番的なアレだと思ってまったり読んでください。

これを書いているのは現在青くらいの人です(競技プログラミングyurahunaという名前でやっています)

目次

  • 振り返り(2015年12月~2016年11月)
  • 成果(レーティングとか解いた問題数とか)
  • 最後に(ポエム)

2015年12月

研究室でデータ分析のためにPythonを身に着けないといけなくなった。 本を読むだけだとつまらないので何か問題を解きながらやりたいと思って調べていたら、競技プログラミングの存在を知った。 みるみるうちに競技プログラミングにハマった。問題を解いてACがつくのが本当に楽しくて、ABCのA,B問題をひたすら埋めていた。

プログラミング経験は、工学系なので大学でC言語をやりはしたけど、情報系ではなかったし、自発的なプログラミングはほとんどしたことないという感じだった。

Twitterをやっていたので競プロ界隈の人たちをフォローした。その影響でABC(AtCoder Begineer Contest)とCodeforcesにはこの頃から出ていたらしい。あとはyukicoderもやっていた形跡がある(★1,2あたり)。

競プロerたちをフォローすると、間断なく競プロ情報が流れて来るのでいいと思う。数日間競プロをやらなくても忘れてそのままフェードアウトするようなことがない。

2016年1月

卒論を書きながらABCを埋めていた。1/19にABCのA,B問題埋めが終わり、C問題をメインに解くようになった。

twitter.com

最初は典型アルゴリズムなんて知らないので1問2時間くらい普通に考えていたのだけれど、ダイクストラやワーシャルフロイドがよく出てきたので蟻本を買って読んだ。1章はよくわからないのでほとんど飛ばしてしまった。ABCのCまでは蟻本の初級編(2章)まで読んでいれば知識としては足りたように思う。蟻本の例題は難しいので、自分で別途類題を集めて解いていた(↓こんな感じ)。

pakapa104.hatenablog.com

CodeforcesはA問題を落としまくってレートが下がる一方だった。

2016年2月

Codeforcesで1,2完が安定してとれるようになりレートがシアンになった。問題をちゃんと読むようにしたのがよかったのかもしれない。

AtCoder埋めを続けていて、2/14にはARCのA、2/16にはABCのCが埋まった。2/20にARCのBも埋まった。この辺りは並行してやっていたらしい。AtCoder Virtual Contestなる神サービスが誕生したので、ひたすら埋めたい問題をコンテストに入れて解いていた。時間制限があると途中でダレなくてよかった。Codeforcesのvirtual participationもちょこちょこ使っていた気がする。

twitter.com

ひょんなことから作問をすることになり、yukicoderで初めて出題をさせていただいた。

No.345 最小チワワ問題 - yukicoder

No.346 チワワ数え上げ問題 - yukicoder

作問には割とハマって、ひたすら問題案をひねり出してはいろんな人にテスターをしてもらっていた覚えがある。問題を作る中でアルゴリズムの新たな側面を知ることもあって面白かった。作問に関しては「AtCoderでいつか作問できるようになりたい」という気持ちがあって、これが作問についても競プロ自体についても割とモチベーションになっていた。

この頃まではPythonで解いていたが、いちいちTLEしてつらいのでC++に乗り換え始めた。

蟻本の3章を読んだのもこの辺りの時期な気がする。ただ、3章の内容はまだ自分の実力でたどり着ける位置の問題には出てこないようなものも多かったので、とりあえず一通り読んでおいて必要になったらまた勉強しようという気持ちだった。二分探索やしゃくとりは割とよく出てきたので問題を解きながら覚えられたけど、フロー周りは正直今でもまだまだ奥が深いなあ……という感じ。

本を読んでがっつり勉強したのはたぶんこれが最後で、以降はコンテストや埋めで解けなかった問題から学ぶ、必要なら蟻本に立ち返るという感じだった。なのでこれ以降は取り組み方に関してあまり言えることがない(その分イベントまとめみたいになります)

2016年3月

RUPCに行った。

pakapa104.hatenablog.com

初めてのオンサイトなのでビクビクしながら行ったが、これがとても楽しかった。競プロerとの交流やチーム戦の楽しさを知った。 ICPCの存在は知っていたが、早生れならM2でも出られるらしいということを知って興味が湧いた。この時から「ICPCに出ること」が自分の競技プログラミングをやる上での1つのモチベーションになったように思う。

オンサイトに行くと楽しいし、モチベーションが爆上がりする。さらにオンサイトで解いた問題は記憶によく残るので勉強のためにもオススメ。

埋めの方はと言うと、LCM-Rushに心を折られながらABCのDを埋めた。ARCのCは半分くらい埋めたけど残りはしんどくて、AtCoder Virtual Contestで解ける適性難易度の問題が見つけづらくなってきた。そんな中YazatenさんにAOJ-ICPCを薦められて解き始めた。Yazatenさんとのdiffを埋めるという名目でやっていたのだけれど、これは結構モチベーションが湧くのでオススメ。適当に実力が少し上くらいの人を見つけて、適正難易度から埋めていくといいと思う。他のコンテストよりも実装重視の問題が多く、実装力の面でだいぶ鍛えられた気がする。

2016年4月

大学を卒業し、進路変更のためにニートをしていた。ニートなので競技プログラミングに打ち込んだ。

ICPCの、JAGによる模擬国内Aがあった。チームメンバーを募集していたらなぜかuwiさんと組ませていただけることになり2人チーム(tempura)で参加した。僕はA,Bを解いたがCの構文解析が永遠に組めず冷え。壁を感じた。一方uwiさんは後ろの方の問題をバンバン通していてすごかった。

この頃から競プロ界隈(で僕が観測している範囲)ではTypingWar(対戦型タイピングゲーム)が流行り始めたらしい。

作問ブームはまだ続いていて、yukicoderで2回目の出題をさせていただいた。

yukicoder contest 136 - yukicoder

★1で出した問題が★2になったりしかも既出だったりして冷えたが、問題を作って人から反応がもらえるのはやはり楽しかった。ますます作問にハマった。特にbtkさんにはテスターとしてかなりお付き合いいただいた(この成果は半年後に日の目を見ることになる)。

2016年5月

Codeforcesのレートがブルーになった。Div2Cが2回に1回くらいは解けるようになったらしい。

Google Code Jamの予選があった。 Round1Cで確か1000位以内に入るとTシャツがもらえたのだが、1063位で悔しかった思い出がある。 と同時に、今年1063位だったなら来年はもらえるだろうという気持ちもあった。 GCJの問題は解いていて面白かったので、来年はもっと上に行きたい。

ICPCのWorld Finalがあり、Twitterに流れてくる写真を眺めながらなんだこの楽しそうな世界は、と思っていた。

2016年6月

大学院入試の勉強の傍ら競プロをしていた。

JAGによる模擬国内Bがあり、チームMusyoku(1人)で参加した。4完できたので、自力2完だった模擬国内Aに比べると成長が感じられる。C,Dを1人で実装しきれたのはAOJ-ICPCを解いていたおかげかもしれない。

ICPC国内予選の本番もあり、観戦勢としては進学先(予定)のNAISTのチームが通ってくれてうれしかった。

2016年7月

院試が終わったのでまた競プロ漬けの日々が始まった。

AtCoderが新しくなり、AGC001が行われた。良問すぎて震えた。C問題が木の直径と中心に関する問題だったのだけれど、このあたりの話がよくわからなくて2週間くらいずっと考えていた記憶がある(ネットで見つけた英語のpdfとにらめっこしていた)

2016年8月

ICFPCに参加した。

pakapa104.hatenablog.com

主にソルバーを担当していたが、長いコードを書いたことがないので実装が進まなかった。

このときチームを組んでいたshora_kujira16さんがビジュアライザとかをパパッと作っていたのに影響されて競プロ以外のプログラミングにも手を出していたが、あまり続かなかった。僕は「プログラミングに興味はあるけど特に作りたいものはない」人だったので、競プロ向きだったんだと思う。

この頃semiexpさんがSlitherlink Playerを作っていた影響でペンシルパズルにドはまりし、競プロがおろそかになりかけた。

2016年9月

JAG夏合宿と会津合宿に参加した。めっちゃ楽しかった。

pakapa104.hatenablog.com

pakapa104.hatenablog.com

この頃は人と会うたびに「次はこどふぇすで会いましょう!」と言っていた(行けるといいなという気持ちも込めて)。

Twitterで話したことがある人とは割と話せたので、オンサイトでいろんな人と話すには普段からTwitterで仲良くしておくのがいいと思った。

会津合宿の直前にやっとフローに再挑戦した(2月のところに蟻本の3章を読んだと書いたが、そのときにはあまりよくわかっていなかったのと、解ける問題を増やしたいという気持ちがあった)。結局会津合宿で出たフローの問題は解けなかったが、復習はできたのでよかった。ざっくりとでもアルゴリズムを知っておくことは、学ぶ機会を活かすために必要だと思う。

2016年10月

KUPCに行った。5時間ソロのオンサイトなので座るだけにならないか心配だったが、最後まで楽しませてもらえた。Eがなかなか嘘をつかせる問題で、解説でカットと聞いてなぜ気づかなかったのかと悔しくなった。

大学院に入学した。新入生向けのガイダンスでICPCの黒いTシャツを着ている留学生がいて、話かけたりした(来年一緒にチームで出られるかと思ったけどそれは無理みたいで残念だった)。

入学前からNAISTの人たちとコンテストを主催したいという話をしていたのだけれど、そのプロジェクトがこの頃から発足した。ひたすら問題を作っていた。

2016年11月

引き続きNAISTコンテスト(仮)に向けて作問をしていた。講義が意外と忙しかったのであまり過去問演習はしていなくて、せめてと思いAtCoderのコンテストには毎週出るようにしていた。

CODE FESTIVALに行った。めっちゃ楽しかった(イベントについてこれしか言ってない気がする)

pakapa104.hatenablog.com

という感じで、最後の方ほとんど箇条書きでしたが振り返り終了です。

成果

1年やった結果をまとめてみます。(レーティング、AC数は2016/12/1現在のものです)

AtCoder

f:id:pakapa104:20161201220515p:plain https://atcoder.jp/user/yurahuna

f:id:pakapa104:20161201220528p:plain http://kenkoooo.com/atcoder/?kind=user&name=yurahuna

レーティングはAGC001以降のやつ。青の上の方という感じ。こどふぇすで落としたのがもったいなかった。

問題数でいうと553問解いた。来年中にARCも全部埋めたい。

Codeforces

f:id:pakapa104:20161201220537p:plain http://codeforces.com/profile/yurahuna

これも青の上の方という感じ。来年はdiv2 3,4完を安定させてdiv1に行きたい。

AC数をhadroriさんの修行で確認したところ、104問だった。

topcoder

f:id:pakapa104:20161201221126p:plain https://www.topcoder.com/members/yurahuna_/details/?track=DATA_SCIENCE&subTrack=SRM

topcoderはつらくてあまり出ていないが、最近はkoyumeishiさんのSRM埋めをやっている。来年は黄色にしたい。

yukicoder

f:id:pakapa104:20161201221243p:plain 🍡yurahuna - yukicoder

yukicoderはアルゴリズムを初めて勉強したときにタグ埋め(ここからタグごとのページに飛べる)でお世話になった。226問解いたらしい。

AOJ

f:id:pakapa104:20161201221619p:plain http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=yurahuna#1

f:id:pakapa104:20161201221744p:plain http://aoj-icpc.ichyo.jp/?aoj_rivals=&sort2_order=desc&year_max=&source4=1&aoj_username=yurahuna&point_max=1200&sort1_order=asc&source2=1&source3=1&source1=1&point_min=100&sort2_by=num_aoj_acceptances&year_min=&sort1_by=point

AOJ-ICPCがメイン。気まぐれでJOI非公式難易度表(5,6あたり)も埋めたりした。AOJ-ICPCは10月頃にそろそろ50000ポイント行けそうと思って埋めまくっていたんだけど、途中で力尽きてやめた。青と黄色の壁が高いので、来年は黄色レベルをしっかり解けるようになりたい。


上記でAC数がわからなかったtopcoder以外のすべてを足すと、553+104+226+244=1127問ICPCの問題がAtCoderとAOJで被っているのを差し引いても1000問は解いたらしい(今となってはやるだけな問題も多いですが)。

最後に

最後なのでポエムを書きます。

僕は割と飽きっぽい性格で、何をやっても続かないことが多かったです。そんな中、競技プログラミングを1年間続けてやってこられたというのは結構驚くべきことです。なぜ競プロを続けてこられたのかと言うと、競プロ自体が面白いのはもちろんなのですが、大きいのは競プロerとのつながりだと思います。Twitterでもオンサイトでも競プロ界の人々、競プロerのコミュニティが大好きでいつまでもここに居たくなってしまいます。競プロをやっていると「なぜこんなに苦しいのに競プロをしているのか…」という気分になることもあるのですが、そんなときは「競プロerたちとのつながりを失いたくない」というのが歯止めになってくれていたように思います。

1年を通して、大きなモチベーションの源になっていたのもオンサイトのイベントでした。RUPCやKUPCなどの各大学による競プロ合宿、CODE FESTIVAL、あるいは競プロer同士のオフ会などです。

そんなこんなで、種々のイベントには今後も積極的に顔を出そうと思っているのでどうぞよろしくお願いします。

来年(今年がまだ1ヶ月あるけど)は、黄色になることと、ICPC国内予選突破を目標に頑張りたいと思います。


Competitive Programming Advent Calendar 2016、明日の4日目はchokudaiさんの「競技プログラマは競プロのコンテストを開いてる会社に就職しろ!って記事」と54k3yさんの「競プロで使いたい✨文字列アルゴリズム達🎀💕」です。