SRM482 の成績・ソース (要ログイン) : AC/AC/- : 嫌いな人が多い問題はだいたい好きな問題です
500開く
- 『N枚ハノイの塔を最速で解く手順でD手目に出てくる局面は、全局面をくまなく辿る手順では何手目に出てくるか』
- 最悪 3**19-1 手かかるので、愚直にシミュレートすると無理かな。
- ともかくテストケース作成。
- N=19のケースを何個かと、
- N=1,D=0、N=1,D=1、N=2,D=0、N=2,D=1、N=2,D=3 を追加
- さて。ハノイの塔と言われると0.1秒で思い浮かぶのが
- こちらのページにあるような、3角形を綺麗に再帰的に並べた状態遷移図。
- 最速ルートは、3角形の一辺をまっすぐ駆け抜けるルート(赤)。
- 全巡回ルートは…ええと、3角形をこう遠回り遠回り遠回りして進むルート(青)か。
- この青の遠回りルートは、もちろん再帰的にくねくねしている。
- この図を念頭に、再帰的に手数を計算しよう。
- 最速 2**(N-1)-1 手以下の局面（赤ルートの前半）は
- 一回り小さい三角形を 赤:／ 青:／＿ で進む時に何手かかるか計算すればいい
- 最速 2**(N-1) 手以上の局面では、
- 遅いルートで 3**(N-1)*2 歩あるいた後、
- 一回り小さい三角形を 赤:／ 青：／＼ で進む時に何て掛かるか
- 初期状態は、赤:／ 青: ＿＼ と進む三角形
int ＿＼(int N, int D) {
if( D <= 2**(N-1)-1 )
return ／＿(N-1, D);
else
return 3**(N-1)*2 + ／＼(N-1, D - 2**(N-1));
}
- 停止条件は…？ N=0 なら 0 枚のハノイだから 0 手で一致する。これ。
- if(N==0) return 0;
- 同じように考えると、
- int ／＿(int N, int D)
- int ／＼(int N, int D)
- も同じように 2**(N-1) で分けて再帰で書けて
- できた！
- そしてサンプル全然合わない！
- (N=1,D=1) ですら合ってないぞ。なんで？
- むむむ
- むむむ
- むむむ
- あ
- 3のベキ乗計算する関数、std::powの整数版がなかったからdoubleにするのがなんとなく嫌で自作してたんだけど、
- これ常に1乗を返している…
- アホだ…
- 直した。通った。
250開く
- 部屋のスコア表見ると結構苦戦している人が多い。警戒。
- 『1からNまで数が並んでます。1から始めて1個飛ばしで(1,3,5,...)と数を消す、残っているのの中から、先頭から始めて2個飛ばしで(2,(4,6),8,(10,12),14,...)消す、…を繰り返すと、最後に消えるのは何？』
- テストケース作成
- N=200万…が単純に最悪ケースだよね
- N=1,2,3,4,5,6,7,8 を手計算して追加
- さてどうしよう。
- ヨセフス数ってやつだっけ。あれは消す幅は一定だったっけ。いずれにせよそんなのが250では出ない気がする。
- うむむ難しい。
- 何も思いつかないけど、とりあえず何も考えずシミュレートする解を書いてみよう。
- 最初のループで残った数の数は1/2になる、次で1/2・2/3=1/3になる、1/4になる…でstep>v.size()で打ち切ると √n回でおわるからO(n^1.5) くらいか
- 200万はきついけど、1万くらいは行けるはずなので、
- あとで作る予定の賢い解の小さいところでの全数チェックに使えるはず
- そういえばこの部分の書き方ですが、
- 個人的な趣味として、「一度"作った"データはできるだけ書き換えない」スタイルをできるだけとるようにしてます。
- できるだけ、というのはメモリ足りないとかの時は諦める。
- vector の erase や insert は使わない。余程の理由がない限り新しくvector作る。
- たとえば
- vector<int> v; があって、そこからstep個おきに要素を取り除くとしたら
vector<int> erase_step(const vector<int>& v, int step) {
vector<int> answer;
{
// ここで answer を計算 / answerの初期化
}
return answer;
}
v = erase_step(v, step);
- ここまで自動的に書いてしまう感じ。
- ここまで書くと中身はほぼ自動的に決まって
for(int i=0; i<v.size(); ++i)
if( i%step != 0 )
answer.push_back(v[i]);
- こうですね。
- 今回実際にsubmitしたコードは、最後に消した要素も同時に返すのが微妙に面倒だったので関数分けないでインラインで書いちゃってますが。
- 話がそれました。
- 書いたコード、N=200万 でも手元で 300msec で完了する…
- あれ？これだけでいいの？
- 念のためサーバで確認。100msecくらい。
- 上限見間違えてないことの確認に N=200万1 を入れたら怒られた。見間違えてない。
- …
- 出しちゃえ！
1000開く
- 『重さのわかってる重りN（≦20）個と、わからない重りU（≦4）個があります。正の整数重みで1億以下なことはわかってます。あなたは神の視点でU重りの重さも全部わかっています。神様でない人が、天秤を使ってU重りの重さを確定できるか、それぞれyes/noで答えてね』
- まず、20個のわかってる重りで計れる重さは
- それぞれ使うか使わないかで、2**20 通りか
- これは全部数えられるな。
- いや違う、天秤の両側におけるので、左に置くか右に置くか使わないかで
- 3**20 通り計れる！
- これは全列挙は無理
- いやいや待て待て
- まず 2**20 を列挙して (W とする)
- 重さ t を計れるかどうかは
- t ∈ W
- または、w∈W が存在して、それをtと同じ側に置いたら釣り合うか判定 w+t∈W
- で引き算パターンも処理できる。
- これは、O(|W| = 2**20)かかるけど、Unknown重りが4個しかないから、毎回このくらいかかっても問題ない！
- よし。つまり2**20全列挙しておけば、各重さを量れるかどうかは十分間に合う時間で判定できる。
- で、この情報を使って…
- 各Unknown重りuについて、
- uが直接計れるなら、当然 "yes"
- 整数と分かっているので、u-1 と u+1 が両方計れるなら "yes"
- これでわかった物uをWに追加、を繰り返して変化がなくなるまでやれば終わりでは？
- 書いた
- あんまりサンプルと合わない
- そうか。1億以下とわかっているので、「99999999より大きい」とわかれば確定する！
- この特殊ケースを追加
- まだ合わない
- ええと、
- {20}, {10,10} --> "yes" "yes"
- …
- なるほど。Unknownな10は直接は計れないけど、10=10 なことはわかって、それ2つと20を比べると、u+u=20 だからuが確定するのか。
- ひええ。
- すると、unknownなものの中で同じ重さのものがk個あったら、
- (u or u±1) だけでなく、(2u or 2u±1) や … (ku or ku±1)
- が計れれば u は確定するのか…
- いや、もっと広いな。ku は k の倍数なことはわかるので、ku±1ではなく、ku±k の範囲で上下挟めれば確定する
- というルーチンを実装
- まだサンプル合わない…
- {12},{1,1,2,2} --> "yes"*4
- なんで？
- そうか、1=1, 2=2, 1+1=2 はわかるから、未確定重りが{u,u,2u,2u} であることはわかる。
- てことは全部乗せると6u。これが12より小さいことも計ればわかるので、
- 6u=6 しかあり得ない、
- ので全部確定！！
- こういう複雑な確定は小さい重みの重りでしか起こらないと仮定して小さいところを全探索…
- と思ったけど、さっきのでも {59999994,60000006}, {u,u,2u,2u} でも確定するし、全然ダメだ。お手上げ。
撃墜タイム
- 同じ部屋で1000をsubmitしている人がいたので開いてみる
- …
- あるていど計れる重さを全列挙するのはいいとして、
- Unknown重りを±10の範囲で全部動かしてみて10000通り試して、
- 「どの場合も実際の値だった場合と違う天秤結果が得られるケースがある」なら確定、としている
- おおお
- そうか、「重りの値が小さい範囲」じゃなくて実際の重りの重さの周辺を小さい範囲で全探索するという手が…
- {1,1,2,4} で "8の倍数に限る" までは作れるけど、"10の倍数に限る"は作れないから、±10で見れば確かに巧く行く気がする…
感想
- 厳密にあっているのかどうかわからないですけど、あの1000の「細かく動かしてみる」解は思いつけるようになりたいなあ。とてもコンピュータ的でとても美しい。
- あとは、1000はコード書いてからサンプル動かして気づくんじゃなくて、サンプルは書き始める前に全部確認しておくべきだよなー。と前も思ったのだけど実践できてない。よろしくない。
