青色になった時の記事はこちら
遭難者です。ABC243でAtCoder黄色になったので記事を書くことにしました。
気が向いたら精進するスタンスを取っているのでレートのグラフがかなり歪です。
自己紹介
現在高専2年の、情報系の学生です。
数学が好きです。文字列が苦手です。
精進量
画像の通りです。気が向いた時に沢山解いています。
習得したアルゴリズム
青色から黄色に上がるまでに習得したアルゴリズムを並べていきます。
-
全方位木dp
全方位って言う割には根を頂点1で固定した方が分かりやすいように感じました。
まだコンテスト本番で実装したことは無いです。
かつっぱさんのこちらの動画で履修しました。 -
Mo's algorithm
クエリをソートして順番に見てくだけなので非常にシンプルでした。
まだコンテスト本番で実装したことは無いです。
ネット上の記事では理解できなかったのですが、友人に具体的なケースで教えてもらい理解しました。
過去に解いた問題を遡って見ましたが、青色から黄色になる過程で習得したアルゴリズムはこの2つのみでした。青色から黄色になるには知識よりも考察力の方が重要だと考えています。実際、私が最近のコンテストで解けた青diff・黄diffの問題は考察がメインで実装は比較的簡単な問題がほとんどです(例:この問題やこの問題、ネタバレに注意してください)。なのでもし現在青色で黄色になりたい！という人がいたら、過去問を大量に解くのが近道だと思います。特にDPの遷移の式の導出等は完全に慣れだと思うので、手を動かし、頭を使って考えるとすぐに出来るようになると思います。
Javaを使ってみて思うこと
-
遅い
ループ等は速いです。しかし、ArrayListやHashMapといったラッパークラスを必要とするものがかなり遅いです。
この遅さは例えば ABC242-F Skateのような問題で露骨に差が出ます。
上3枚の画像はC++、Python3(PyPy3)、Javaの提出のうちACとなったものを実行時間順に並べたものです。Javaが特に遅いのが一目瞭然です。これが原因で苦しい定数倍高速化を要求されるケースも少なくないです。 -
ラムダ式が便利
配列に値をセットしたい時やソートの方法を指定する時に非常に便利です。ルールが結構複雑ですが、慣れれば非常に強力な武器になります。
例えば ABC225E-フで入力を受け取ってからソートするまでは以下のように書くことができます:
var a = new long[sc.nextInt()][];
Arrays.setAll(a, i -> new long[] { sc.nextLong(), sc.nextLong() });
Arrays.sort(a, (i, j) -> Long.compare(i[0] * (j[1] - 1), j[0] * (i[1] - 1)));
(ACコード)
ソートもそうですが、特に Arrays.setAllは非常に強力です。Javaを使っていて良かったと思う数少ない場面の1つです。
今後の目標
- 海外のコンテストに挑戦する
英語を読むことに強い拒否感があり、AtCoderやyukicoder、TechFULといった国内のコンテストにしか出場できていません。これを克服してより多くの問題を解こうと思います。 - パソコン甲子園で良い成績を取る
情報オリンピックもパソコン甲子園も今年度はどちらもオンライン開催となり、交流の機会が減ってしまいました。来年度こそはパソコン甲子園で会津に行きたいです。
終わりに
競技プログラミングを始めた当初は緑色になるのが目標だったのですが、まさか黄色になれるとは思いませんでした。今後も競技プログラミングを頑張っていきます。
ここまで読んでくださりありがとうございました。