cafelier@SRM

SRM452

SRM | 23:18 |

SRM452 の成績・ソース (要ログイン) : AC/-/- : rng_58さんの出題だったらしい。面白かったけどむずかった…

500開く

• 『IとOと?が2500文字以下並んだ文字列が与えられます。?を全部IかOで埋めたときに、等間隔で I...O...I となる部分が１カ所でもあるような埋め方は何通り？』
  • 答えは mod 1000000007 で

• DPぽい？
• 左から埋めてって、埋め方の状態毎に可能なパターン数をメモして…
• うむむ、これだと左にあるIの位置が一カ所でも違うと右のIの置け方かわるから、全然メモで探索が共通化されない…

• 二カ所固定すると残りの一カ所は決まるから、"最左のIOI部分"の位置は高々2500*2500通り。
• それぞれについて、「そこが最左のIOIになるような埋め方」を数える…
• どんだけ頑張ってもさらに*2500くらい時間がかかる気がするぞ。むり。

• 最左とか考えなければ「そこがIOIになるような埋め方」なら？
  • 2^残りの?の数、だからこれなら簡単に求まるけど
  • 重複が。
  • 包除原理？2500*2500候補あるのに？無理だ

• まったくわからない
• スコアボード見てみた。こんだけ時間経ってるのに誰もまだ500解けてない。これは難しいと感じていい問題だ。

• IOI文字列のみを受理するオートマトンを考える
  • 非決定性オートマトンで2500状態くらいので受理できる
  • 決定化すると2500*2500状態くらい
  • これを使ってメモ化DPすれば…！解けるけど 2500*2500*2500 時間だ。これも無理だ。

• "IOIじゃない文字列"の方が決めやすいな
  • 左から?を埋めていくときに
    • I は自由に埋めていい
    • O を埋めるときは左のIの鏡像の位置は全部Oで埋める
  • と決めていける
• なんか意外とIOIじゃない方は(mod 100...007する間でもないくらい)少なかったりするんじゃないか
• それならそっちを求めて引き算

• ガリガリと愚直なバックトラック探索を書く
• はい "?"*2500 で終わりません
• ていうかそれ以外のケースでも全然答えが合わない

• ううむもう250を解く時間がない。諦めよう

250開く

• スコアボード見ると瞬殺してる人が結構いるなあ。
• 『W*Hのマス目に石を置いていきます。ユークリッド距離2の石ペアがあってはいけません。最大で何個置けますか』

• ユークリッド距離2というのは、横か縦に１個飛びの場合しかないな。

• むむ、わからん。置き方全探索？
  • W,H<=1000だ。それは無理だ。
  • なんで瞬殺してる人がいるんだ。

• greedyに左上から置けるとこ置いてっていいのかな？
  • うーむ、いいのかな。自信ないな。
  • 置けるところに置かなくても最適解を得られたとすると変形してgreedyに置けることに置く最適解にできる…という証明をできるか考えてみたけど、わからん。
  • 置けるところにあえて置かないと後で置ける場所が２カ所増えるし。

• えーと、１個飛びに影響があるんだから
• 0 mod 2 のマスと 1 mod 2 のマスへの石の置き方は完全に独立だ
• ということは、
  • x%2=0,y%2=0のマス目グループ
  • x%2=0,y%2=1のマス目グループ
  • x%2=1,y%2=0のマス目グループ
  • x%2=1,y%2=1のマス目グループ
• はそれぞれ独立して考えられる。
• しかもそれぞれ独立して考えると、１個飛びの置き方じゃなくて、「隣接してはいけない」の最大の置き方を考えればいい
• それは市松模様に置く場合が最大に決まっとる

• よし解けた
• 書いた。サンプル通った。submit!

• （500に戻るも結局分からないまま時間切れ。）

撃墜タイム

• なんでこんなたくさんの人が500サブミットできてるんだ。すげー。
• と思ったら僕がウインドウを開くや否や撃墜される人が多数発生
• みんな撃墜が早すぎるwww

• 500の残った解答は見てもよくわからないのでスルー
• 250を見ていく。greedyに埋めている人がいるぞ、これはいいのか…？
  • あれ、いいじゃん！自分の「当たり前に市松模様が最適だ」というのは要するに左上からgreedyに埋めていくのと同じだ。そりゃそうだ。うわあああああああああ

感想

• そう、だから、250は

bool stone[1000][1000] = {};
int cnt = 0;
for(int y=0; y<H; ++y)
  for(int x=0; x<W; ++x)
     if( (y-2<0 || !stone[y-2][x]) && (x-2<0 || !stone[y][x-2]) )
       ++cnt, stone[y][x]=true;

• これでいいんだよなあ。うわーうわー。
• 変な綺麗な計算式より遙かに、とっさにこれが書けるようになりたい。

• すっかり負け癖がついてるなあ。
• 年内に2400…いや2500に戻して年を越すことを目標としたい。