# 半年間競プロをやってみた ---- ## 自己紹介 * 藤田 悦誌(@wotsushi) * インフラエンジニア＠某SIer * 激辛料理が好き <img src="https://i.imgur.com/AYDytm8.png" width="400"> ---- ## 半年間競プロをやってよかったと感じたことを話します ---- ## 競プロとは 以下を競うプログラミングコンテスト * 複雑な処理を正しく記述する力 * 計算時間のかかる処理を数学的／情報科学的に高速化する力 <img src="https://i.imgur.com/8s9iO6E.png" width="300"> <img src="https://i.imgur.com/ETLEXdp.png" width="300"> ---- ## 問題例 * N体のモンスターがいます。それぞれ **体力** と **攻撃力** というパラメータを持っています * モンスター同士のバトルは1:1で行われ、以下の手順で勝敗が決まります 1. お互い同時に相手を攻撃する。相手の体力は自分の攻撃力分だけダウン 2. お互い体力0以下の場合、引き分け 3. 片方だけ体力0以下の場合、もう片方の勝利 4. お互い体力が0より大きい場合、1に戻る * 他のどのモンスターとバトルしても勝利できるモンスターがいれば、それを求めてください ---- ## 問題例の例 |モンスター|体力|攻撃力| |--|--|--| |ドラゴン|7|3| |スライム|9|2| |ゾンビ|2|5| ---- ## ドラゴン VS. スライム ターン0 |モンスター|体力|攻撃力| |--|--|--| |ドラゴン|7|3| |スライム|9|2| ---- ## ドラゴン VS. スライム ターン1 |モンスター|体力|攻撃力| |--|--|--| |ドラゴン|7->5|3| |スライム|9->6|2| ---- ## ドラゴン VS. スライム ターン2 |モンスター|体力|攻撃力| |--|--|--| |ドラゴン|5->3|3| |スライム|6->3|2| ---- ## ドラゴン VS. スライム ターン3 |モンスター|体力|攻撃力| |--|--|--| |ドラゴン|3->1|3| |スライム|3->0|2| ドラゴンの勝ち！ ---- ## ドラゴン VS. ゾンビ ターン0 |モンスター|体力|攻撃力| |--|--|--| |ドラゴン|7|3| |ゾンビ|2|5| ---- ## ドラゴン VS. ゾンビ ターン1 |モンスター|体力|攻撃力| |--|--|--| |ドラゴン|7 -> 2|3| |ゾンビ|2 -> -1|5| ドラゴンの勝ち！ ドラゴンはスライムにもゾンビにも勝てるので、 **答: ドラゴン** ---- ## どうやって解く？ * 素直に総当たりする * バトル数は N (=モンスター数) の2乗に比例 * 例えば N が100万だと3時間くらいかかる... * 適当にトーナメントし、優勝者とその他全員とバトルさせる * トーナメントのバトル数はN未満 * 優勝者とその他とのバトル数もN未満 * 合計で2N未満のバトル数で答えを求められる * 例えば N が 100万でも5秒もかからない！ ---- ## 競プロをやってよかったこと * 毎日コードを書くようになった * 強い人と知り合えた * 自信を持てるようになった ---- ## 毎日コードを書くようになった * 一問が小規模なので、気軽に取り組める * Streakを伸ばすのが楽しい <img src="https://i.imgur.com/ZUb8H8S.png" width="700"> ---- ## 強い人と知り合えた * 強い人の解法・思考過程・マインドを見るのは（競プロに限らず）勉強になる * 競プロerが集うイベントでCSにとても強い学生や社会人と話すのはいい刺激になる！ ---- ## 自信を持てるようになった * レーティング上昇に応じて、自分の実装力を自信を持ってアピールできるようになった * 同時に、自分より強い人もまだまだいることが分かった <img src="https://i.imgur.com/UdOBJX7.png" width="500"> <img src="https://i.imgur.com/LGixpZQ.png" width="400"> ---- ## その他 * 競プロを通して新しい言語(Rust)に入門した * 競プロで新しい言語を習得するのはアリかも！？ * 標準ライブラリの勉強になる * 週一回、会社の同僚と身内コンテストを開催して布教 * 朝練 * 頭の体操としてもいい感じ ---- ## まとめ * 競技プログラミングは面白い（とくに数学やパズル好きにオススメ） * コードを継続的に書くきっかけになる * 自分の強さを客観的に測れる ---- ## ご清聴ありがとうございました