ARC115 参加記録
- 3完0ペナ 67分でした。
- 体感的には B < C < A <<< D でした。
A - Two Choices
最初は の制約を見て、正解列を bit 全探索して固定させ、各生徒の正解数をチェックするのかと思いましたが、計算量が となり間に合いません。
他の解き方を考えようとしましたが何も思い浮かばなかったので 5分くらいで B問題へ。
戻ってきてから再度考え直して AC することができました。どのような回答状況だと正解数を同じにすることができるか?を考えます。
サンプル1でも提示されていますが、二人の回答状況が00
と11
、01
と10
、10
と01
、00
と11
のときに正解をうまく選ぶことで正解数を同じにすることができます。
ここから、例えば 10101
と 00100
の正解数を同じにすることができるかを考えてみると、1問目と5問目は 11
と 00
で、2問目と4問目は同じ 00
であり、残りの3問目が1
で共通なため、正解数を同じにすることができます。
サンプルベースでの考察ですが、このように 1
が含まれる数の偶奇が等しい場合に正解数を同じにできるので、あとは組み合わせの計算を行うことで答えを求めることができます。
B - Plus Matrix
行列の要素が で作られるので、列 を固定して適当な値 を決めると、 として各 を求めることができます。
は非負整数なので、 の中で最も小さな値を として計算し始めると問題なさそうです。
あとは求めた を使って、全ての で が成り立っていることを確かめて答えとしました。成り立たない場合は No
を出します。
C - NColoring
が の約数ならば、 が成り立つように数列を構成します。またその数列に現れる値の最大値が最小になるように作ります。
から順に小さい値を振っていくことを考えます。例えば の場合を考えてみると、 は 以上全ての整数の約数になっているので、
1 2 2 2 2 2 2 2 2 2 2 2
のような数列が作れます。 は、「 以上の全ての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 にする : :
このような方針で埋めていくと数列に現れる値の最大値が最小となるように作ることができます。
この作り方は、素因数分解を高速に行うエラトステネスの篩のアルゴリズムに似てるので、そちらも参考になるかと思います。