naoya_t@hatenablog

いわゆるチラシノウラであります

〈AGC埋め〉AGC B問題 (002 - 005)

AGC埋め

7月5日

AGC 002 B - Box and Ball (400)

  • 最初、それぞれの箱の赤玉率を求めるみたいな問題と思って考え始めたけど
  • いやそうじゃない、赤玉がある or not
  • なので移動が起こるたびに伝染する
  • 空になったらリセットしないといけない(ということに気づかせてくれるサンプルケースが親切だ)
  • Python2で投稿しちゃってRE(1)

→AC 11’52
https://beta.atcoder.jp/contests/agc002/submissions/2792529

解説解も同様

AGC 003 B - Simplified mahjong (400)

  • DP : 端からペアリングしていって、iの時点で1つ残っている / 1つも残っていない場合の最大ペアリング数

→AC 25’25
https://beta.atcoder.jp/contests/agc003/submissions/2792626

解説読む
  • Ai=0で分断されていない区間について、その区間の合計がSならfloor(S/2)ペア、とな
  • 貪欲にペアリングしていけばいいだけの話、なのか
  • 駄目だ、これ自明に見えない…解説の証明が頭に入ってこない…
    • 端からi=iのペアを作って行って、余ったら次に1つ繰越し、みたいなことか。ああ

7月10日

AGC 004 B - Colorful Slimes (400)

  • シフトの最大許容回数を決め打ち(0..N-1)
  • すべての色について、許容シフト内の最安値(1つずつ左を見ていく)で買う
  • その合計+シフトの所要時間、の最小値が答え
  • シフト回数をインクリメントしながら(時刻を遡りながら)最安値更新してO(N^2)

→AC
https://beta.atcoder.jp/contests/agc004/submissions/2822075

解説解も同様

AGC 005 B - Minimum Sum (40)

  • 最小がkになる区間がいくつあるか数え(c個あるとする)、ckを足していく
  • kを含む区間を見つけたらkの前後に分割していく。
    • 最小がkになる区間の数 = f(kを含む区間) - f(kの前) - f(kの後)
    • f(n) = n(n+1)/2
  • 区間はset<pair<int,int>>で
    • O(NlogN)

→AC 54'18 // 方針は良かったけど時間かかりすぎ
https://beta.atcoder.jp/contests/agc005/submissions/2822310

解説読んだ

  • Nから降順に
  • a_iより小さい数を含まない左限と右限を見つけるのにsetを使ってる
  • 今まで見てきた数(の位置)をsetに入れながら、a_i以上の数が占める位置だけから成る空間で
    • ある数未満の値が入らない最遠を探すのO(logN)では無理では?
    • 昇順じゃないとO(logN)は無理だよねやっぱ(日本語の解説が間違ってるのでは。英語は大丈夫)

自分の解法でいうところの分割位置だけをsetに入れていって、次の数をそこに入れたときに左と右に来る(それ未満の)数の位置がどこかをlogNで調べれば、左右それぞれそこより手前は次の数が最小になる領土。