Xenous の精進記録

AtCoder関連他、学習したことの記録です。

ARC115 参加記録

  • 3完0ペナ 67分でした。
  • 体感的には B < C < A <<< D でした。

A - Two Choices

最初は  1 \leq M \leq 20 の制約を見て、正解列を bit 全探索して固定させ、各生徒の正解数をチェックするのかと思いましたが、計算量が  O(2^{M}N) となり間に合いません。
他の解き方を考えようとしましたが何も思い浮かばなかったので 5分くらいで B問題へ。

戻ってきてから再度考え直して AC することができました。どのような回答状況だと正解数を同じにすることができるか?を考えます。
サンプル1でも提示されていますが、二人の回答状況が0011011010010011 のときに正解をうまく選ぶことで正解数を同じにすることができます。
ここから、例えば 1010100100 の正解数を同じにすることができるかを考えてみると、1問目と5問目は 1100 で、2問目と4問目は同じ 00 であり、残りの3問目が1で共通なため、正解数を同じにすることができます。
サンプルベースでの考察ですが、このように 1 が含まれる数の偶奇が等しい場合に正解数を同じにできるので、あとは組み合わせの計算を行うことで答えを求めることができます。

B - Plus Matrix

行列の要素が  C _ {ij} = A_i + B_j で作られるので、列  j を固定して適当な値  b を決めると、 A_i = C _ {ij} - b として各  A_i を求めることができます。
 A_i, B_j は非負整数なので、 B_j の中で最も小さな値を  0 として計算し始めると問題なさそうです。
あとは求めた  A_i, B_j を使って、全ての  i, j C _ {ij} = A_i + B_j が成り立っていることを確かめて答えとしました。成り立たない場合は No を出します。

C - NColoring

 i j の約数ならば、 A_i \neq A_j が成り立つように数列を構成します。またその数列に現れる値の最大値が最小になるように作ります。
 1 から順に小さい値を振っていくことを考えます。例えば  N = 12 の場合を考えてみると、 1 2 以上全ての整数の約数になっているので、

1 2 2 2 2 2 2 2 2 2 2 2

のような数列が作れます。 2 は、「 4 以上の全ての2の倍数」の約数に(当然)なっているので、

1 2 2 3 2 3 2 3 2 3 2 3

となります。
同じ要領で続けていくと、以下のように数列が変化していきます。

1 2 2 3 2 3 3 3 2 3 2 3   # 3番目は2.   6, 9, 12 番目を 3 にする
1 2 2 3 2 3 3 4 3 3 3 4   # 4番目は3.   8, 12番目を 4 にする
1 2 2 3 2 3 3 4 3 3 3 4   # 5番目は2.   10番目を 3 にする
1 2 2 3 2 3 3 4 3 3 3 4   # 6番目は3.   12番目を 4 にする
:
:

このような方針で埋めていくと数列に現れる値の最大値が最小となるように作ることができます。
この作り方は、素因数分解を高速に行うエラトステネスの篩のアルゴリズムに似てるので、そちらも参考になるかと思います。