作業跡: AtCoder/abc119 at master · murnana/AtCoder · GitHub
相変わらずC,D解けてないです…
C - Synthetic Kadomatsu
魔法で指定された長さの竹を作ろう！ということらしい。 MPとか書かれている辺り、ゲーム脳が楽しくなってきた。
だからって、解けるかどうかはまた別なのであった…
解説動画やPDFからのメモ
- 足し算の結果は順序を入れ替えても変わらない
- Nが8本あったとき、パターン数は 48 = 216 = 65536 通りしかない
- 全部試そうと思えば試せる！😃
- よし、全パターン試そう！(全探査)
- 解き方①DFS
- 1から順に全パターンを調べる(最終的に65536 通りができる)
- 解き方②4進数
- Aを
0, Bを1, Cを2, ☓を3とする- そうすると、すべて2進数で表せる
- Aは
00, Bは01, Cは10, ☓は11`
- 最終的には、すべてが
00のパターンから、すべてが11のパターンになる(0 ~ 216 - 1通り)
- Aを
D - Lazy Faith
解説動画やPDFからのメモ
- ソートされた数値N個にに対して、O(logN)で計算して答えが出せる
- 数あてゲームで、想像した数値より「小さい」「大きい」と答えて近似値を求めるのと同じアルゴリズム
- 求めているものが自分の位置より大きいか、小さいかで移動する範囲は決まる
- 神社から寺に行く、という問題がある場合、コストの小さいのは？
- 二分探査で計算する
