SRM486 の成績・ソース (要ログイン) : AC/AC/AC : 機械化計画
300開く
- 300-450-1000 の変則セットだったので「450はスコア的には普段より簡単と言っているように見えるが普段とは毛色が違うという可能性もあるので警戒回避」で300から
- 入力
s : int where 1≦s≦10億
t : int where 1≦s≦10億
min[cmp] {p | eval(s,p)=t} || ":-("
where cmp a b = (a.size(),a) < (b.size(),b)
eval r [] = r
eval r ('+':p) = eval (r+r) p
eval r ('-':p) = eval (r-r) p
eval r ('*':p) = eval (r*r) p
eval r ('/':p) = eval (r/r) p
- 『レジスタ１個しかないマシンがありまして、r=r+r, r=r-r(要はr=0)、r=r*r、r=r/r(要はr=1)の４つの命令を使って最短でレジスタの初期値sをtに変えてね。同じ長さの命令列があれば辞書順(*+-/)で早い方。無理なら ":-("』
- テストケース作成
- てきとうにでかいの
- (1,10億) (10億,1), (1,1<<30), (1<<30,1)
- (3,10億) (10億,3), (3,1<<30), (1<<30,3)
- ちいさいの
- (2,4) で + より * がちゃんと先にでる確認
- ええと、- で 0 になる。 / で 1 になる。
- t が 1 以上なので、- を使う意味はない
- / はいつやっても 1 になるので、使うなら最初
- * と + は増える。と思いきや 1 なら * では増えない。
- ２倍や２乗で増えるので、すごい増える。32回も使えば確実にtより大きくなる
- ということで、
- + と * だけで s から t を作れるか全探索してみる
- / で 1 にしてから、+ と * だけで 1 から t を作れるか全探索してみる
- 早い方をとる。
string run(int s, int t);
...
return min(run(s,t), "/"+run(1,t));
- こう。
- 待て待て。できない場合 ":-(" を返すルーチンはどこだ。
- bestはダメだったら ":-(" を返すとして…
- いや ":" って辞書順早いからやだな。ダメだったら "NO" とか返すか。
string run(int s, int t); // ダメならNO
...
string x = run(s,t);
string y = "/"+run(1,t));
if(x=="NO"&&y=="/NO")return":-(";
else if(x=="NO")return y;
else if(y=="/NO")return x;
else return min(x,y);
- うわーひどいコードになってきた。なんだ "/NO" って。
- まあいいか。runの実装は
- s==t なら空文字列
- s>t なら "NO"
- それ以外なら "*"+run(s*s,t) と "+"+run(s+s,t) の小さい方。
- ぎゃー"*NO" とか "+NO" とかいうコードをなんで俺は書いてるんだ。
- 今わたしの
- 願いごとが
- かなうならば
- Maybeモナドが欲しい
- うーむ。例外を使って書いてみる。
- あんまり綺麗にならない。
- 返値に"+"などを足していくのではなくてアキュムレータに貯めてく
string run(string p, int s, int t) {
...
return min(run(p+"*",s+s,t), run(p+"+",s+s,t));
}
- あーだいぶマシになった。
- なんか色々と酷いな。
- 終わったら落ち着いて綺麗に書く書き方復習しておこう。
- さてサンプル…通らない。
- あれ？
- しまった、minだと辞書順最小であって、最短なもの優先というのを考慮してない
- 考慮
- できた。通った。
- 最大ケース(1,10億で:-(を返す)でも時間問題ないな。
- submit
450開く
- 300で苦戦している間に既に450を通している人が結構いる
- てことは簡単なのかー
v : vector<1..50>
i≠j → v[i]≠v[j]
1 ≦ |v| ≦ 50
f(v) where
f(v) {
if( |v|≦1 )
return 0
else {
return 1/|v| * Σ{
f( [e∈v|e＜p] )
+ f( [e∈v|e＞p] )
+ |[e∈v|e＞pでeはpより左にある]|
+ |[e∈v|e＜pでeはpより右にある]|
| p∈v}
}
}
- 『ランダムにpivotを選ぶクイックソートをしたときに要素を動かす回数の期待値』
- 期待値だ！無理！
- 450ってことは実は確率とか関係なくて、すごく簡単とか…
- 順序逆転してるペアは最終的に必ず１回ずつ動かされるから
- 順序逆転ペアの答えを数えて返すだけ！
- とか。期待値も何も常に同じだったり！
- 実装してみた
- はい違いましたー。
- サンプルの一個目にpivotの選び方によって回数違う例あるじゃないか…それぐらいは読みなよ俺…
- ううむ
- 単純にシミュレーションするのが間に合うわけないから
- 何か対称性みたいなのを利用して期待値の計算が簡略化したりするんだよなあ
- わからない…
- 確率はわからない…
- あまりにも思いつかないので、そういえばSRM解答機械化計画の最中だったので、問題をフォーマルに書いてみよう。
- ※上記の「出力」を書く
- これが求める物の定義そのまま…
- …って、あれ？これメモ化すればこの定義そのまま実行して間に合うんじゃないか！？
- この関数 f の引数にくるvectorは
- 「pivotより大きい」か「pivotより小さい」で切って作った物しかないので
- 元々のvectorの同じ順番に並んでて、
- つまり [e∈v | a≦e≦b] という「a以上b以下」のもの全部という形で表せるものしかこない
- てことはせいぜい50^2通りしかない。
- fの中身は適当に実装しても50^2。50^4は通る。
- というわけで実装。
- map<pair<int,int>,double> memo; ...
- できた
- 通った
1000開く
- LayCurseさんやwataさんが既に高速に片付けてる
- ぬぬ、これも簡単問題なのか。
- 300と450で出遅れてしまったからこれは解いてやる
p : set<Point2D>
|p| ≦ 50
min { max(area(convex_hull(a), convex_hull(b)) | disjoint_union(a,b) = p }
- 『二次元平面上の点を、重ならない二つの凸多角形で覆いたいです。大きい方の面積を最小にして下さい。』
- あれ、これは本当に簡単かも。
- 点集合pを、ありうる分け方全通りで２つに分けてみる
- 凸包を求めて面積を求める（ライブラリコピペするだけ）
- 最小値を返す
- 最適解を分ける直線を適当に持ってきて動かしてやると両端が凸図形の頂点に引っかかるようにできるので、
- pから2点の選びかた全通り試す
- その2点の間に直線を引いて、それで点集合を左右に分ける
- で「ありうる分け方」全通りが試せる。
- 分け方候補はO(|p|^2)で、凸包などはO(|p|log|p|)で求まるので、計算量は十分間に合う。
- 実装実装。
- 引いた直線上に点が乗っかってると、左右どっちに入れるか決められないなあ。
- 適当に、(pから選んだ点±1e-6) を使って直線を引くようにしよう。これでピッタリ線上に乗ることはなくなるはず
- できた。
- 何故か答えが２倍になる。
- なんで？
- …
- …自分ライブラリの面積関数が間違ってる…外積を2で割ってない…
- 修正。できた。submit。
- これ大丈夫かね本当に。
- 直線に乗っちゃう場合の扱いがやっぱり怪しい…
- (pから選んだ点±1e-6)だけじゃなくて(pから選んだ点±1e-6i)も入れておこう
- なんかこれでもいじめられる気がするけど、きっとテストケースそんな強くないだろう…
撃墜フェーズ
