cafelier@SRM

SRM447

SRM | 12:03 |

SRM447 の成績・ソース (要ログイン) : AC/AC/- : みんなrowにx、columnにyという変数名のインデックスでアクセスするのやめようぜ！！！

500開く

• 『AさんとBさんの友達の友達の友達の～関係が4ステップ以上になるように人を間引くには最低何人間引けばいいですか』
• 人数は全部で40人以下。

• 直接友達なケースはないらしいので
  • A-*-B になってる
  • A-*-*-B になってる
• の両方のケースを全部除けばいい
• A-C-B になってるCはとりあえず全部消さないとだめなので消す
• A-C-D-B になってるC,Dは…どっちか一方消せばいい
  • この「どっちか一方消せばいいペア」情報を全部集めてなんか最適解を求めればいいはず

• なんだろ。
  • C-D をエッジとするグラフを作って、全部の辺のをカバーするように点集合を選ぶ、最小点カバー
  • ってNP完全問題だっけ。40人までだから二分割して探索的なあれでなんとか解けるのか
  • 解けないなあ

• よく考えたら
  • A-*-B を最初に全部消してあるので
  • Aから距離1の皆さんとBから距離1の皆さんはdisjointだ
  • てことはさっきのグラフは2部グラフだ
  • 2部グラフのカバーは最大マッチングでありすなわち手元にライブラリがある

• 書いた
• 動かした
• サンプル通った
• submit

• サンプルみるといろんなケース含んでるからこれだけで大丈夫かな。次

250開く

• 『チェスのナイトを固定アルゴリズムで動かすときに何マス訪れられるか計算』

• アルゴリズム決め打たれてるので、探索とか考えずひたすらシミュレーションするだけ
• そういうコードを書いた
  • たまに気分転換に番兵とか置いてみるとやっぱり楽だなあ（普段は毎回範囲チェックするコードを書くことの方が多い）
• できた
• サンプル通った
• submit

• これも厳しいコーナーケースは特にないかなあ。テスト増やさなくても良さそう。
• というか、8x8固定だったのか。読んでなかった。

1000開く

• 疑似乱数入力だー
• 『1500x1500 のマス目が白黒に適当に塗られてます。100万点ほどマスが指定されるので、各マスごとに、そのマスを含む白い四角形の個数をスコアとします、スコアの総和を答えてね』

• 最初、そのマスを含む最大の白い四角形がスコアと勘違いしていろいろ考えてました
• distinct四角形の個数か

• 100万マスを処理しないといけないので
  • O(1) でスコアが求まるインデックスを作るか
  • 逆に、白い四角形を全列挙して、含まれている指定マスの個数をO(1)でカウントできるインデックスを作るか
    • 白い四角形全列挙って、1500^4 くらいあるんじゃなかろうか。却下

• DPみたいに全マスのスコア求まらないかな。
• 上のマスのスコアから下のマスのスコアがO(1)で求まればいい
  • 上のマスを囲む四角形のうち、そのマスが下辺に接してないものは全て下のマスを含む
  • 下のマスを囲む四角形のうち、そのマスが上辺に接してないものは全て上のマスを含む
• ので、score[下] = score[上]-score下接[上]+score上接[下]
• とかそんなんだ。一番上の列は左と右で同じような式で求める。一番右上は気合いとかで求める。

• 接してる四角形なら自由度が一つ落ちてるからなんとかならないかな。
• なにかRange Minimum Queryを使ってごにょごにょ…
  • 毎列RMQ用のインデックスを作るのは全部でO(N^2 logN)くらいでできるから計算量は足りる
  • あとは何とか四角の個数を…

• と、この辺で時間切れ

撃墜タイム

• ナイトの飛び方アルゴリズムは「次に行ける場所が一番少ないところに飛ぶ。同点の時はできるだけ低いrowに飛ぶ。さらに同点のときは出来るだけ低いcolumnに飛ぶ」だったんですけど、同点→x→y の優先度で飛んでる人がいる！と思って2回チャレンジして2回失敗。row=x、column=yで組んでる人だった。ぐあ

感想

• チャレンジ失敗してなくても60位とかその辺り止まりっぽかったので、まあ結果オーライかなあ。
• 500はもう5分速く解きたい。2部グラフに見えるのが遅すぎた