CODE FESTIVAL 2017 qual A D: Four Coloring

競技プログラミング 競技プログラミング/AtCoder

D - Four Coloring

解き方

  • 45度回転してマンハッタン距離の代わりにチェビシェフ距離を使えるようにして、d*dの正方形ごとに色をかえる

ハマったところ

  • 45度回転する考えがそもそもなかった
    • 要するにチェビシェフ距離が扱いやすいので、できるだけこれに変換する、という話なんだと理解している

github.com

ABC075 D: Axis-Parallel Rectangle

競技プログラミング 競技プログラミング/AtCoder

D - Axis-Parallel Rectangle

解き方

  • 長方形の頂点のx座標、y座標はいずれかの点のx座標、y座標と等しいと考えて問題ないので全探索

ハマったところ

  • 全体でO(N^5)だったのでいけるか不安だったが、TLEはしなかった。

github.com

ABC075 C: Bridges

競技プログラミング/AtCoder 競技プログラミング アルゴリズム/深さ優先探索 データ構造/グラフ

C - Bridge

解き方

  • DFSして橋を数える

ハマったところ

github.com

DDCC2017 Qual C: 収納

競技プログラミング 競技プログラミング/AtCoder

ddcc2017-qual.contest.atcoder.jp

解き方

  • 最長の鉛筆をまず箱に入れて、もし入るなら最短の鉛筆も入れる。これを繰り返して個数を求める

ハマったところ

  • 最長の鉛筆と入れられる最長の鉛筆を入れるようにしたら、TLEした
    • 後者を求める時に、配列の要素削除などでO(n)になっていた

github.com