menu

競プロ「これだけ5問!」

AtCoderで青色レベルになるための最短経路を模索するための記事です.

私はプログラミング経験がありますので,「すぐに青色ぐらい行くやろ」と思って競プロを始めました.

しかしコンテストに出ては思ったほど問題が解けずこんなはずじゃないというのを10回くらいやりつつ茶色をさまよっていました.

それが最近,よさげなコンテストを「過去のコンテスト」欄に見つけたのでリアルタイムのコンテストでなくいわゆる「過去問解き」に手を出し始めました.

過去問を解いていっていると「すぐに青色ぐらい行くやろ」という気持ちになってきたのでこの記事を書いた次第です.(緑なりたてで執筆しています)

ちなみにEducational DPというのがきっかけとなった神コンテストです.

競プロ入門者に足りないがちの力

問題を解く上では, - 解法を考える - 実装する

という2つのステップがありますが,入門者に足りないのは圧倒的に実装ステップです.

私もそうだったのですが,蟻本の中級ぐらいまでをざぁーっと読んで「蟻本完全に理解した」といっていざコンテストに出ると全然解けないという状態に陥ります.

アルゴリズムの雰囲気を理解するというのとそれをコードとして実装するというのには幾分かのギャップが存在します.

私の例ですと,コンテスト中に「cpp 降順 ソート」みたいな基本事項の検索に時間をとっていました.

このギャップを埋めるには「実際に書く」というのが手っ取り早いです. そして,実際に書くには問題を解くというのが一番気持ちが乗ります. 解いていくうちにアルゴリズムを完全に理解してはいなかったことに気づいたりします.

コンテストに何回も出ればいずれ身につくでしょうが,思い立ったときにコンテストに出て問題を解くスタイルでは被覆される基礎事項がランダムですので全被覆には時間がかかります.

そこで欲しいのは「これさえ解ければ基本事項はマスターできる」という問題集です.

もちろん,問題数を増やせばこれは可能です.実際私もdrkenさんの蟻本問題シリーズの信者であり,本記事で出す問題もどこかで言及されたやつがほとんどです.

ですが,時間は有限.また,コードの再利用を考えても解く問題数が多すぎると過去の自分の遺産を見つけづらくなります.

そこで本記事では極限まで問題数をしぼり,これだけやれば基礎事項が身につく5問を選出しました.

理解を目指す基礎事項

蟻本に書いてあるアルゴリズムはどれも重要です.その中で知らないとどうしようもないことをリストアップしました.

実装力部門

  • 文字列の入力
  • modの割り算
  • long longの出力
  • 配列(特に多次元配列)のソート
  • queueの使い方

アルゴリズム部門

  • 最小全域木
  • Union Find木
  • Segment木
  • 動的計画法(DP)
  • フロー問題(dinic法) *ちょっと難しい

いくつかの問題を解いて,これらを完全に理解することを目指します. 以下が問題設定です.

Select 5 problems


問題文

ネット上に,大量の競技プログラミングの問題があります. プログラミングの知識が全くない坐禅君がそのうちN問をACできるようなコードがかけるようになったとします.このときの坐禅君のレートを最大化する問題のリストを出力せよ.

ただし坐禅君は解法の理解に2時間以上かかる問題は解けません.

制約

  • 高度な考察をしなくていい(解答を読めば分かるレベル)
  • N = 5

出力例1


1. Welcome to AtCoder

これを解けるようになればint型の入出力だけでなく,int型同士の足し算,さらにはstring型の入出力もできるようになるという良問です. これに加えて

string s;
cin >> s;
cout << s[0] << endl;

で文字列の最初が出力できることをおさえておけば入出力ではしばらく困らないかと思います.

またこの問題を解くときにある程度cppファイルのテンプレートをつくっておくとよいと思います. 先人たちが多くのテンプレートを考案しているので好きな人の提出履歴などを見ながら合うものをみつけてください. 私の現在使っているテンプレートはこちらに載せておきます.

2. ARC 076 D - Built?

最小全域木の問題です. 「x方向の辺とy方向の辺の2つの辺がつくられる」 という考察さえできればあとはシンプルに最小全域木を求めればいいだけです.

蟻本では最小全域木の解法としてプリム法とクラスカル法が挙げられていますが,まずはクラスカル法だけ押さえておけば十分かと思います. 必要となる知識は

  • Union Find木
  • 配列のソート

です.

配列のソートについては多次元配列のソートなどは特につまづきポイントであると思うので別ページにまとめておきました.

3. ABC 110 D - Factorization

素因数分解と組合せの問題です. 立式まではいけると思います. あとはこの実装です.つまずくのがコンビネーションの計算です. - 階乗はありうるやつを全部保存しておく. - 素因数分解をライブラリとしてもっておく.

が大事となり,この問題をACできるコードをもっておくだけで$$10^9 + 7$$でわるときの安心感が違います.

4. ABC 010 D - 浮気予防

アルゴリズム自体が少し理解に時間を要する最小カットの問題です.

蟻本にも書いてあるdinic法を使います.

dinic法にはDFS,BFS,queueの使い方など基礎事項がてんこ盛りですので少し大変ですがおすすめです.

自分で0から書くのは時間がかかるので人が書いたものをライブラリとして持ってきておくだけでも役にたちます.

問題を選んでおきながら「これ理解すればいいから頑張って!」では少し不親切なのでアルゴリズムについて私が咀嚼した記事も書いておきました.

5. ARC 073 F - ManyMoves

Segment木を用いて最小値の検索を高速化するやつです.

F問題でACは難しいのですが,実行時間を気にしなければ方針自体はそれほど理解は難しくありません. 高速化も答えを知ったあとだとなんとかなります.

この問題,イメージとしては数直線上にある値F(x)がのっていて,毎ステップyが与えられ $$F(x) + | x - y |$$ が最小値をとるxを求めるという操作が必要になり,この操作をSegment木で高速にしようという流れです.

yは毎ステップ変わるので $$F(x) + | x - y |$$ をSegment木に保存しようとすると全要素を毎ステップ更新する必要がでてきて意味がありません.Segment木で保存する値をyに依存させないのがこの問題の肝です.

結局答えとしては $$F(x) + x$$ の値を保存したSegment木と $$F(x)-x$$ の値を保存したSegment木との2本を持っておくことで解決します.

Segment木の理解だけなら他の問題があると思いますが,他のテクニックとの組み合わせという点では勉強になるかと思います.

まとめ

以上が私なりの「競プロこれだけ5問」です. 必須なアルゴリズムはある程度これでおさえられると思います.

N=7とかになると - BITを用いた転倒数の計算 - 期待値DP 倍精度実数の出力

などもいれたいところです. 「このセレクションはセンスがない.おれならこの問題をいれる.」みたいな指摘を期待しています.