SRM487 の成績・ソース (要ログイン) : AC/WA/AC : 綺麗なコードを書く綺麗なコードを書く綺麗なコードを書く
250開く
- 550-950を警戒して250から…ってそろそろこういうのやめた方がいいのではないだろうか俺は…と思いながら250から。
- 出たなウサギさん。
- 入力
k : int where 1≦k≦50
p : vector<int> where 1≦p[i]≦100万, 1≦|p|≦50
max Σ{ p[i]+p[j] | (i,j)∈S }
where S ⊆ {(i,j)∈[0..|p|)×[0..|p|) | i+k+1=j},
∀i ￢( (i,_)∈S ∧ (_,i)∈S )
- 50個以下の自然数列が与えられます。１匹のウサギさんはぴったりk個間を空けた二つのマスを占拠できます。ウサギさんが大量にやってきて被らないようにマスを占拠したとき、抑えたマスの数の和を最大化。
- で題意はあってるよね？
- 念入りにサンプルを確認。
- 合ってる。絵が丁寧で素晴らしい。
- で、どう解くか。
- 常に k 個空きで押さえるので、
- (1番とk+2番)の組と(k+2番と2k+4番)の組と…
- と、k+1 で割った余りが同じマス同士だけが干渉する
- 逆に言うと、k+1 で割った余りで別々のラインにまず分割して
int N = preference.size();
for(int s=0; s<=k && s<N; ++s)
{
vector<int> sub;
for(int i=s; i<N; i+=1+k)
sub.push_back( preference[i] );
- さて、このsubをどうしよう。
- k+1 ごとに分けたので、１匹のウサギさんは隣り合うマスを押さえられる、という状態に変わっている。すると
- 偶数だったら、全マス取れるから Σsub が答え
- 奇数だったら、どれか１個使えないから、えーと、Σsub - min(sub) が最適かな。最小値を使わない。
- 書いた
- サンプル合わない
- あれ？
- ええと…
- そうか、奇数だったらどれか１個使わないけど
不使使使使
使使不使使
使使使使不
- 隣り合ったペアを選ばないといけないので、↑のように、奇数番目のマスしか使わないことができない。
- これだ。
- というわけで最小値の代わりに奇数番目の最小値に。
- 解けた。
550開く
- 問題複雑だ…
- 『m 個の横に並んだマスを k 色のどれかで塗ります。ただし、隣同士は違う色で塗ります。また"a番目とb番目は同じ色"という制約が最大10個来ます。二人がこの制約に従って自由に塗ったときに、同じ色になるマスの個数の期待値は？』
- 1 ≦ m, k ≦10億
- 塗れない場合は -1 を返せ
- 制約に二度現れるマス番号はない。(i,_)∈L∧(_,i)∈L ってことはない
- m, k は線形時間でも間に合わない大きさなので「10個しか制約が来ない」が重要なんだな。
- きっと、実質ここだけ考えればいい系。
- まず苦手な期待値に入る前に、-1 を返す場合ってどういう場合か考えよう。
- k=1 なら…2マス以上あると塗れない
- k=2 なら、abababa... か bababab... の塗り方しかないので、
- 「奇数番目と偶数番目が同じ色」という制約があると塗れない。それ以外なら塗れる。
- 塗れる場合はどちらかの塗り方が等確率で選ばれるので、完全一致（mマス一致）か完全不一致、が五分五分。
- ということは答えは m/2 か。
- k=3 なら…必ず塗れるんじゃないだろうか、実は。
- そうでないと、塗れる塗れないの制約を満たすケースだけを上手く探索しながら期待値計算なんて無理そうだし。
- ちょっと具体例を作って考えてみよう。
ＡＢＣＡ
- これで、1番目と3番目は制約に使えないので、「どこかがＡである」とダイレクトには言えない…
ＡＢＣＡ？Ｂ？Ｃ
- と思いきや、このようにＢ？Ｃと挟めば間はＡしかない
- そしてＡ？Ｂの間はＣしかない…
- この２つを＝でつなぐと！
- (1,3) (2,6), (3,8), (4,7)
- これは３色で塗れないなあ。だめだ。
- うーむ。すると塗れるかどうか判定しないといけないのか。
- あ、ここで10個しか制約がないことが効いてくるのか
- 10頂点のグラフの彩色数を求めるのは、単純に探索しても時間は間に合った記憶がある（2004年ICPC愛媛大会G）
- 行ける
- (i,j)が同じ色という制約と(a,b)が同じ色、という制約と…の、制約を頂点とするグラフと考える
- それぞれに色を塗りたい
- ただし、「隣り合ってる」つまり |i-a|, |i-b|, |j-a|, |j-b| のどれかが 1 のペアは違う色にしないといけないから
- そこに辺を引く
- この制約マスを全て塗り終われば、残りのマスは、３色あれば順に両隣と違う色を選んでいけばいいので、あとは必ず塗れる。
- こうやって作ったグラフは何色で塗れるか？
- 普通に再帰で全探索。たかだか10色なので行けますよ。
- 書いた。
- サンプルは…よし、-1 のところは合った。
- あとは塗れる場合の期待値だ。
- まず制約が一切ない場合は？
- 3色と4色の場合で手計算してみる。m/k …かな？
- どのマスも確率 1/k で一致するから、それがm個。
- という計算に見えるけど…なんでだろう
- 制約がある場合…
- わからないけど、これ、全部 m/k でいい、となってないと
- mやkが効いてきてしまってとても解けないと思うんですが。
- サンプルも全部 m/k になってるし。
- いいやそれで。理由は分からないけど出しちゃえ！！！
950開く
- お、問題文短い
- 『「mの倍数ならmで割る」「そうでなければ1を足す」を繰り返して1になるまでのステップ数が n な自然数は何個？』
- なんとなく、コラッツ予想を思い出すなあ。
- そしてコラッツ予想のステップ数と言われると、コラッツ木 を描いてルートからの距離
- が思い浮かぶ。
- 描いてみよう。例として m=5 で…
- これのルート (1) からの距離が n のノード数を a[n] とすると
- (5) からの距離が n-1
- (4) からの距離が n-2
- (3) からの距離が n-3
- (2) からの距離が n-4
- なノードの数だから
- a[n] = a[n-1] + a[n-2] + a[n-3] + a[n-4]
- ですよね。このツリー再帰的な形をしてるから、それぞれの子ノードでのカウントは再帰的に a[] でいい
vector<int> a(n+1);
a[0] = 1;
for(int i=1; i<=n; ++i)
a[i] = a[i-1] + a[i-2] + ... + a[i-m+1];
return a[n];
- この a[i-1] から a[i-m+1] まで足すのは一見O(m)に見えるけど、これはこの手のDPのパターンで、和も同時に求めておけば
vector<int> a(n+1), s(n+1);
a[0] = s[0] = 1;
for(int i=1; i<=n; ++i) {
a[i] = s[i-1] - s[i-m];
s[i] = s[i-1] + a[i];
}
return a[n];
- こう、差１発で求まる。全体でO(n)。よしできた。
- 書いた。
- あれ？合わない。
- どうせ i-m+1 とかの +1 や -1 を間違えたんだろ、俺。よくやるし。
- 考え直そう。
- x の上には 5x, 5x-1, ..., 5x-4 があって、5x-5 はないわけだから
- 子供は m 人。
- s[i-1] - s[i-m] だと… m-1人しか足してない。ダメじゃん！
- 正しくは s[i-1] - s[i-m-1] だよ
- 直す
- あれ、でも、やっぱりさっきの絵、1の上には5から2の4人しか…？
- おおお
- 1 の所だけ特殊だ！
- 基本的には子供は m 人
- なので再帰的にはそのつもりで数える。
- a[n] = a[n-1] + ... + a[n-m]
- だけど、最後だけ a[n-m] の分は余分なので
- 引いて答える
撃墜タイム
- 550の3色で塗れないケースを準備
- でもあんまりsubmitしてる人いないな
- １人撃墜。３人取られたorz
