お久しぶりです。Viという者です。前回の記事（入緑記事）をたくさんの方にお読みいただけて、嬉しい限りです。2022/02/27のARC136にて入水できたのでその報告の記事です。12
入水するまでにしたこと
タイトルにもある「力技」の具体的内容です。以下の三分野を強化することのみに絞って精進しておりました。通常は問題を多く解いて場馴れしていくのが普通ですが、無理やり一部の高diff問題を解けるようにして入水した、ということでかなり「力技」な方法だと思います。
-
データ構造
- 平方分割
- フェニック木（BIT）
- セグメント木
- （遅延セグメント木3)
-
グラフ探索アルゴリズム
- ダイクストラ法
- クラスカル法
- ワーシャルフロイド法
-
動的計画法
- メモ化再帰
- bitdp
- 桁dp
- 区間dp
- 木dp
- その他データ構造と組み合わせるdp4
まず初めに
基本的にどんな邪道も縛らずに自由に競プロしていましたが、一つだけ縛っていたのがAtCoder Libraryの使用です。目的としてはACLで殴れる高diff問題を解いて無理やり入緑すると、後々アルゴリズム力の不足が目立ってしまうのではないかと危惧していたからです。
そのため、入緑してまず取り掛かったのがACLの習得です。全てではなく、使用頻度の高いごく一部に絞って覚えました。具体的には、
#include <atcoder/fenwicktree>#include <atcoder/segtree>#include <atcoder/modint>#include <atcoder/dsu>
の四つです。私は代数的構造についての抽象数学をほとんど学んだことがなかったので、特に#include <atcoder/segtree>の理解には苦労しました。せっかくなので個人的解釈を書いてみようと思います。5
#include<bits/stdc++.h>
#include<atcoder/segtree>
using namespace std;
using namespace atcoder;
const int inf = 1<<29;
int op(int a, int b){
return min(a, b);
//二項演算、RSQならa+b、RMQならmin(a, b)
//この時、結合法則を満たしている必要がある。f(f(a, b), c) = f(a, f(b, c))
//(単位元が存在していることが好ましい)
}
int e(){
return inf;
//適当な単位元が存在しない時は、-1などのありえない数値を設定しておいて、
//二項演算opの処理内で、
//if (a == -1) return b;
//if (b == -1) return a;
//などとすると良い。
}
int main() {
int n;
cin >> n;
segtree<int, op, e> seg(n);
//segtree<要素の型T, 二項演算の関数op, 単位元を返す関数e> foo(要素数 or vector<T>)
//以下略
}
その後
その後は前述の通り、以下の三つについて勉強しました。
- データ構造
- グラフ探索アルゴリズム
- 動的計画法
データ構造
目的は、コンテスト中、途中で出てきた小問題の解決法がわからない時に、考えることなく無理やりACをもぎ取るためです。
例えば、https://atcoder.jp/contests/arc134/tasks/arc134_b では、公式解説では前後から貪欲法で解いていますが、セグメント木に文字コードを突っ込んで、範囲動かしながらRMQをするだけで解くこともできます。
たとえ非効率なコードだとしても、C++ならTLに間に合うことも多いので、大幅な時間短縮に使え、また「最終手段がある」という安心感はメンタル面でもかなりアドバンテージがあります。
グラフ探索アルゴリズム
これは、グラフの問題が出た時に、諦めずに解くことができるようにするため、最低限の知識だけインプットしました。特にダイクストラ、クラスカルは出題頻度も高く、早めに学ぶ価値が高いアルゴリズムのように感じます。
まだまだ拙いので、これからの課題です。
動的計画法
入水するまでに最も力を入れたのがdpです。というのも、多数の問題に共通しているかつ、ある程度難易度の高いものがdpだと考えたました。
緑後半では edpcを中心に、dpの力を青色中位程度まで高めることを目標にしていました。J問題を除くU問題まで埋めて、青diff以下なら大半のdp問題に太刀打ちすることができるようになりました。7
U問題まで解かなくとも、S問題くらいまで解けば、大半のdpの問題に太刀打ちできそうです。
今している取り組み
現在入青を目指してしているのは、典型アルゴリズムの習得、そして典型問題の習得です。
今の所はライブラリ整理はあまりせず、あくまでアルゴリズムを理解して、問題に柔軟に対応できることを目指して精進しています。
今の所は成長できているのか、レーティングは単調増加できています。
最後に
ここまでお読みいただきありがとうございます。今回は多少なりとも入水を目指す人にとって参考になるように書いたつもりですが、かなり読みにくい文章になってしまっていると思います。（そもそも正攻法の入水の仕方からは程遠いですが）
記事に勘違いや間違い、あるいは不明確な点などございましたら、お気軽にコメント等お願いします。
LGTM、ストック等してくださいましたら泣いて喜びます。