TopCoderの学習のお時間

■ [SRM]SRM536 20:59

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14728&rm=311896

• Coding
  • 250
    • たとえば単純に、正と負の要素がある、と考えたとき、まず負のやつだけを1つにまとめてから他とくっつけると良さそう
    • などのように考えていると、結局小さいものから順に2つずつくっつければ良いのでは、と直感する
    • 証明もやればできそうだし、他の人らも提出してるし、ということでさっと書いて提出してしまう
    • しばらく様子を見ていたが誰も再提出しないので大丈夫だろうと確信
  • 500
    • 頻度のグラフは左右対称な台形になる
    • 一番上の辺の位置と長さだけが分かっていれば更新していける
  • 1000
    • サイズが10^16なので、2進表記でバイナリーなあの感じでやるのだろう
    • 直感的には、何度も多項式を掛けていったら0の項がどんどん増えていきそうな気がするが
    • 試してみると、P^(2^N)のときに1になる項は、Pで1の項の次数を2^N倍したところのみだとわかる
    • ということで、P,P^2,P^4,... のうち必要なものを使うとすると、項が高々50個の多項式を高々50個くらい掛ける、と整理される
    • 単純にDPすると計算量50^50になってだめなので良い方法を考えていたが浮かばなかった
    • 残り10分切ったくらいの時点であきらめて枝刈り探索やっておくべきだった
• Challenge
  • 500で単純に平均を使っている人がいたので落とす
• System Test
  • 2問とも通った

• 244.86 + 375.22 + 0.00 + (50*1-25*0) = 670.08
• 29位/798人
• 2162->2256

念願のデュアルレッドコーダー

■ [SRM]SRM535 20:59

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=15037&rm=311769

• Coding
  • 250
    • √L/Gまで全部調べて2つの約数に分ければ良いというのがすぐ見えたので書く
    • 2つの約数が互いに素でないといけないこと、考えてるときは気にしてたけどコードを書くときには忘れてしまっていた
    • サンプルで拾われて良かった
  • 500
    • 計算量50*500万のDPを書いてしまった。提出してから最大ケース入れてMLEすることに気づく…
    • 計算量落ちないかなーと考えてたけど無理だった
• Challenge
  • 寝落ちしていた
  • 500は落とされた。部屋内の500をwataさんが落としまくっていた
• System Test
  • 250は通った

• 242.89 + 0.00 + 0.00 + (50*0-25*0) = 242.89
• 129位/900人
• 2131->2162

■ [SRM]SRM533 19:50

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421

• 250
  • 逆向きに、両端だけがある状態から1つずつ間を埋めていくと考えると区間DPが見えた
  • 真ん中に1つ置いたとき、左半分と右半分を独立して別々に考えられるというのがポイント
• 500
  • サンプルを見ていると、結局行・列ごとの偶奇だけで決まるのでは？　と思う
  • 必要性は証明できるが十分性がわからない
  • どうせ一筆書きの条件の「次数が奇数の頂点が0個か2個」というあの法則が関係してて大丈夫なんだろう
  • 提出した後で、自分で作った非連結の場合のテストを見返すと、期待値が間違っていることを発見…
  • 連結性の判定でミスがあったので再提出
• Challenge
  • 500で、横向きが先であることを考慮しておらず("#","#")でYESを返すのを1つ撃墜
• System Test
  • 2問とも通った

• 232.36 + 229.95 + 0.00 + (50*1-25*0) = 512.31
• 54位/848人
• 2043->2131

■ [SRM]SRM531 00:07

http://community.topcoder.com/stat?c=coder_room_stats&rd=14724&rm=311335&cr=22744421

• 300
  • 「全曲最低1度は使わないといけない」と「同じ曲はM曲以上離す」の両方の条件を考慮するのが難しそうだけど
  • 後者が満たされるときにどういうことになるかよく考えてみたら、連続したM個の曲は全て異なる、ということに気づく
  • なので、すでにA曲使っている状態の場合、次に未使用の曲を使う場合がN-A通り、すでに使っている曲を使う場合がA-M通り
  • という感じになって、dp[現在何曲目か][これまで何曲使ったか] というDPができる
    • 「A曲使っている状態」は、具体的にどの曲を使ったかは関係なくて何曲使ったかだけが重要で、それらは同一視して良いと気づくのも1つポイントかも
    • 確率の問題で線形性を考慮するときとどこか似ている
  • ここまではすぐ思いついたのだけど、変数の取り違えが多発してコーディングに時間がかかってしまった
  • たった10行くらいのコードでも1文字変数はだめなものだなあ
• 500
  • とりあえず、収束する場合は、Nターンシミュレーションすれば全ての通過しうるノードを通過するので十分なはず
  • というわけで、収束するか発散するかを判定するのが本題
  • 収束する場合は以下のケースに分かれる
    • 1匹しか生まない経路のみを通って自分に帰ってくる
    • 複数に分かれて、そのそれぞれが収束のループに入る
  • 後者の判定は大変なので、ひとまず前者の簡単なやつを見つけてから、徐々に"収束するノード"を伝搬させていく
  • 具体的には、収束性の判定をN個のノードそれぞれに対して行うのをN回繰り返す
    • ベルマンフォードっぽく
  • こうすることで、後者のパターンでもそのうち分岐先のノードの収束性がはっきりするので収束すると決定できる
• 1000
  • 強い人が多数1000から開いていたが、なかなか解かれていないので無理そうだなあと思いつつ一応読む
  • やっぱりすぐには何もわからないので閉じて500のテストをやる
• Challenge
  • 300で二項係数を計算しようとしてオーバーフローしている人がいたので落とした
• System Test
  • 300と500両方通った
  • 500で落ちてる人が意外といなくて（4/7がPassed）なかなか優秀な部屋だった

• 264.51 + 319.46 + 0.00 + (50*1-25*0) = 633.97
• 20位/791人
• 2045->2172

自己最高順位。

volatilityがぐんぐん上がる

■ [SRM]SRM529 19:35

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14722&rm=311123

• 250
  • やるだけゲー
  • サンプル通ったので提出したあと、手で1から50までテストケース作って動かしてみたら何カ所もミスってた…
  • 泣きながら再提出
  • 確かに、あまり賢くないミスりやすい実装ではあった
  • サイズ小さいから効率悪くても全探索で良いよねーというの、何回か出てきてるけどなかなか浮かびづらい
• 600
  • 擬似コード（？）を解析していくと、bag1を2から1つずつ増やしつつ、bag0(=N)を割り算してみて割り切れるまで続ける、というようなことをやっていることになる
  • 数えていくと、Nの1以外の最小の約数をPとして 1 + Σ[2<=i<P](1+4N+ceil(N/i)) + (1+3N+N/P) が答えだとわかる
  • けどNが大きな素数の場合O(N)になってTLEするので Σ(ceil(N/i)) の計算量を下げないといけない
  • N=13とかで書き出してみると、ceil(N/i)が2や3になるiはたくさんあるのでこいつらをまとめてやると良さそう
  • 一方、ceil(N/i)が大きな値になるとceil(N/i)として出現する数がまばらになってくるので、iについて一つずつ調べる
  • より具体的には、
    • ceil(N/i)<10^6までの場合は、ceil(N/i)==Mとなるiの数は ceil(N/(M-1))-ceil(N/M) みたいな式によって各Mに対してO(1)で求められる
    • N/i>=10^6の場合は、i<=N/10^6<=10^12/10^6==10^6 だから、iについてループ回して全部調べれば良い
  • というわけで O(√N) で計算できる
  • しかしNの最小の約数を探すところで、10^6未満の素数でしか調べていなかった関係で、10^12以下の最大の素数を与えると無限ループになってしまっていた…
  • そのほか、MODとるのを1箇所忘れていたり、平方分割するのを10^6じゃなく10^5にしてしまっていたりと細かいミスが
    • この2つはこの問題で落ちる原因になってたかどうかは微妙なとこだけど
• Challenge
  • 600と900が即落とされているのを尻目に250に集中
  • 落ちそうなのがない
  • 結局システムテストでも全員落ちてなかった
• System Test
  • 250は通った
  • 600は落ちた

• 161.79 + 0.00 + 0.00 + (50*0-25*0) = 161.79
• 497位/811人
• 2037->1953

やっぱり再提出可能なコンテストかどうかで戦い方全然違いますね。1発勝負難しい

最大の素数でテストしてないのはかなり致命的なミス。時間あったのに

■ [SRM]SRM526.5 01:37

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14762&rm=310932

• 250
  • 一番後ろが落とされる場合の回数を数えれば良いんじゃないの、と直感して約√N回のループを書く
  • サンプル通ったので提出
• 500
  • DPで外側のエリアから順に、0個積もる場合、1個積もる場合、…の確率を計算した。
  • そのままだと計算量50*10000*50*10000とかでダメだけど、極端に1箇所に何個も集まる場合の確率は無視できるだろうから途中で切り落とせないか？　と思っていた
  • がだめだった
• Challenge
  • 250で微妙に違う方針の人が多い。いまひとつどういうつもりのコードなのかわからない
  • +50しても順位的にあまりおいしくなさそうなので何もせず
• System Test
  • 250は通った
  • いまさらになって、この解法ではN-1個目が取り除かれた後にN個目が取り除かれる場合を考慮してない！　大丈夫なの!?　と気づく
  • 結果的に大丈夫だったわけですがかなり良くない

• 239.75 + 0.00 + 0.00 + (50*0-25*0) = 239.75
• 59位/614人
• 1933->2023

500は往年の毎回難問だった時代を思い起こさせる感じで良かった