cafelier@SRM

SRM459

SRM | 03:46 |

SRM459 の成績・ソース (要ログイン) : AC/AC/- : 2問解けてるだけよしとする

500開く

• 『一番下のB段目にはB個の正の整数a[B][0..B-1]が並んでいます、一個上の段は、B-1個並んでいます。a[B-1][i]=a[B][i]+a[B][i+1] となっています。以下同様。段数Bと、一番上の段の数Tがわかっているときに、可能なパターン数を数えてね。mod 1000000009で。』
  • B, T ≦ 100万
  • とりあえず自作したコーナーケース
    • B=2, T=2 (最小)
    • B=100万, T=100万 (最大)

• 100万ということは線形時間の解があるということかな。
• あと mod 1000000009 ということはパターン数すごく多いので全部数え上げるような解は不可
  • あれ、普段って1000000007 じゃなったっけ。
  • 1000000009 というのは何か意味があるのだろうか。素数じゃないとかかな
  • とすると割り算が少し面倒。まあどっちでもいいや。
    • (※あとでチェックしてみたら素数だった)

• ええと…
• パターン数を pat[B][T] としよう。
  • 1段目はTに確定だから、2段目の分け方は (1,T-1), (2,T-2), ... のT-1通り
  • それぞれについて pat[B-1][1]*pat[B-1][T-1] + ... と和を取れば…
  • だめだなあ。3段目の真ん中とか、それより下は左と右で共有されているので、
  • 独立にパターン数数えて掛け算だと、余計に数えすぎる

• ちょっとサンプルで様子をつかもう
  • B=3,T=5 では、{5}, {2 3}, {1 1 2} かその左右反転しかないらしい。
  • {5}, {1, 4}, ... は何故ダメなんだっけ。
  • あ、そうか、最下段も必ず正の整数を入れるので、1以上で、てことは下から2段目の数字は必ず2以上でないといけない、などなど
  • ふむ。
  • ということは、最低でも一番下に全部 1 を埋めた場合よりは T は大きくないといけない、と。
  • いくつだろう。
  • 一番左の1はtopに到達するまでに何回足されるかというと、1回。各列の一番左の数字にしか影響しないので。
  • 要は、その数字からtopまでの経路の数の分くらい足される
  • 要は、最下段のi番目の数字はtopに行くまでに nCi where n=B-1 回足される

• ということは問題は、
• 『a[0]*nC0 + a[1]*nCi + ... + a[n]*nCn = T となるようなa[0..n] は何通り？』
• という問題になるな。a[0..n] が最下段の数字。
• nC0 から nCn まで足すと 2^n なので、最低でもT >= 2^n でないといけない。
• そうじゃない場合は無条件で 0 を返す

if( T < (1<<n) ) return 0;

• ..あれ。nが100万くらい大きいときにオーバーフローして変なことになるな。
• (1<<n)が明らかに100万を超えるときはシフトしないですぐreturnしていい</li>
• えーと、24bitが1677万で、それを16で割っても100万越えてるから、20以上なら即returnでいいか

• というわけで、
• 『a[0]*nC0 + a[1]*nCi + ... + a[n]*nCn = T となるようなa[0..n] は何通り？ T≦100万、n＜20、a[i]≧1』
• という問題になりました。a[i]≧1よりa[i]≧0の方が楽そうなので
• 『a[0]*nC0 + a[1]*nCi + ... + a[n]*nCn = T-(1<<n) となるようなa[0..n] は何通り？ T≦100万、n＜20、a[i]≧0』</li>
• これは O(nT) くらいのDPでしょう。

• dp[k][s] を、「a[0]*nC0 + ... + a[k]+nCk = s となるような a[0..k] の数」とする
  • dp[n][T-(1<<n)] が答え。</li>
  • dp[-1][0] = 1, dp[-1][それ以外] = 0;
  • dp[k][s] = ...
    • a[k]が0になる作り方は、そこまででsが作れてるパターンの数だから、dp[k-1][s] 通り
    • a[k]が1の場合は、そこまででs-nCkが作れているところにnCkを一個足すのだから、dp[k-1][s-nCk] 通り
    • a[k]が2の場合は、dp[k-1][s-nCk*2] 通り
    • ...
    • Σ_i dp[k-1][s - nCk*i]

• これをそのまま実装すると
  • 埋めるdp表のエントリ数 = O(nT) 個
  • それぞれのところで Σ を取るのに O(T) 時間
  • O(nT^2)
  • これは間に合わない

• いや、でも、方針はあってるよねえ。
  • nC0 から始めるからΣのループに時間がかかるんで、
  • まんなかから初めていけば意外と時間かからんのでは。
  • 一番時間かかりそうな nC0 と nCn のところは、特別に式一発で計算できるし
• いやいや、こういうのはダメだ。ダメだと前回心に誓っただろう。考える。

• DPの表の依存関係を絵にしてみる…
• nCk = 2 だったとして、

dp[k-1] dp[k]
　□　　□
　□　　□
　■　　□← このマス
　□　　□
　■　　□

　　の値は、■のマスの値の和。

dp[k-1] dp[k]
　■　　□← このマス
　□　　□
　■　　□
　□　　□
　■　　□

　　の値は、■のマスの値の和。

• …あれ？ここで毎回馬鹿みたいにΣとらなくても、
• 自分の列dp[k]のnCk個下のエントリに横のを足せばいいんじゃね？

dp[k-1] dp[k]
　■　　□← このマス
　□　　□
　□　　■
　□　　□
　□　　□

• つまりこの２カ所の和でいい。
• これだ！よし！

• 実装…ええと、

long long memo[100万+α][30];

• ガリガリ
• あれ、一個前の列だけ覚えときゃいいんだから、2次元配列にしなくてもいいじゃん。
• 書き直し書き直し。
• できた。
• サンプル。テストケース通った。
• あ、最初に作ったテストケース、100万 & 100万は最悪ケースじゃないな。
  • T=100万、B=20 も追加。OK。

• submit！
  • あ、2次元配列つかったDPのコードは消したけど配列の宣言消し忘れてた
  • まあ、このくらいなら不要コードで怒られることもないでしょう。おーけーおけー

250開く

• 『"X < 100" みたいな形の、X と定数の大小比較の形の式がN個与えられます。できるだけ多くの式を満たすようにXを決めると何個満たせますか』
  • 式に出てくる数は整数だけどXは実数でもいいよ
  • N≦50
  • 追加したテストケース
    • {"X > 1000"}
    • {"X < 1"}*50

• (自然数, ＋, ×) の理論は決定不能なのに、(実数, ＋, ×) の理論は決定可能、なぜなら2次方程式の判別式みたいなのが必ず実数の範囲で書けるから（自然数だとかけないかもしれない）
  • みたいな話を使った話を最近読んでいたので、おおー、と思いながら問題を読んでました。
  • まあそんな難しい話はどうでもよくて
• それぞれの式を満たせる区間を数直線上に並べて一番多く重なってるところが解
  • 別にそれでも書けるけど250でそれはちょっと無いと思う。350くらい。
• X として調べればいい数は
  • 式に出てくる定数 C
  • 式に出てくる定数 C1 と C2 と中点 (C1+C2)/2
• くらいで、これ以外のところを調べても意味ないので、これを全探索すれば終わり。
• 50*50*50 くらい。

• 書けた。submit。
  • 定数の前後 ±0.5
  • そもそも定数の範囲が 0から1000らしいので、その範囲の0.5刻み全部
• とかでもよかったかもしれない。まあいいや。

1000開く

• 『N人チームとM人チームの間で総当たり戦をやります。最小の時間で全部終わらせられるようにするスケジュールを求めて。辞書順最小で。』
  • たとえば 3人チーム{A,B,C] vs 3人チーム{1,2,3} だと、
  • 1回戦: A-1 B-2 C-3
  • 2回戦: A-2 B-3 C-1
  • 3回戦: A-3 B-1 C-2
  • と当てれば3ステップで全組み合わせが終わる。これを最小に。

• むう？辞書順最小になるようにグリーディーに、先頭の方のチームメンバからガンガン割り当てていくだけではないのか？
• 5人チーム{A,B,C,D,E] vs 3人チーム{1,2,3}
• で貪欲に割り当てたら
  • 1回戦: A-1 B-2 C-3
  • 2回戦: A-2 B-3 C-1
  • 3回戦: A-3 B-1 C-2
• となってしまって5回では終わらない。これはどうしようもない。

• ううむ。
• あきらかに max(N,M) 回戦まででおわるだろーと思ってたけど
• 本当か？どうやって（辞書順気にしないでも）スケジュール組むのかわからない…

• …
• 全然わからん。何も思い浮かばない。

• 250と500の撃墜例でも考えておくか。
• 500に戻る。
• 最悪ケースって自分のでサーバで何秒くらいだろ。
  • test。1000000, 20、っと。ポチ。
  • …
  • サーバー様「SIGKILLが飛んで死にましたプギャー」
  • …
  • は？
  • はい？
  • long long memo[100万+α][30];
  • これか！これがメモリ制限オーバーしてるのか！
  • こんなもん使ってないよ。削除削除。再サブミット。
  • test。1000000, 20、っと。ポチ。
  • 通った。
  • 危ない…150点になってしまった…

感想

• 結局撃墜はできなかった
• 500のタイプのDPは今度からちゃんと一発で組めるように頑張ろう

SRM459 500

あとで | 03:46 |

• 改めて清書し直してみると綺麗に書けるものだなあ。
• この手のDPを線形時間で書くのが苦手なので克服しなければ。
  • このパターンが苦手であるとはっきり認識できたのでよかった
  • 次は迷わず解く

class NumberPyramids { public:
   int count(int baseLength, int top) 
   {
      const int n = baseLength-1;
      const int s = top - (1<<n);
      if( s<0 || n>20 )
         return 0;

      vector<int> dp(s+1, 0);
      dp[0] = 1;

      for(int i=0, nCi=1; i<=n; ++i, nCi=nCi*(n-i+1)/i)
         for(int x=nCi; x<=s; ++x)
            (dp[x] += dp[x-nCi]) %= 1000000009;

      return dp[s];
   }
};