Skip to content

Instantly share code, notes, and snippets.

@n-ari

n-ari/160518div1.md

Last active May 25, 2016 16:11
Show Gist options
  • Save n-ari/aae878f0656af9085bde7860de075e4e to your computer and use it in GitHub Desktop.
Save n-ari/aae878f0656af9085bde7860de075e4e to your computer and use it in GitHub Desktop.
Download ZIP
2016 5/18 div1 traPcontest
Raw
160518div1.md

160518div1

少しアルゴリズミックなことをしています。詳しくは「蟻本」を買うか、ググりましょう。

AtCoder Typical Contestというものがあるのですが、それの第一回・第二回のA問題でDFSとBFSが分かりやすくまとまっています。ぜひ参考にしてください。

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

A: 幅優先探索 - AtCoder Typical Contest 002 | AtCoder

解説

  • A : 出力ミスが目立った問題。末尾に無駄な空白を入れず、改行を忘れない。後は実装あるのみ。
  • B : 橋の許容量が小さい順に使うと最適解。その場その場での評価で最適解を求めるアルゴリズムを貪欲法と呼びます。
  • C : *深さ優先探索(DFS)*です。再帰、もしくはスタックを使って記述します。全探索が出来ます。
  • D : *幅優先探索(BFS)*です。キューを使って記述します。最短経路が求まります。
  • E : Dに同じ。ただ壁で判定するので少し実装が面倒です。
  • F : 階段を13段登るとn-1n-3段の階段を登るというサイズの小さい問題に分割できます。 すると、最終的には0,1など自明な解を持つところまでサイズが小さくなるので、これで求まります。 ただし、これを再帰で書くと非常に時間がかかります(指数時間)。 これを、「ある段数についての答えが求まったら保存しておいて、次からはそれを返すようにする」というようにしておきます。 すると、段数の数(つまりn=0~30)に対してそれぞれ1回のみ計算するので、非常に高速になります。 これをメモ化再帰とか*動的計画法(DP)*とか呼んだりします。
  • G : 想定解は平衡2分探索木と呼ばれるものです。 でも、それを実装するのはとても大変です。 C++においてはset/map、JavaにおいてはTreeSet/TreeMapを使うことで平衡2分探索木を扱えます。 平衡2分探索木とは要素数をNとして、「値の追加」「値の検索」「値の削除」をそれぞれO(log_2(N))で行えるデータ構造です。 詳しいことは割愛しますが、速いです(確信)。 これを使い、Sの値をまとめておき、各Tの値に対して、Sに存在するかを検索すればO((N+Q)log_2(N))で完了します。 なお、O(NQ)の解法は10^9を超えます。これは現代のコンピュータでも数秒では終わらない処理となります。気をつけましょう。 また、JavaのHashSet、C++11のunordered_setという、ハッシュを使ったデータ構造だと、各操作をO(1)で行えます。 こちらでも解くことが出来ます。C++11の場合は、コンパイル時にはg++ -std=c++11、提出時もC++11を選択するように。

C++による解答例

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment