sima(mu)*雑記

print(f"{雑多なこと}")

Python(とPyPy)でAtCoder黄色になりました

f:id:awaawa4423:20191111232534p:plain

この度第二回全国統一プログラミング王決定戦予選で黄色になりました!!!!!!わーい!!

のでいわゆる変色記事とか言うやつを書いてみたいと思います
別にこういう勉強法が良いよ!とかこういうことするとレートが上がるよ!みたいな有益な話はそんなないと思います
わりと日記な感じなのでごめんなさい

お前は誰

  • 東京の工業な大学のの†土木工学系†に所属している B4です
    • 土木についてあまりイメージがわかない人は講義でFORTRANをやらされる学部だと思っておけばよいです
  • プ歴(≒競プロ歴)は2年くらい
    • B1の教養科目でちょろっと触ってたけど,本格的にプログラミングを勉強し始めたと言えるのは AtCoder を知って楽しくてハマったのがきっかけ
    • メイン言語は Python3/PyPy で,極々稀に C/C++ を書いたりしてるかもしれない
  • 一応数学も書いておくと高校数学は得意な方でした(特に整数論のパズルみたいな問題が好き).大学数学は多分苦手です
    • これは人生で唯一できる自慢なのですが数学280/300で合計点では学部内首席でした (くっそまぐれ当たりなので入学後の成績は…
    • でも受験数学の範囲は出てなくて数オリとかそういうのは全く触れたことないです

最近の Rated 戦績

令和ABC以降の~700 の (AC提出時間-直前の問題のAC提出時間) でなんとなくなかけた時間表です f:id:awaawa4423:20191111232833p:plain

こうしてみてみると結構成長が感じられて面白い
400,500 がそこそこの速度で解ける = 600にちゃんと時間をかけて解けるようになった気がします.

定期的に 300 で破滅してるの面白い (JSC決勝もここには書いてないけど300で死んでいたため

持ってるライブラリ

これも良くみるので書いておく

  • グラフ

    • Dijkstra
    • WarshallFloyd
    • Kruskal
    • FordFullkerson (Dinic の理解を諦めたため
    • BellmanFord
    • トポソ
  • データ構造

    • 再帰セグ木
    • 遅延セグ木(持ってるだけで使えないけど)
    • BIT
    • BIT上をにぶたん
      • 値の追加削除がO(logN), 下からi番目の値の検索がO(logNlogN)でできるやつ(多分
      • C++でいう set(?) の下位互換です
    • 動的中央値管理
      • heapqを上下に二つ繋げたやつ、値の追加O(logN) 中央値検索O(1)
      • これいる??????
  • 数学
    • 逆元Combination
    • なんか高速な素数判定

一応作るときに意識してるのは

  • 完全理解して自分で1から書く(これは半分くらい本当だけど半分くらい嘘
  • できるだけ早くしとく≒非再帰で書く
  • 分かりやすく書く、classとか使って抽象化する
  • 自分が 使いやすくする (strをオーバーロードしてデバッグ出力を簡単にするとか

黄色まで(≒ABC) にはこれくらいでそんなに困りませんでした(当然もっとあって悪いことはない

やったこと

やったこと…何やったっけ?

  • こどふぉにはほぼほぼ出てない
    • 睡眠は大切なので
    • あと個人的にあんまり問題が好きじゃない (これは参加した回が少ないせいかもしれなです
  • その代わり日本語コンテストには出る
    • ほんまか?(割りと用事被って出てないような)
  • ぶっちゃけ最近は"競プロの"精進はしてないです.problems がこんな感じなので…せいぜいコンテストと復習くらい f:id:awaawa4423:20191111233614p:plain
  • でもコードを日常的に書く機会というのはかなり増えました

競プロ自体の精進はしてないのですが,最近の戦績 を見てみるとバイトを始めたあたりから結構成績良くなってて, コードを書くようになったってのは結構影響してるのかなって思います.
特に私自身情報系の学科じゃないので競プロ以外でコードを書く機会が少なかったので.

ぶっちゃけなんで最近レートが上がったかってABCが6問体制になったからが一番大きい気がします
600前後くらいの問題が個人的には丁度良いと感じるのですが、旧体制だとそこを解けることにそんなに恩恵がないような配点が多かった感

コンテストで意識してること

っていうのを下書きの時点で章だけ作ってたんだけど書くことありますか?っていう気持ちになっています 一応なんとなく思い浮かんだことを書いておくと

  • ABCの~500 はわりとパターン認識だと思ってる (それより上とAGCは知らない
    • 似たような問題設定見たことあるなー,きっとこういう見方をすると嬉しいんだよなみたいな思考はわりとするし,わりと使える
    • なので過去問梅は大事 (しかしそんなにやってない気がしますが
  • 制約とサンプルからエスパーする
    • 制約から計算量を逆算するとかなりヒントになるので, あと構築とかも制約を手掛かりにすることが多いです (問題の美しさ的に必要以上に大きい制約にはしないはずというメタ(?)読みができるので
    • 数え上げでサンプルの出力値を素因数分解する一般的なテク
    • サンプルエスパーは割と大事だと思ってて,問題の雰囲気とサンプルから無証明で出すのは稀によくやります
      • ペナルティは高々5分なので,5分かけて証明するより自明な反例が浮かばなければ提出してしまえばいいという思考 (これは必ずしも得ではないと思いますが

AtCoderをやってて良かったこと

ここが一番書きたかったところです

  • 楽しい
    • やっぱり競プロはネトゲなんですよね
    • 解けなかった時の悔しさもあるけど,その分上手く解けた時の脳汁がドバドバなので
  • プログラミングの楽しさを知れた
    • これがほんとにめちゃくちゃでかい
    • 競プロ楽しい!から一般的なプログラミングにはまった
    • ので,そのきっかけになった AtCoder で人生変わったは過言じゃなくわりと事実
    • 将来の進路にまで割と影響してきている (これは某土某通省のせいで土木に対する熱が冷めたのもだいぶある
  • 情報分野のバイト/インターンに繋がった
    • AtCoder jobs 様本当にありがとうございます
    • 情報系の学部じゃなくてもAtCoderで実力を評価してくれるの本当に有難い
    • 時給も良い嬉しい(最低賃金の採点バイトしてたので)
    • もっとAtCoderのレート評価してくれるとこ増えろ
  • 交遊関係は広がらない
    • コミュ症なので仕方ないですね
    • 日経コン本選行くのでこの記事を読んでる奇特な人がいたら是非話しかけて下さいお願いします!

何でPythonを使うのですか

まあ結局何で?って言われると好きだからなんですね
じゃあ何で好きかって言われると困っちゃうんですけど,まあ好きってそういうもんじゃないですか (ここJpopの歌詞っぽい

今後について

最初は青を目標にしてたのですが,いつの間にか黄色になってました. 橙なりたいと思わないわけではないのですが,橙より上は人外だと思ってます.人外になりたいですね??

でもこれより上はいわゆる高度典型と言われるものを抑える必要があると思うのでちゃんと精進しなきゃなんですね. まあとりあえずはAGCでレート配ってABCで黄色復帰する人にならないようにまずは黄色キープを目標にしていきたい

それと maspy さんのブログを読んで思ったのですがやっぱり Python で競プロやってる勢が(特に上位では)少なく,Python 勢にとって上位問題の解答/解説が多くないっていうのはあると思います
自分でも割と上の方(国内黄色↑が10人くらい)らしいので,他の競プロ Python 勢に貢献できるように記事とか解法とか残していけたらいいですね (多分めちゃくちゃ苦手な分野ですけど頑張っていきたい