ICPC_国内予選_2018
前置き
書く流れな予感がしたので書きました。ささっと書いていきます。書き手はtwitter id: @25__toma (アンダースコアは2個)です。よろしくお願いします。書いて良いか分からない笑い話は半分以上カットして、流れを主に記述してます。
前日談
ICPC参加チームは、何というかTwitterで話すなどしていたら、気が付いたら決まってました。「チームどうしよう～～。 え、もう決まってるんですか？分かりました～」くらいな感じでした（話しやすい方とでしたのでそのまま続行）。先に話しておくと私がチーム内最年少なので、チームメイトは先輩です。
主に戦略としては、先輩方がA,B問題を1問ずつ解いて、その後D以降を考察している間に、私がプリンター係兼C問題担当という感じでした。
本番直前は、
ある人は直前までの授業を真面目に受けながら、
ある人は「フビライ・ハン」と 「エビフライゴハン」の編集距離が3であるという衝撃の事実に打ち震えながら、
ある人は「フビライ・ハン」「エビフライゴハン」などを絵にかきながら、
ある人はそれをよそにボイスロイドの音楽を2時間ぶっ通しで聞きながら、
ある人はYoutubeで謎の踊りを見てそれの真似をして踊りながら、
各々自由な時間を過ごしていました。
後そのとき、私はチームメンバーの一人の学年を勘違いしていたことが判明したりしました。
本番
C 問 題 が 分 か ら な い
10分程読みましたが、頭が真っ白になりました。
C担当の役割を他の人にぶん投げました。
A問題を通した先輩が拾いました。
捨てました。
B問題を通した先輩が拾いました。
何か上手くやってくれました。
その裏で、「え、本番で自分だけ0完マジ？」とか思いながらD問題を見ていました。
その時の様子を以下時系列順に（脚色あり）
見て数分「勝敗数が同じ・・・。チーム数が5つなら、全チームが2勝2敗？」
更に数分「全探索したらどれくらい重いんだろ…10^10とか？」
更に数分「ある1チームの対戦相手はN-1。だったら、試合を1回もしていない場合、勝利を分配する場合の数は(N-1)C{(N-1)/2}で良いよね」
数分後「は？？？この方法での全探索、O(10^6~7)ってマジ？？？優勝じゃん」
先輩「combinationで全探索ってマ？DFSやろ」
私「や・ら・せ・て」
先輩「あ・はい」
後はそこから、ペーパーコーディングしたコードを写経して、先輩の持ってた紙ライブラリにあったnext_permutationならぬnext_combinationという関数を写経して、手動マージして、境界値例外を付け足したら通りました。心臓に悪いですよ本当。
その時点で開始約1時間半、ABCD4完でした。
EFGHを説明してもらいましたが、最終的にはチーム全員でEを解くことに。
なんやかんやでE問題は誤差の原因究明が上手く行かなくてアでした。
その後
E問題は解けませんでしたが、アジアには出場できました。ありがとうございました。
E問題どうやって解くんでしょうねぇ本当。
競プロ勉強法分類（偏見）
注意
酔った勢いで書いた文章みたいなものなので、雑に呼んでもらえると助かります。
異論は大量に出るかと思いますが、程度によってはこの記事は削除します。
前置き
ふと昼食のとき、競プロの勉強法に関して話題が上がった。
そこで思ったのが、競馬の用語を流用できそうだということだった
（最近Twitterに画像が流れたりする、あのウマ娘のイメージでも良いかも）。
そこで、30分程度で直感的に思う、競プロの勉強法の分類をテキスト形式で書いた。
実例は失礼に当たらない程度に、原文から削除して、以下にコピペしようと思う。
競プロ能力の伸ばし方の種類（イメージ）
早熟型
主に、「過去問を色々見て、解けそうな問題をどんどん解いていく」という方針を取るとなりやすい。
基本的に成績がlog関数に近似できる。天井は水色くらい。
天井に近づいたら、普通型に移行が必須。
メリットは、早い成績反映によるモチベ維持。
デメリットは、頭打ちの速さ。
実例は僕自身。
普通型
主に、「過去問を順番に解いていく」という方針を取るとなりやすい。
基本的に成績が一次関数に近似される。天井は黄色直前くらい。
メリットは、早熟型に比べれば伸びること。
デメリットは、あまり伸びないことによるモチベの減少。
実例は、ツイッタラーに多いはず。
（社会レベルでの能力上位になりたい場合におすすめ）
晩成型
主に、「難しい問題をじっくり考察する」という方針を取るとなりやすい。
基本的に成績がシグモイド関数に近似される。天井は特にない。
メリットは、成績の無限の伸び幅。
デメリットは、競プロやアルゴリズムの本質に気づけるまでは伸びが難しいこと。
実例は、けんちょんさんやchokudaiさん。
（世界レベルでの能力上位になりたい場合におすすめ）
あとがき
競プロで有名な人は大体晩成型の人の為、
基本的に競プロの練習方法はその人たちが聞かれやすく、
そのために晩成型の勉強法が広まりやすいイメージがある。
ただコストが大きく変わってしまうため、
求めるレベルに応じて、勉強法を検討されたい。
（そろそろ僕は普通型に移行したい・・・）
AtCoderの水色を、プログラミング初めて1年で取った私のやり方
前書き
この記事は、ゲームが大好きな私が「プログラミング知識ゼロから」たった1年でAtCoderで水色を取れたことを振り返り、その時のやり方などをまとめたものです。主に、プログラミングを始めて日が浅い人向けの文章や具体例を用いているつもりです。誰かの今後の方針のきっかけになれば幸いです。
ただ、かなり思想的なお話になり、アルゴリズム方面が無いことはご了承ください。
注意事項
水色になるまでにやらなかったこと、知らなかったことは全部省いています。あくまで、やったことを中心に綴るスタイルで行きます。
軽い自己紹介
2525toaといいます。twitterIDも同じです。はてなブログでは数字を先頭に出来ないのでtoa25にしました。
水色になった時点では、競技プログラミング(Python)と、ゲームプログラミング(C++)をしていました。後は、大学の宿題に追われて連日しくしく泣いたりしています。
本題
凡そ時系列順に、やったことを並べていきます。
きっかけ
私がプログラミングを始めたきっかけを少し。
高校まではプログラミングはしていませんでした。ニコニコ動画は見てました。
大学入学後、大学のサークル漁りをしていたときに、何となく好みの看板キャラクターを見つけて、チラッと覗いたサークルがありました。そのサークル内にプログラミングをしている部門があったので混ざっていきました。
ゲームプログラミング
1.やったこと
私はゲームが大好きです。そのため、ゲームを中心にプログラミングを始めていきました。その時に使ったサイトの代表例は以下の通りです。ゲーム好きの方は、是非目を通してみてください。
ちなみに私は、水色になるまでに以下のようなゲームを作っていました。
(この年、引越し2回あったり、サークル4つ兼サーして忙しかったんですorz)
- ブロック崩し(コピペ)
- 2Dダンジョンゲーム
- シューティングゲーム*2(片方コピペ)
2.やってみて分かったこと
単刀直入に言います。
「好きなものを中心にプログラミングを始める」
私はこれが一番大切だと思います（異論は認めるし、否定はしない）。
理由は凄く単純で、挫折しにくい気がするからです（要出典）。
挫折しにくいと沢山良いことがあるのですが、一つ上げるならば、
場数を特に多く踏める ⇒ 経験値が早く溜まる(RPG脳)
でしょうか。これに関する理由を聞きたい方は少ないと踏んで、これ以上は省略します。とりあえず好きなものがあれば、それを中心にプログラミングを始めてみてはどうでしょうか。
競技プログラミング
1.やったこと
私が競技プログラミングを始めた理由は、pythonの深層学習に興味を持っていたからでした。コミュ障なので、対話botを作ろうとしていました。プログラミングを始めて5ヶ月ぐらいのときのことです。
使用サイトはpaizaでした。ブラウザ上でプログラミングが容易に出来る点、入出力テンプレートが自動表示な点で選択しました。時々イベントで、ゲームっぽく解けるときもあるのが楽しかったです。イベント合わせて、凡そ50~60問解いていました。7割前後がC,Dランクでした。
時々、CheckiOも十数問程度解いていました。
最終的に、AtCoderを知ったのは、プログラミングを始めて10ヶ月ぐらいのときでした。水色になるまでに30問近く解いていました。
2.分かったこと
大体自分が競プロで問題を解いて行って、どういう流れが好きかが分かったので以下に載せます。
- 最初は、今の自分で解けるものを解く。
自分の現状の実力を把握することを目的とする
（おまけで精進が出来るくらいの気分）。 - プログラミングの世界のイメージを少しでも理解できるようになると強い
（数学ガールの恐らく1作目の、2つの世界の行き来の話を参考）。 - 次に面白そうな問題を解く。
マンネリ化を防ぐため。たまにぶつかる難しい問題で強くもなれる。 - 最後に、一般に言われる精進の方法を参考にしていく。
おまけ.競プロが続けられた理由
- 研鑽する仲間を作りやすい（Twitterで顕著）
- 頻繁にコンテストがあり、例えばテスト直前にしか勉強しない人でも、精進がしやすい
- コンテストは基本2時間前後なので、メリハリをつけやすく、闘争本能をくすぐられる(そしてACが出る)
- プログラミングに娯楽の側面を生み出してくれる
- 楽しいことに理由は不要
まとめ
一般論は大事だし、能力は上がりやすいのかもしれない。
他の人の方法論を学んだり、講座を受けたりすれば、強くなれるかもしれない。
ただそれは、続けられなければ、そもそも話にはならない。
そこで、一つの提案として
好きなもの中心のプログラミング
を出します。
今、私は、競技プログラミングが好きです。だから続けます。
AtCoderの水色を1年で取ったわけですが、それは結局の所、
好きなものでプログラミングをしたから、能力を高められた結果だと思っています。
これからプログラミングをする人は、好きなもの、ことを沢山見つめて欲しいです。
この記事が、私達の転換点となりますように。
