kmjp's blog

競技プログラミング参加記です

高難易度帯ポイントおさらい : ARC011~ARC020

ここら辺は時々本番全完している。

AtCoder ARC #011 : D - きつねさんからの挑戦状 - kmjp's blog

  • 本番は非想定解法によるゴリ押しで通してしまった回。
  • 最寄りの点や線からの距離を最大化しようとすると、自然とボロノイ図が出てくる。
  • ボロノイ図そのものを求める問題はそうそう出てこない。
  • ただ頂点間の垂直二等分線の集合はボロノイ図を含むことになる、というのは覚えておいてよさそうだ。

AtCoder ARC #012 : D - Don't worry. Be Together - kmjp's blog

  • 二項係数の組み合わせのパターンは色々あるので覚えておかないとなぁ。

AtCoder ARC #013 : D - 切り分けできるかな? - kmjp's blog

  • 限られたリソースで多様な組み合わせを作る、という話が出てきたら最大フローを疑う。

AtCoder ARC #014 : D - grepマスター - kmjp's blog

  • これは本番もさほど困らなかったしまぁいいか。

AtCoder ARC #015 : D - きんいろクッキー - kmjp's blog

  • ARC初優勝回でした。
  • 同じことを繰り返す確率系の問題では、等比数列の和を考えるといいことがある。

AtCoder ARC #016 : D - 軍艦ゲーム - kmjp's blog

  • 確率や期待値を最大・最小化する問題で、「初期状態に戻る」という選択肢がある場合、解の二分探索をすることで解の値を仮決めできるので「初期状態に戻る」選択肢が有効か無効か判定できるようになる。

AtCoder ARC #017 : D - ARCたんクッキー - kmjp's blog

  • Segmentの代表値をGCDにする問題。今ならあまり迷わず解けるかな。

AtCoder ARC #018 : D - 僕は友達が少ない - kmjp's blog

  • 行列木定理を知っていますか、という問題。

AtCoder ARC #019 : D - ほんとうのたたかい - kmjp's blog

  • 構築ゲーは知見を他に活かしにくそう。

AtCoder ARC #020 : D - お菓子の国の旅行 - kmjp's blog

  • 一次元の数直線上を左右に移動する距離に関する問題は、同じ位置の移動回数をカウントすると良い場合がある。