SRM462 の成績・ソース (要ログイン) : AC/AC/- : 撃墜祭りだと思ったのに…
450開く
- 『N個の箱に、各C個ずつキャンディーが入ってます。i番目の箱のキャンディーは1個につきscore[i]点のスコアです。そこへイタズラ者がやってきて、2個キャンディーをランダムに選んでswap、をS回くり返しました。さて、それぞれの箱に入ってるキャンディーの平均スコアの期待値は？』
- 1≦N、C≦50
- 1≦score≦100
- 0≦S≦10000
- 同じ箱のキャンディー2個をswapすることもあります
- 1 ＜ C*N
- まずテストケース追加…
- 大きい方は全部大きい場合でいいとして、
- 最小ケースってどれが一番ヤバいんだ？
- C=N=1 は… 1＜C*N だから無しなのか。なんでだろう。
- ああ「2個選んでswap」がこの場合あり得ないからか
- C=1、score={1,1}、S=0
- C=2、score={1}、S=10000
- くらい足しておく
- キャンディー全部で2500個あるから
- どれがどこにあるかを全部ベクトルで管理して
- １回のswapを確率でどうにかして遷移行列を作ってS乗を計算
- それは2500×2500の行列の掛け算です
- 無理です。
- そもそもキャンディー全部の位置を行列遷移できるようなベクトルで書いたら、2500次元では足りない気がするぞ
- キャンディー１個１個独立に計算できるかな。
- 箱iにある特定のキャンディー１つに着目したとき、
- 1回のswapで他の箱jに動く確率は、
- ペアの選び方 C(NC,2) で
- その特定の1個と、箱jにある1個が選ばれる場合の数を割るんだから
- 要するに箱jにあるキャンディーの個数に等しいので
- C / C(NC,2) = 2/N(NC-1)
- だ
- 動かないで元の箱に残る確率は 1-(↑これ)*(N-1)。
- というのをS回くり返せば、どの箱に何%の確率でいるかは求まる。
- これ独立に計算して大丈夫なのか…？
- 小さいサンプルで手計算してみる。
- あってる。
- いいのかな。他に思いつかないからこれで組むしかないな。
- サンプルに結構複雑なのがあるから、それが通れば問題ないはず。
- 書いた。N*Nの行列でさっき求めた遷移確率の行列を表現。
- S乗を求める。O(N^3*log S)
- ベクトル (1 0 ... 0) を書けると、0番目の箱にあったキャンディーがS回後に各箱にある確率のベクトルが求まるので
- それを使って期待値を計算
- できた。実行！
- サンプルと…表示された答えはあってるんだけど、
- ローカルのテストコードが "FAILED" と返している。
- ううむ、これは、精度が 10e-9 の範囲に収まっていないということ…？
- 他の箱に移る確率は全部等しいから、N-1個に分けて考えるんじゃなくて、1つにまとめて考えられるはずなんだよね、これ、本当は。
- ちゃんとまとめて式を立てないと誤差が大きすぎてしまうのだろうか。
- 一から考え直すのいやだなあ。最後の期待値計算のループだけまとめ計算に直したら通ったり
- …しない。やっぱりFAILED。
- ええー。
- そもそもどれくらい誤差が出ているんだろう。
- テストルーチンの 1e-9 の閾値をさげて 1e-6 くらいにしたら通るくらいだろうか
- ちょっとテストルーチン変えてみよう
- …
- 変えてみよう…
- …
- あれ？
- 10e-9 の誤差考慮してない？？？？
- if(Expected==Received) ...
- そんな馬鹿な…？？？naoya_tさんカスタムバージョンTZTesterを参考にdoubleの誤差許容は入っているはずなのに…
- …
- ！！！！わかった！！！！
- 返値がdoubleの時は誤差を考えてるけど、vector<double>のときは考えてない！！！！！
- うおおー。修正。
- ちゃんと 10e-9 に最初っから収まってた。なんてことだ。
- submit
250開く
- 結構解くまでの時間がバラけている。難しめなのか。
- 『0と1の並んだ文字列と、正の数ageが与えられます。文字列をB進数と思って読んだらageと等しくなるBを答えてね。"問題を簡単にするために"、Bは正の数であればなんでも、整数じゃなくてもいいことにするよ。そんなBが無いときは-1、複数あり得るときは-2を返すべし』
- "簡単にするために"って、「整数じゃないとだめ」だったらBを1から100まで試すだけで強烈に簡単なのに。ひどい。
- ええと、まずテストケース作成…
- しかし、-1 とか -2 が出るってどういう場合かそもそも見当もつかないぞ。
- 先に解き方ちょっと考えよう。
- 要するに、文字列を a[0]a[1]...a[n-1] とすると
- a[0] + B*a[1] + B^2*a[2] + ... + B^n-1 a[n-1] == age
- という方程式の正の解がBだ。
- n-1次方程式の解を求める？ぬぬぬ。これが250レベルなのか…？
- 意外と何かの範囲を全探索すれば解けたりしないかな。
- age以下の自然数全部
- age以下の自然数の平方根全部(a[odd]=0のとき)
- age以下の自然数の立方根全部(a[1,2 mod 3]=0のとき)
- ...
- だけ見れば十分とか
- いや、x^2+x=1 の解って黄金比だから(√5-1)/2とかだよね。無理。
- しかしそういう解き方する人いるかも。撃墜用に覚えておこう。
- なんだろう。多項式に解があるかどうかって微分して極大値極小値求めてその範囲でニュートン法とか…
- ええと、どういうグラフになるのか書いてみよう。
- a[0]はx軸(B軸？)に平行な定数関数で。y=0かy=1か。
- B*a[1]は原点を通って傾きa[1]の直線で
- B^2*a[2]は放物線で…
- あ
- なんだ
- これB>0の範囲で単調増加ではないか。
- 狭義単調増加なら、y=ageと交わるとしたら1点しかない。
- a[1],a[2],... が全部0だと定数関数になるから、a[0]=age で無い限り、交わらない。この場合 -1。
- というか、a[0]=ageの場合交わるというかピッタリグラフが一致するから、Bを何にしてもいいので、この場合が -2 か。
- あとは必ずy=ageの線と一カ所で交わるから、十分大きいBから二分探索していけば求まる。
- ん？本当に交わるか？
- ええと、a[0]意外に1の項があることを仮定しているので、Bを大きくすればいくらでも大きくなるから、B=0でageより下にいれば、必ずいつかは交わる。
- B=0でageより下にいれば？
- age=1, a[0]=1, ... のとき、B=0 でちょうどageと一致するけど…
- "111", 1 みたいな入力のとき。
- これって B=0 が答えでいいんだっけ。
- ええと… B は any strictly positive number と書いてある。
- これはダメだ。-1 を返さなくてはいけない。
- このケースを除くと、
- だから、B=0 とすれば確実にageを下から抑える。これでいい。
- 解法わかった！
- さてテストケース作る。
- まず
- あとは…文字列に leading zero はありかな？ありだな。例にも出てる。
- 全部 0 の文字列は…これもアリか。何も問題文に書いてない。
- s="000", 3
- s="00", 2
- s="000", 1
- s="0", 0。あ、age=0はないのか。なしなし。
- そもそもこのケースは答えはなんだ？Bをどうやっても0になるから、ageと等しくないから-1か。ふむ。
- 最後の一桁以外0の場合は特殊っぽいのだった。
- s="1", 1
- s="1", 2
- s="01", 1
- s="01", 2
- あと適当に長いの入れておこう。
- よし書こう。
- まず全部ゼロ"000...000"の場合と、"000...001" の場合は特殊処理。
- それ以外で、終わりが 1 でageが1の場合も特殊処理。
- あとは二分探索。二分探索は、解のある範囲を上下から挟むことを確実な初期値から始めて、範囲を狭めていきます
- 上限は…B=ageでいいかな。a[1]以降のどっかa[i]は1な場合を考えているから、そこでB^i*a[i]がかかるし。
- しかし、これでやると最悪100の50乗とかから始まるけど、doubleに入る気がしないぞ。
- やめよう。B=1,2,4,8,... を順に試してみてageを越えたらそこで二分探索に移ればいい。
- 下は、さっき考えた。特殊ケースを除いたら、B=0 なら ageより下にいるからこれでいい。
- というわけであとは二分探索を実装。
- できた。
- サンプル全部通った。
- submit。
1000開く
- もう20分もないけど、RankList見るとかなり高得点で1000解いてる人が多い。これは解ける問題だろうか？挑戦してみる
- 『1カ所辺が壊れているかもしれないグラフ上で、始点から終点に、壊れている辺を見つけたら引き返すなども考慮した上で最悪ケースにかかる時間が最小になるように移動してね』
- あー、似たような問題を見かけたことがあるけど解いたことがない
- 全然解き方パッと閃かないのだけど、上位陣には定番のパターンだから瞬殺できる類なのではないだろうか。
- だとすると自力で考えて間に合わせるのは苦しいかもしれない…
- 10分考えて無理だったら、250の撃墜ケースを練りに戻ろう。
- 考えた。全然思いつかない。ダメぽ。あとでちゃんと復習する。
チャレンジフェーズ
- の前に250用のデータを練る。
- 「全部ゼロ」を考えてなさそうなコードを見たら "00",3
- 「B=0」という答えを返しそうな状況で二分探索に突入してたら "11",1
- あ、二分探索終わったあとに B=0 なら -1 を返すみたいな、後で分岐している人がいるかも
- それって落とせないかな。B=1の1/50乗とか答えになるときに-1を返したら間違い。
- Bの最小値って幾つだろう
- ええと、
- "11111...111", 2
- "11111...110", 1
- 辺りが最小だよね。これは…B=0.5か。
- それより小さくはならないから、二分探索の後でゼロ判定しているコードは安全。通していい。
- というわけで撃墜祭り開幕！！！！
- さて、コードを開いてヤバそうだったら撃墜…
- と思って読んでいる間に、あれよあれよという間に自分とあと１人を除いて部屋の全員Challenge Succeededになってしまっている…！！！
- おいぃ
- その「あと１人」が全員Challengeして回っている本人だったので、これは落とせないだろうなあ。
- がっくり
感想
- このくらいハマる人が多そうな罠を見つけたら、ソース読まずにChallengeしてみてもいいのかな。
- 2回に1回より多く落とせればプラススコアなわけだし。ううむ。
- ところで、twitterにも書いたんですが、今回の250のようなのはとても好きだし、良い問題だと私は思うんです。
- 自分は
- (1) アルゴリズムの手順を思いつける／知っている
- (2) そのアルゴリズムが使える条件を確認できる／知っている
- (3) 実際の問題を、各アルゴリズムが使えるようなモデル/形に帰着できる
- のどれも等しく重要だと考えています。競技プログラミングとしても、実際に「役に立てる」時にも。
- が、どうも(1)を過剰に重視している人が多いように思うし、(3)はまだしも、(2)が他と比べて明示的に意識されることがとても少ないように感じる。
- で、今回のようなコーナーケースは、本質的には (2) と同じ事だと思うのですよね。
- 三分探索する前に関数が凸であることは当然確認するでしょう
- Dijkstra最短路する前に負の辺が存在しないことは当然確認するでしょう
- 割り算の / を書くたびに右オペランドが 0 にならないか常に戦々恐々とするでしょう
- …というのと同じだと思う。「なんで今自分が書いたコードはちゃんと全ての入力を処理できるのか」わかっている、意識している、ということをしていれば、少なくとも自分の経験で言えば、格段に考慮漏れは減ります。
- ※ 減ってこの程度かよ！というツッコミはアリです(^^;; 修行中…
- ※ 「プログラマが常に全てを意識するなんて疲れる！なんとかしろ！」という反論も当然で、その辺をなんとかする方法論を考えるとかも含めて(2)が重要だと思うなあ、という
- 「テストケースを必ず先に作る」とか「できるだけ変な条件分けとかが少なくなる、実装が楽な方針を突き詰めてから書き始める」とか自分はそのくらいのことしか考えていないですが
- あと、話それますが、doubleを使う問題で誤差を許容するというのは、「無限精度の完全に正確な実数で計算したとしたら通るアルゴリズムは、できる限り通す」のが目的であって、それ以上ではないんではないかと。無限精度で考えても間違ってるコードはやっぱり間違ってるんじゃないかなあ。
wataさんの解法を参考にして書いてみたもの。
typedef int vert;
typedef int cost;
typedef pair<cost,vert> edge;
typedef vector<edge> edges;
typedef vector<edges> graph;
static const cost INF = 0x12345678;
static const vert START = 0;
static const vert GOAL = 1;
class WarTransportation { public:
int messenger(int n, vector <string> highways)
{
return solve( parse(n, highways) );
}
graph parse(int n, vector <string> highways)
{
graph G(n);
string hi = accumulate(highways.begin(), highways.end(), string());
for(int i=0; i<hi.size(); )
{
int k = hi.find(',', i);
if( k == string::npos ) k = hi.size();
int a, b, c;
stringstream(hi.substr(i,k-i)) >> a >> b >> c;
G[a-1].push_back( edge(c,b-1) );
i = k+1;
}
return G;
}
int solve( const graph& G )
{
vector<cost> ukai;
for(int v=0; v<G.size(); ++v)
ukai.push_back( ukaiDist(G,v) );
cost L=0, R=99999999;
if( !reachable(G, ukai, R) ) return -1;
if( reachable(G, ukai, L) ) return 0;
while( R-L>1 )
(reachable(G, ukai, (L+R)/2) ? R : L) = (L+R)/2;
return R;
}
cost ukaiDist( const graph& G, vert v )
{
if( v == GOAL ) return 0;
if( G[v].size() == 0 ) return INF;
cost worst = 0;
for(int f=0; f<G[v].size(); ++f)
{
priority_queue< edge, vector<edge>, greater<edge> > Q;
set<vert> V;
V.insert(v);
for(int i=0; i<G[v].size(); ++i)
if( i != f )
Q.push( G[v][i] );
worst = max( worst, dijkstra(G,Q,V) );
}
return worst;
}
bool reachable( const graph& G, const vector<cost>& ukai, cost ukaiLimit )
{
priority_queue< edge, vector<edge>, greater<edge> > Q;
set<vert> V;
Q.push( edge(0,START) );
return dijkstra(G, Q, V, ukai, ukaiLimit) != INF;
}
cost dijkstra( const graph& G,
priority_queue< edge, vector<edge>, greater<edge> >& Q, set<vert>& V,
const vector<cost>& ukai=vector<cost>(), cost ukaiLimit=-1
) {
while( !Q.empty() )
{
cost c = Q.top().first;
vert v = Q.top().second;
Q.pop();
if( V.count(v) || (ukaiLimit>=0 && c+ukai[v]>ukaiLimit) )
continue;
if( v == GOAL )
return c;
V.insert(v);
for(int i=0; i<G[v].size(); ++i)
if( !V.count(G[v][i].second) )
Q.push( edge(c+G[v][i].first, G[v][i].second) );
}
return INF;
}
};
