本記事について
E869120さんがQiitaに公開されている記事をやってみてそれについて感じたことをメモする。
qiita.com
メモ
全探索：全列挙
1.ITP1_7_B - How Many Ways?
- 問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja
- メモ
問題文の「重複無しで...」と「組み合わせの数を...」の部分を見落としていて、最初はi,j,kの正整数(順序あり)を全探索しようとしてしまい、少し時間を無駄にした。このようにたまに問題文を間違えて認識してしまうことがあるので、注意しなければいけない。j = i, k = x - i - jとして問題のあるi,j,kを省いたけど、j = i + 1, k = j + 1で全探索して数えたほうが楽。
- 提出コード
AIZU ONLINE JUDGE: Code Review
- 参考サイト
2.AtCoder Beginner Contest 106 B - 105
- 問題リンク
- メモ
Nの約数を全列挙するアルゴリズムを使う問題。Nの約数の全列挙の効率的なアルゴリズムの計算量はO(√N)である。効率的でないアルゴリズムの計算量はO(N)である。
- 提出コード
Submission #16922721 - AtCoder Beginner Contest 106
- 参考サイト
N の約数を全列挙するアルゴリズム | アルゴリズムロジック
- 関連問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_D&lang=ja
B - 完全数
3.AtCoder Beginner Contest 122 B - ATCoder
- 問題リンク
- メモ
切り分けられる文字列全てを取り出し、その文字列が条件を満たすか調べていた。これでもACできるが、解説動画で紹介されていたやり方のほうが計算量も少なくて済みそうだし書くのも楽だと思った。文字列について、それぞれの文字が条件を満たすかどうか(ATCG文字かどうか)を01ビット列に変換して最長な1の数列の長さを求める。
- 提出コード
4.パ研杯2019 C - カラオケ
- 問題リンク
- メモ
全探索を実装するだけ。特に必要な知識は無し。
- 提出コード
全探索：工夫して通り数を減らす全列挙
6.三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
- 問題リンク
- メモ
単純に文字列Sから3桁を取り出して全ての組み合わせ計算をすると(3x10^4)C3≒10^12で間に合わない。だけど、そもそも、3桁の暗証番号は各桁0-9だから組み合わせは10^3通りしかなくて、その暗証番号が文字列Sにその順番通りに存在するか各桁ごとに全探索すれば、計算量は最大でもO(10^3*30000)≒O(10^7)だから間にあう。
- 提出コード
Submission #16934841 - Sumitomo Mitsui Trust Bank Programming Contest 2019
7.JOI 2007 本選 3 - 最古の遺跡
- 問題リンク
- メモ
単純に全ての点から4つの点の組み合わせをすべて全探索するとO(NC4)となりこれはO(3000C4)≒O(10^12)で当然間に合わない。ここで、思いつくのは正方形は連続する2頂点が決まれば、残りの2頂点は反時計回りに90度または-90度回転の2通りに決まる。また、座標xyはともに0-5000であることから、bool型の二次元配列bxyを作って、その座標に点が存在すればtrue、その座標に点が存在しなければfalseを代入する。そうすれば、任意の座標に点が存在するかしないかはO(1)で求められる。よって、すべての点から2つの点の組み合わせを選び、その２点を連続する頂点とする正方形は2通り存在できる。それらの正方形がそれぞれ存在するための必要純分条件は残りの2頂点が存在するかであるから、これは先ほどの二次元配列bxyを使えばO(1)で調べられる。以上の考え方で全探索した。
補足で書くが、私の提出コードを確認してもらえばわかるが自分の解き方では、少し込み入って行っていて面倒である。しかも、先ほど言及していたそれぞれの正方形の残りの2頂点の座標を求める式について、図を描いて考えていた(高校数学的気分)。しかし、大学で学ぶ回転行列を使えばもっと簡単に残りの頂点の座標を考えることができる。回転行列の考え方の気持ちを下式に示す。図も含めて説明を書きたいところだが、めんどくさいので省略します。すいません。参考リンクを載せておくので、それでお願いします。
よって
または
- 提出コード
Submission #16937602 - 第６回日本情報オリンピック 本選（オンライン）
- 参考リンク
【Python】JOI 2007 本選 3 - 最古の遺跡(①高校数学ベクトル、②「in リスト」は激遅)【AtCoder】 - Qiita
Ruined Square [AtCoder Beginner Contest 108 B] - はまやんはまやんはまやん
https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho-review.pdf
- 関連問題
8.Square869120Contest #6 B - AtCoder Markets
- 問題リンク
- メモ
確かに、工夫するとO(30*30)で全探索できる。最初にやり方を思いついた時、ホントにあっているのか少し不安に思った（証明できるのかなと思った）が入力例が思いついた方法の通りだったのでこれならあってるはずだと思って実装して提出したら、ACした。入力例を見ることも非常に重要である。それぞれ、入口は配列A、出口は配列Bから任意の一つの座標を選びその入口と出口の移動時間を調べて、最小の移動時間を出力すればよい。移動時間はA[i] < B[i]よりO(1)で計算できる。
- 提出コード
9.JOI 2008 予選 4 - 星座探し
- 問題リンク
- メモ
制限時間10sになっていたのを見逃していて、いつも通り制限時間2sで考えていた。制約はちゃんと見ましょう。JOIの予選は制限時間がないらしいです(解説に書いてた)。ただ、制限2sでも解けるので問題はなかった。単純に全探索するとO(MN^2)≒O(2*10^8)となる。これは10sくらいかかる。効率よく全探索するとO(MNlogN)≒O(2*10^6)となり間にあう。星座の一つの点を決めて、任意の星を一つ選びその星を先ほどの星座としてみなし、移動量dx,dyを求める。その後そのdx,dyをそのほかの星座の座標に足して、その座標に星が存在するかを調べる。星座すべてが存在すれば良い。
- 提出リンク
全探索：ビット全探索
10.ALDS_5_A - 総当たり
- 問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja
- メモ
dfsで部分和問題を解く。setに可能な部分和を保存した。
- 提出リンク
