cafelier@SRM

SRM455

SRM | 03:25 |

SRM455 の成績・ソース (要ログイン) : WA/-/- : さようなら2500

300開く

• 300, 550, 900 の構成だったので
  • 経験上、普段より難しい550は絶対解けない
  • 普段より簡単な 900 は解けることが多い
  • 普段より難しい 300 はかなり苦戦すると思うけど、さすがにLv1はなんとかなるだろう…
• と思って 300 → 900 の順に取りかかることに。550は捨てた。

• 『'0'のマスと'.'のマスがあるgrid(最大50×50)が与えられます。'0'だけを使って四角形の枠が作れるとそれがドーナツになります。ドーナツの中にドーナツの中に…で最大何重ドーナツが作れるでしょう』

• 以下、max(H,W)をNとして…
• えーと、とりあえず作れるドーナツ全部数えてみるかー
  • 全列挙＆テストは
    • 左上と右下のマスを全列挙 : O(N^4)
    • 全部辺上がゼロになってるかテスト : O(N)
    • 50^5 はもうこの時点でTLEっしょ
  • もーちょい賢く。O(N^4)ならやっていい。

• むむむむむむ…？

• むずかしい…

• ええー

• えーと、これだ。
  • 左上のマスを列挙 : O(N^2)
    • そこから右に延ばせる 0 の数を数える : O(N)
      • 右に延ばしてったそれぞれのマスから下に延ばせる0の数を数える : O(N)
    • 同じ事を下→右の順で延ばす場合でもやる
    • そのあとに、右下のマスを列挙。
    • (y,x)だったら、ここを右下にしてドーナツが作れるということは
    • 右にy行ったところから下にx延ばせる＆＆下にy行ったところから右にx延ばせる
    • これはさっき前計算しといた情報で判定可能。
• よし O(N^4)!!

• で？
• これやると最大ケースで130万個くらいドーナツ候補がでてくるんですが
• これ、dagの高さを求めるdpをまともにやると O(130万^2) だ
• これはダメだ…

• ドーナツ候補作る時に明らかに無駄なもの消しながら作れるかなあ。
• 他のドーナツと辺を共有しててしかも小さいやつとか
• いやいや、それは無駄じゃない。別口のドーナツに小さい方だけ入れる可能性が…

• うーむむ。

• そもそもさっきのドーナツ列挙
• 前処理を左上マス毎に毎回やるんじゃなくて、全部まとめてできるなあ
  • 各マスから、左右上下に延ばせる 0 の数を全部求めておく
    • O(N^3)
    • と思いきやDPっぽく上手い順番で計算すると O(N^2)
  • で、foreach(左上) foreach(右下) 上下左右にそれぞれそこまで延ばせればOK
  • これでO(N^4)。この方が綺麗だ。
• 書き直そう

• そんなことはどうでもいいし！ドーナツ列挙してそれでどうするんだ！

• 小さいドーナツから、それを覆うドーナツを列挙すると…
  • 左上角より左上から、右下角より右下から次のドーナツの角を探すので、
  • これは全体の半分くらいのスペース。
  • 半分くらいでは O(N^2) は揺るがない…だめだ…

• やばい残り20分しかない！
  • 550も900もあんまり解かれてないから、今から慌ててトライしても自分では絶対解けないな…
  • というか、300たくさんsubmitしてる人いるけど、
  • こんなん通るわけないし大撃墜祭りだよね。最悪でも撃墜ポイントで0点は免れられるはず…
  • というわけで300と心中しよう

• ドーナツ列挙するのがそもそもの間違いではないか。
  • そもそもk重にドーナツが配置された風景を心に思い浮かべる
  • これは
  • まんなかにたどり着くまでに必ずk回のドーナツ(0)を越えなければいけないということだ

• ということは、
  • 外側から、0を何回越えたらたどりつけるか？距離を全マスに対して求めたら、
  • その最大値が答えではないか？？

• なんかそれっぽい！
• いまいち自信ないけど時間ないしやるしかない！
  • ダイクストラダイクストラ
  • よしサンプルと自作最小＆最大ケース全部通った！submit！

• あーあと10分しかないけど、どうしよう。
• 一応他も問題だけ目を通しておくか

900開く

• グラフにinactiveなedgeとactiveなedgeがあって全部activeにしたいとかなんとか。
• 頂点とツリーの形、のペアを指定してその頂点から始まる指定形と同型なツリーの辺をスイッチできる？

• 問題文長いので適当にとばし読んでこの辺で飽きた
  • なんかこれ、同型部分木をハッシュかなんかで全列挙したらあとはxorでランプを最適に全部つける問題に帰着して終わりかなあ。
  • 同じ頂点から同型ツリーが複数ぶらさがってたりするとめんどいのか。

550開く

• とばし読みだけどたぶん
  • 辺の長さN(<=500000)の正三角形を辺の長さ1の正三角形に分割したような図形があります。この中に凸な六角形は何個ありますか
• だと思う。答えは mod 1000...007 で。

• O(N) か、せいぜい O(N log N) かー。
  • 上側の台形の作り方、下側の台形の作り方を線形時間のDPで数えて、掛け算…
  • 上の台形を選ぶと隙間をうめる平行四辺形の候補は定数通りしかないのでこれでなんとか…
  • でも上の台形の下底の長さがN通りあるからこれだとO(N^2)か…

300に戻って…

• わからんので残り5分は撃墜例作成に費やす
• ランダムでそこそこ解が大きくなるヤツ
• できた

撃墜タイム

• Chat Area のログから、念入りにテストして無さそうな人とレートとsubmitタイムの適当な加重平均で撃墜対象順序リストを作っておく。
• スタート！
  • １人目明らかにO(N^8)くらいしてる。撃墜！
  • ２人目明らかにO(N^8)くらいしてる。撃墜！
  • ３人目これもDFSとか書いてあるけど全探索だなあ。撃墜…失敗！あれー？
  • ４人目DPって書いてある。あれだろ、dagの高さのDP表だろ、これも撃墜…失敗！あれれれれー
• 落ち着いて見て回る
  • あーそうか、四角があたえられたときに、それにピッタリはまるドーナツがあればそれを使う、なければ、再帰的に上下左右どれか一列削った四角での最大値…
  • というDPなら 4*N^4 なのか…！
• なるほどなあ。頭いいなあ。
• ということは、上下左右削って4回再帰呼び出ししてる風味の解は正解だ。避けよう。
• あ、もう一人TLEっぽいの見つけた。撃墜！
• これで +100
• うーむ不用意に４人目に突っ込んでなければ…
• って、あれ、３人目はやっぱりDPっぽいことしてないからTLEするはずだぞ？
• うーむ
• あ、僕さっきランダムケースじゃなくて全部0のケース突っ込んでた！
• これはこの探索だと一番最初に通って以下全部枝刈りされるっぽい…
  • てことはランダムケース突っ込めばたぶん落とせる…
  • けどここでさらに -25点 したくないなあ
  • うーむ

• あー時間だ

感想

• 結局自分のはおちてました

00000
0...0
00 00
.0.0.
.000.

• とか、ドーナツ作れるわけないけど 0 越えは必要だ…そりゃそうだ…
• もう今度から300も捨てようかな…