SRM469 の成績・ソース (要ログイン) : AC/WA/TLE : 苦手な感じの問題をドハマリせずに解けたと思いきやだめだった
500開く
- 『N本のホラー映画を見ます。それぞれ長さはlength[i]分あります。scary[i]分のところにビックリポイントがあります。初期状態は目覚め度+74で、1分につき1減ります。ビックリポイントにくると47増えます。目覚め度が-0.5を切ったら永遠の眠りにつきます。順番を工夫してできるだけ多くの映画を最後まで見たいので順番を考えてね。同点の場合は辞書順最小。』
- N≦20
- 0＜scary[i]:int＜length[i]:int≦474
- 最小ケースと最大ケースを適当に作成
- えーと、寝る寝ないのギリギリのラインをさまようケースが必要だな。
- -0.5 というのは…そうか、これは単に「0 なら寝ない、-1 なら寝てる」ということか
- length や scary は全部整数だから、映画が丁度おわった瞬間に寝るようなコーナーケースは考えなくていいということだ。
- さて
- N≦20 ということは O(2^N) か O(N 2^N) が間に合う。
- O(2^N) ということは、「今までみた映画の集合」みたいなのを状態として状態空間探索する感じかな。
- 「今まで見終わった映画の集合」が決まると
- そこまでに眠りさえしていなければ、目覚め度合いはどの順番で見ても同じだな。
- その目覚め度を m とする。
- その次にみられる映画は、
- ビックリポイントまでに寝ない
- つまり scary[i] ≦ m なもの
- 目覚め度 0 は寝てないので、ここは = が入る…
- かつ、ビックリポイントの後にも寝ない
- ええと…ビックリポイントの後ろはあと length[i] - scary[i] 分で
- そこで 47 加算されるんだから、
- length[i] - scary[i] ≦ m+47
- なもの、かな。（※: 間違い！）
- mについて整理すると
- max(scary[i], length[i]-scary[i]-47)≦m
- な映画だけ見始められる。
- この映画を見終わったあとの目覚めポイントは
- だな。この増分を inc[i] としよう。
- あとはこれで探索すればいいか。
- 辞書順最小の解が欲しいんだから、
- 見られる映画の内辞書順最小のものを最初に見る→再帰探索
- というループを回す
- 今までに見つかった解より真に長いものが見つかったら更新。
- で、「今までに見た映画集合」を覚えておいて、同じ状態に来たら辞書順最小解にはなりえないので即座にreturn。
- できた。これだ。O(N 2^N) か。
- コーディング中…
- よし完成。
- あれ、最悪ケース2秒くらいかかってる。危ない。
- メモをsetでやると重いのかなあ…
- vectorにした。今度は余裕のタイム。
- submit！
250開く
- スコア表見る限り、瞬殺ゲーム。心してかかろう。
- 『縦n×横m の映画館の座席があります。k箇所は埋まっています。空いているとこから2つ横に隣り合ってる席を取る取り方は何通り？』
- む？単にn*mの座席表作って埋めて探索するだけ？
- k≦47
- 1≦n,m≦10億
- 最小、最大テストケース作成
- あと3x3のマップでいろいろなパターンを手で計算して追加
- 関係ないけど、問題名の最初の方がどのレベルも一緒だと
- n,mがでかくてもkが小さいので、
- 埋まってる席がなかった場合の取り方 n*(m-1)
- から、埋まってせいでダメになかった座り方を引けばいい
- O(k) か O(k^2)では求まるでしょう…
- えーと、
- 埋まってる席のせいで隣あってとれなくなった席を数える
- k個の埋まってる席のリストのなかで隣り合ってるものを数えればいいのでは (※: 間違い)
- sort して、隣同士を比べて隣接してたら cnt++
- あれ、全然答え合わない
- って、なにやってるんだ俺、違うよ、全然違うよ
- (y,x) が埋まっていると、(y,x)-(y,x+1) という席の取り方と
- (y,x-1) (y,x) という席の取り方の二つを潰します。
- というわけで、set に (y,x) と (y,x-1) を insert する
- これを全部繰り返して set に入ってる要素数が、ダメになった席の取り方の総数
- できた
- あれ、まだなんか違う。
- 座席番号1オリジンか。0オリジンのつもりで書いてた。いかん。修正。
- よし通った。submit。
1000開く
- 『N本の映画のレビューを2人でやります。まずN本を順番に、一本ずつランダムに、J君とB君に割り振ります。各自、自分の担当分を先頭から順に消化していって、全部終わったら、相手の担当分に先頭から順に手を伸ばします。ただしここで、バランスの悪い割り振りをしていると相手に追いついてしまう。これを避ける割り振り方は何通りあるか』
- 各映画のレビューを終える速さは二人で違っていて、それぞれ j[i] 分とb[i]分
- N≦47
- j[i],b[i]:int ≦20
- 問題分を数式で整理しよう…
- J君担当分を a[1] a[2] ... a[k] とする
- B君担当分を a[k+1] ... a[N] とする
- 「J君がB君に追いついてしまう」というのは、
- (j[ a[1] ] + j[ a[2] ]+....+j[ a[k] ])+(j[ a[k+1] ]+...+j[ a[m] ]) よりも
- (b[ a[k+1] ]+...+b[ a[m] ]+b[ a[m+1] ]) の方が小さい
- J君はa[m]番目終わっちゃったけどB君a[m+1]終わってない！というときだ。
- 式を整理すると
- j[ a[1] ] + ... + j[ a[k] ] + (j-b)[ a[k+1] ] + ... + (j-b)[ a[m] ]) ＞ b[ a[m+1] ]
- こうならないような割り振り方…
- よりはこうなるような割り振り方を数えて引いた方が考えやすいか。
- 「全パターン数」 - 「J君がB君に追いつく」 - 「B君がJ君に追いつく」
- だ。
- 両方が両方に追いつくってパターンないよね？うん、ないね。
- まず全パターン数は…割り振り方は2^Nで、それぞれの並べ方が…階乗がなにか…
- あれ？問題文に全部で2^N通りって書いてある。
- あ、そうか、先頭から順に振っていって先頭から順に消化するのか。じゃあ2^Nだ。
- 解き方も、それなら先頭から割り振りを全部試すのでいいのでは。
- J君がB君に追いつくパターン
- j[ a[1] ] + ... + j[ a[k] ] + (j-b)[ a[k+1] ] + ... + (j-b)[ a[m] ]) ＞ b[ a[m+1] ]
- を考える。
- i番目の映画をJ君に割り振るなら、j+...+j の部分が増える
- B君に割り振るなら (j-b)[] + ... の部分が増える
- B君に割り振る場合そうして作った左辺が、最終的に b[] を越えてはいけないという制約が加わる。
- これを全部覚えて
- map<tuple<j...の部分の和, j-bの部分の和, 越えてはいけないb>, int>
- 先頭から47個わりふりを全部試す。
- 「～～の部分の和」は 47*20＜1000 だからそんなにパターン数無いはず。
- 最悪で数えると 1000*1000*47*α の計算量だからまずそうだけど
- 実際にはそこまで酷くならないと期待してGo。時間ないし
- かきかき
- 3分前にsample通った。えい、出しちゃえ。
- 手元で最悪ケース試す。
- 100秒くらいかかるなー
- 時間切れ
撃墜タイム
- 250でn*mするのに64bit整数を使ってない人がいるのは予想していなかった
- オーバーフローするケースを考える数秒の躊躇の間にとられた
感想
- 自分の500がsystem testで落とされる
- なんと？
- ソースを見なおすと…
- length[i] - scary[i] ≦ m+47
- ってなんだ
- でしょう！！！！！！！！！
- こういうバカみたいなミスが全然なくならないところに実力が現れているなあ…ひどい…
class TheMoviesLevelTwoDivOne { public:
vector <int> find(vector <int> length, vector <int> scary)
{
int N = length.size();
vector<int> lwb(N), inc(N);
for(int i=0; i<N; ++i)
if( scary[i]+47 < length[i] )
lwb[i] = length[i] - 47;
else
lwb[i] = scary[i];
for(int i=0; i<N; ++i)
inc[i] = 47 - length[i];
memo = vector<bool>(1<<N);
memo[(1<<N)-1] = true;
vector<int> temp;
rec(0, 74, N, lwb, inc, temp);
set<int> not_used;
for(int i=0; i<N; ++i) not_used.insert(i);
for(int i=0; i<result.size(); ++i)
not_used.erase(result[i]);
result.insert(result.end(), not_used.begin(), not_used.end());
return result;
}
vector<int> result;
vector<bool> memo;
void rec(int mask, int cur, int N, vector<int>& lwb, vector<int>& inc, vector<int>& temp)
{
if( result.size() < temp.size() )
result = temp;
if( memo[mask] )
return;
memo[mask] = true;
for(int i=0; i<N; ++i)
if( !(mask & (1<<i)) && cur>=lwb[i] )
{
temp.push_back(i);
rec(mask|(1<<i), cur+inc[i], N, lwb, inc, temp);
temp.pop_back();
}
}
};
class TheMoviesLevelThreeDivOne { public:
long long find(vector <int> timeJ, vector <int> timeB)
{
int N = timeJ.size();
return (1LL<<N) - quitJ(N, timeJ, timeB) - quitJ(N, timeB, timeJ);
}
LL quitJ(int N, vector<int>& J, vector<int>& B)
{
typedef pair<int,int> state;
typedef map<state, LL>::iterator iter;
map<pair<int,int>, LL> M;
M[state(0,-0x3fffffff)] = 1;
for(int i=0; i<N; ++i)
{
map<state, LL> M2;
for(iter it=M.begin(); it!=M.end(); ++it)
{
int sum = it->first.first;
int bound = it->first.second;
LL n = it->second;
M2[state(sum+J[i], bound-J[i])] += n;
M2[state(sum+J[i]-B[i], max(bound, B[i]-sum))] += n;
}
M2.swap(M);
}
LL cnt = 0;
for(iter it=M.begin(); it!=M.end(); ++it)
if( 0 < it->first.second )
cnt += it->second;
return cnt;
}
};
- Σ J[...] と Σ (J-B)[...] を別々に覚える必要はない
- 足しちゃってよい。
- あらためて整頓する。
- Σ_{0≦i＜N} f(i) ＜ timeB[x]
- where
- f(i) = timeJ[i] if "i-th movie goes to J"
- f(i) = timeJ[i]-timeB[i] if "i＜x" and "i-th movie goes to B"
- となる x が存在すると、J が B に追いついてしまう。
- このパターン数を全部数える。
- 上のソースコードで
- sum がだいたい Σ_{0≦i＜x} f(i)
- bound が timeB[x] - Σ_{0≦i＜N} f(i) の最大値
- n が sum と bound がそうなるパターン数
- 最終的に bound ＞ 0 なパターン数が答え
