3匹の猫

みみねこの競プロ精進メモ

AtCoder Regular Contest 115参加記(~C問題)

Aがわからない状態でウンコする最悪ムーブ
f:id:mmnkblog:20210322053311p:plain

A - Two Choices

この問題いつみても解けません。マジで苦手です。解説頑張って書こうとしたけど何もまとまりません。ごめんなさい。
愚直に解こうとするとO(N^2)なので何かしらの工夫が必要というところはわかりました。逆に言うとそれ以外なにもわかってません。(ブログ公開が遅れたのもこの問題のせい)

AtCoderの公式YouTubeチャンネルにあがっているすぬけさんの解説がわかりやすかったですが、あの解説を文章で書けないです。解説目当てで来た人はこちらを見てください。
youtu.be

B - Plus Matrix

100マス計算の内側から外側を復元できるか?という問題。

まずは判定問題を考える。
Aの各要素が定数だと仮定すると、行列CよりBも一意に定まる。これを言い換えれば、行列Ci行目の各要素からA_iを引けば、すべての行はBに一致するということである。つまり、もし解を構成できるならば、C_{i, j}からC_{i, j+1}までの増分をK_{i, j}として書き出すと、各行の増分は等しくなる(K_{i, j} = K_{i', j})。逆に、各行の増分が等しいなら、先ほどの議論よりABが存在することが言える。ただしこのままだと負整数も要素に含まれているので、数列の最小値を引いて0以上にする必要がある。

計算量は、O(N^2)

C - ℕ Coloring

こういう、2つの要素間に条件が発生するような問題は、N頂点の無向グラフを考えると良い性質が見えることがある。

i番目の頂点に整数iを書き込み、ijの約数なら頂点ijに辺を張る。このとき、問題文の条件は
「辺で結ばれた2頂点に異なる色を塗る必要があるときの、使用する色の数の最小化(とその色の塗り方)」
ということができる。これはグラフの彩色問題と呼ばれる有名な問題だが、NP困難(効率的に解くアルゴリズムが知られていないという意味のはず)の問題である。ということは、辺の貼られ方に特徴があるはずだ。

頂点1を最小の正整数である色1で塗ることとする。
頂点1は他の全ての頂点と隣接しているので、他の頂点が色1で塗られることはない。頂点2と頂点3は隣接していないので、それぞれの頂点を色2で塗る。この時、頂点2を除く2の倍数の頂点は色1でも色2でも塗れないことがわかる。3の倍数に関しても同じ。2のべき乗の頂点だけ考えると、頂点4は色3で、頂点8は色4で、…という風に、指数の増加に比例して色の種類数も増えていく。
つまり、ある頂点nn=p^x\times q^y\times r^z\times \dotsという風に素因数分解できるとき、頂点nの色は\max(x, y, z, \dots) + 1であることがわかる。これをN以下の整数すべてに対して求めてやればよい。これは例えばエラトステネスの篩を用いた素因数分解などでO(N\log N)で解くことができる。

感想

A問題よりB問題やC問題の方が簡単だと思います