コンテストURL
2完。くっそつらい。お前ぜってー水コーダーじゃねえだろって感じがした。あー、つら

C問題「Pyramid」

考察

コンテスト中の考察

N個の点から中心座標を求める感じかなー。
101× 101の配列を用意して、そこに入力で与えられた点を書き込む。1つの点に対して、そこから十字に同じ高さで埋めて...みたいなこと考えたけど無理だった（この時点でこの方針は捨てるべきだった）
考察はその先もあまり進まなかった。
順位表見たらDの方が解かれてるからDを見に行った（結局Dも解けなかったんですが...つら）

理想の考察

与えられた点を使って中心の点を求めたい。
与えられた点のみで中心の点を求める方法を考えてみる。けどこれは難しそう。具体的な方法が思いつかない
与えられた点からどの方向に中心点があるかわからない。なので、中心点を定めてやればいいのでは？とい発想になる。座標は$100 \times 100 = 10^4$だから中心点は全探索できそう。中心点を決め打てば、色々できそうだな～ってなる。

中心点の高さは与えられた点の高さよりも高くなる。なので、高さは「与えられた点の高さ＋そこから中心の点までのマンハッタン距離」で求めることができる。
この問題では高さは一意に定まるとされているので、与えられた点から求めた中心座標の高さが一意になればそれが答えとなる。
これでACできそうだけどWAになる（自分の実力では一発ACは厳しそう）
そこで、間違えてそうな部分を考える。すると、$h[i] = 0$のときが怪しそうだと気づく。
$h[i] = max(H-|X-C_x| - |Y-C_y|, 0)$という制約がある。これは、中心座標から見た座標$i$の高さがマイナス値になっても0として与えられることを示している。この辺が怪しそう。として与えられた点は、本当は$h[i] = -20$だったかもしれないし、$h[i] = -30$だったかもしれない。それを考えると、以下のような図が描ける。これは$h[i] = 0$のときの中心座標の高さの範囲は$1\leq H \leq |x_i - cx| + |y_i - cy|$であることを示している。

なので、この範囲内に入っている高さなら大丈夫そう。
与えられた座標から求めた中心座標の高さが1つに定まり、かつその高さが$h[i]=0$のときの範囲ないであればそれがこたえとなる（日本語壊れてる）

解法

$(cx, cy)$を全探索して中心座標を決め打つ。
与えられた$N$個の座標から、決め打った$(cx, cy)$の高さを求める。
求めた中心座標の高さについて、矛盾がないかを調べる。矛盾がない場合は、そのときの$(cx, cy)$と求めた高さが答えとなる。矛盾を調べる方法は以下のとおりである。
- $h[i] \geq 1$のとき、$(cx, cy)$の高さは$h[i] + |x_i - cx| + |y_i - cy|$となる。この高さを配列などに記録しておく
- $h[i] = 0$のとき、高さの値の範囲を更新する。$maxRange = min(maxRange, |x_i - cx| + |y_i - cy|)$みたいな感じで。
- そして、中心座標の値の候補が1つかつ、その値が高さの範囲を満たしているならそれが答えとなる。

コード

# include <bits/stdc++.h>
using namespace std;

# define int long long

int N;
int x[111], y[111], h[111];

// 中心座標の高さが求められたら高さを返す。求められなかったら-1を返す
int check(int cx, int cy) {
   set<int> cand;
   int Max = 1e10;
   for (int i = 0; i < N; i++) {
      int dist = abs(x[i] - cx) + abs(y[i] - cy); // 現在見ている座標から中心座標までの距離
      if (h[i] <= 0) {
         Max = min(Max, dist);
      } else {
         cand.insert(h[i]+dist);
      }
   }

   // 矛盾が無いなら中心座標の高さを返す
   if (cand.size() == 1 && *cand.begin() <= Max) {
      return *cand.begin();
   }

   return -1;
}

signed main() {
   // 入力
   cin >> N;
   for (int i = 0; i < N; i++) {
      cin >> x[i] >> y[i] >> h[i];
   }

   // 答えとなる(x, y, h)
   int ax = 0, ay = 0, ah = 0;

   // 多重ループを抜けやすくするためにラムダ式を使っている
   [&]() {
      // (cx, cy)を全列挙
      for (int cy = 0; cy <= 100; cy++) {
         for (int cx = 0; cx <= 100; cx++) {
            int t = check(cx, cy); // (cx, cy)が中心座標かどうかをcheck()で評価する
            if (t == -1) continue; // 返り値が-1なら処理を飛ばす

            // 答えが見つかった、変数に代入してループを抜ける
            ax = cx, ay = cy, ah = t;
            return;
         }
      }
   }();

   printf("%lld %lld %lld\n", ax, ay, ah); // 答えを出力

   return 0;
}

コード長くて複雑に見えるけどやってることは単純。$(cx, cy)$を全列挙して、それが正しい中心座標かチェックしていってるだけ。

要点

人間は複雑なことを考えられません
- 今考えている方針が複雑だったら、単純な方針になるように考え直すべき
- 考え直すと無駄に時間を使ったことになるためどうしても今考えている方針を手放せない気持ちになる。
- でも複雑で処理しきれなさそうなときはさっさと手放すべき。どうせ複雑な処理書けないし。
- 強い人もめちゃくちゃ複雑なことを考えてるんじゃ無くて、問題を単純にとらえるのが上手いだけだったりする。（まあガチで複雑なことを考える人もいそうですが）
全探索が基本
- これ忘れがち。
- ついつい賢い方法を試してしまう。賢くないくせにかっこつけるから解けないんだよバーカ。あー、つら。
式を見ろ
- 条件描いてある式、大体見づらいから読み飛ばす。
- 問題を解くためのカギになることもあるので、見逃さないようにする。

感想

$h[i] = max(式, 0)$っていう制約がこの問題を難しくしていたなーと感じた。なんなんだあの制約。マイナス使った方が現実的には絶対楽なのに...
なんで本番で解けるのかも、なんであの解説で理解できるのかも全く分からない。劣等感が半端ない。自分の頭が悪すぎてつらい。
質問すれば人々は答えてくれるけど有能な人間の時間を食いつぶしてるようで申し訳なくなる。あー、つら。質問に答えてくれた方、ありがとうございます...
この問題、理解に滅茶苦茶時間かけたんですが、ホンマつらい。
なんとなくわかったけど本番で解ける気がしねえ。

参考サイト

アルメリアさんのブログ

D問題「Partition」

考察

コンテスト中の考察

全探索しか思いつかない。
良い感じの式立てて、ループの回数調節してTLE逃れるやつをずっとやってた。最悪

理想の考察

$gcd(a[N])$を$k$とおく。
すると、$a_1, a_2, ... ,a_N = kx, ky, ..., kz(x, y, z \geq1)$となる。これは$a_i$が全て$k$の倍数である事を意味している。$k$は$a[N]$のGCDであるため、$a_i$の約数に$k$が含まれているのは当然のこととなる。
さらに、$M$も$k$の倍数である事が分かる。これは、$a_1, a_2, ... ,a_N = kx, ky, ..., kz=k(x+y+...+z)=M$と変換できることからも明らかである。
このことから、$M = tk(t \geq 1)$なので$k$は$M$の約数であることがわかる。
$k$がわかると、$k$を$N-1$個と$kb(b \geq 1)$を1個でGCDが$k$となる$a[N]$が完成する。
ここまで分かればあとは$M$の約数を列挙するだけとなる。$M$の約数は$O(\sqrt{M})$で出来る。

コード

# include <bits/stdc++.h>
using namespace std;

# define int long long

int N, M;

bool check(int n) {
   // 約数nをN-1個取ると、最後のひとつはMこの式になる
   int lastOne = M - (n * (N-1));
   // 最後のひとつが0より大きく、nの倍数であるならOK
   if (lastOne > 0 && lastOne % n == 0) {
      return true;
   }
   return false;
}

signed main() {
   cin >> N >> M;

   int ans = 1;
   // i, jはMの約数
   for (int i = 1; i*i <= M; i++) {
      if (M % i != 0) continue;

      int j = M / i;
      if (check(i)) {
         ans = max(ans, i);
      }
      if (check(j)) {
         ans = max(ans, j);
      }
   }

   cout << ans << endl;

   return 0;
}

解法

Mの約数を列挙する。それには、$1 \leq i \leq \sqrt{M}$の範囲でループを回す。
約数が条件に合うかを調べる。条件に合えば値を更新する。

要点

求めたいものを変数で置き換える
- 今回は、$gcd(a[N])$を$k$とおいた。これによって少し考えやすくなった。
$M$の約数は$O(\sqrt{M})$で列挙できる
- 素因数分解で列挙するのかなーとか考えてしまった
- これ前もやったことあるはずなのに普通に忘れててつらい。
- なんでこれでいいのかよく分かってない（最悪）

感想

chokudaiさんの解説放送わかりやすすぎる。
アレが一瞬で思いつけると良いなーと思う（思うだけ）