けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

マンハッタン距離

AtCoder ABC 127 E - Cell Distance (500 点)

何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…

全国統一プログラミング王決定戦 本選 C - Come Together (300 点)

こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…

Tenka1 2018 E - Equilateral (700 点)

素直な問題だったけど、重たかった 問題へのリンク 問題概要 のグリッドが与えられる。各マスには白黒で塗られている。 黒マスの 3 つ組であって、それがマンハッタン距離の意味で正三角形になっているようなものが何個あるか数え上げよ。 制約 考えたこと …

AtCoder ARC 103 D - Robot Arms (600 点)

くやしい 問題へのリンク 問題概要 個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて (), (), (), () をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。 各 について共通の を用いなければな…