木更津高専 Advent Calendar 2023の20日目の記事となっております
Prev ← AtCoder入茶しました by @nairoki
Next → AtCoder入緑記事 by @toma09to
はじめに
青色になりました！
昨年の12/10に緑になってからちょうど1年、今年の6/10に水になってからちょうど6ヶ月です
学んだこと
あんまり多くないと思います
最近は偶然自分の得意な問題セットに当たっているだけな気もします
以前よりも解くスピードと安定感が上がって、応用力が少しついたイメージです
例えば二分探索での判定問題とか、セグ木に何を乗せるかとかを考えるなどです
アルゴリズム等
それらを使った問題も載せておきます
二分探索
答えを決め打ち二分探索
しゃくとり法
二分探索でええやん←ダメです、しゃくとりを書けるようになりましょう
セグメント木
モノイドを考えます
遅延評価セグメント木
写像も考えます
ローリングハッシュ
文字列系統は苦手で、まだZ-algorithmなどは理解していません…
強連結成分分解
互いに行き来可能なグループごとに分割します
考え方やテクニックなど
期待値の線形性
期待値の問題が出た時、これを理解してなくて困ってました…
逆元を毎回計算するとTLEする場合があります
必要な場面では前計算しておきます
二項係数のライブラリは以下を参考にさせていただきました
DPをメモ化再帰で書く
遷移が面倒な場合はメモ化再帰をしています
EDPCのフレンズさんの解説を読んで知りました
その他やったこと
デバッグ用ライブラリの整備
ローカルでは標準エラー出力、ジャッジの時は何も出力されないようにしています
マクロ等を作る上で以下の記事を参考にさせていただきました
atcoder-cliを自分好みに使う
シェルスクリプトを書いて以下を一気にできるようにしました
acc submitの時にojに引数を渡せるのを最近になって知りました
- ファイルが更新されている場合は再度コンパイル
- ローカルテスト
- ACが出たら提出か確認
- 提出
解けないor時間がかかる問題をスルーする
自分の実力だとABC-Dでも解けない場合があるので、順位表でどのくらい解かれているかを確認してから一旦飛ばしてます
順位表の確認にはAtCoderStandingsAnalysisを使っています
使用している拡張機能や便利サイトなど
入水の時にまとめたのをご覧ください
現在読んでいる本
- PAST本(上級~エキスパート)
- 一問一問学びがあって楽しいです
- 本に書いてあるのはPythonのみですが、C++のコードも公開されています
https://github.com/tsutaj/pastbook-2-source-code
- マスター・オブ・場合の数
- マスター・オブ・整数が良かったのでこちらも読んでいます
- 数学オリンピックの表彰台に立て！
- JMOに出ますと言ったら優しい先輩が貸してくれました！
手を動かして問題を解く癖がついてきた気がします
- JMOに出ますと言ったら優しい先輩が貸してくれました！
精進
夏休みに精進BAN鯖に参加しました、お世話になりました
水diffへの苦手意識がかなり薄まりました
さいごに
今まで基本的にABCしか参加してなかったので、これからARC,AGCだったり、Codeforcesにも挑戦しようと思います
黄色…なれるんでしょうか…