NIKKEI2019-2-QUAL E. Non-triangular Triplets

atcoder.jp

考察

• をそれぞれとしよう。

• 実験をして、の右辺はすべての要素になるのではないかと思う

• もし右辺にC以外の要素があるなら、の形の式があって、1つ目の式の左辺のCと2つ目の式のnot Cを交換しても条件を満たす。 これを繰り返せばすべての式の右辺をCの要素にできる
• とりあえず必要条件を考えてみる。A,Bの要素の和がCの要素の和より大きい時は明らかに不可能。この条件を整理するととなる。
• どうせ十分条件だろうと予想して(パチンコ)実験をしてみる。この条件をギリギリ満たすもので実験するとなにか見えそうなのででやってみる

(7, 10, 17)
(5, 11, 16)
(3, 12, 15)
(6,  8, 14)
(4,  9, 13)

• Aの方を2ずつ減らして、Bの方を1ずつ増やすことでCのほうを1ずつ減らすとなんかうまくハマりそう。実際に一般のK, Nでこの構築方法をしたときにうまく行くかを不等式評価してみると なんかうまく行く。Nが偶数の場合もほぼ同様にできることがわかる。

感想

序盤の考察ルートは良かった。十分条件っぽいのを見つけてからがただのパズルにしか見えない。(なにか典型構図がある？)

パズルはパチンコなので苦手

Submission

void solve() {
  int n, k;
  cin >> n >> k;
  if (n < 2 * k - 1) {
    cout << -1 << endl;
    return;
  }
  vector<int> a(n), b(n), c(n);
  for (int i = 0; i < (n + 1) / 2; i++) {
    a[i] = k + n - 1 - i * 2;
    b[i] = k + n + n / 2 + i;
    c[i] = k + 3 * n - 1 - i;
  }
  for (int i = 0; i < n / 2; i++) {
    a[i + (n + 1) / 2] = k + n - 2 - i * 2;
    b[i + (n + 1) / 2] = k + n + i;
    c[i + (n + 1) / 2] = k + 3 * n - 1 - (n + 1) / 2 - i;
  }
  for (int i = 0; i < n; i++) {
    cout << a[i] << ' ' << b[i] << ' ' << c[i] << endl;
  }
  return;
}