AtCoder Regular Contest 115参加記(~C問題)
Aがわからない状態でウンコする最悪ムーブ
A - Two Choices
この問題いつみても解けません。マジで苦手です。解説頑張って書こうとしたけど何もまとまりません。ごめんなさい。
愚直に解こうとするとなので何かしらの工夫が必要というところはわかりました。逆に言うとそれ以外なにもわかってません。(ブログ公開が遅れたのもこの問題のせい)
AtCoderの公式YouTubeチャンネルにあがっているすぬけさんの解説がわかりやすかったですが、あの解説を文章で書けないです。解説目当てで来た人はこちらを見てください。
youtu.be
B - Plus Matrix
100マス計算の内側から外側を復元できるか?という問題。
まずは判定問題を考える。
の各要素が定数だと仮定すると、行列よりも一意に定まる。これを言い換えれば、行列の行目の各要素からを引けば、すべての行はに一致するということである。つまり、もし解を構成できるならば、からまでの増分をとして書き出すと、各行の増分は等しくなる()。逆に、各行の増分が等しいなら、先ほどの議論よりとが存在することが言える。ただしこのままだと負整数も要素に含まれているので、数列の最小値を引いて0以上にする必要がある。
計算量は、。
C - ℕ Coloring
こういう、2つの要素間に条件が発生するような問題は、頂点の無向グラフを考えると良い性質が見えることがある。
番目の頂点に整数を書き込み、がの約数なら頂点とに辺を張る。このとき、問題文の条件は
「辺で結ばれた2頂点に異なる色を塗る必要があるときの、使用する色の数の最小化(とその色の塗り方)」
ということができる。これはグラフの彩色問題と呼ばれる有名な問題だが、NP困難(効率的に解くアルゴリズムが知られていないという意味のはず)の問題である。ということは、辺の貼られ方に特徴があるはずだ。
頂点を最小の正整数である色で塗ることとする。
頂点は他の全ての頂点と隣接しているので、他の頂点が色で塗られることはない。頂点と頂点は隣接していないので、それぞれの頂点を色で塗る。この時、頂点を除くの倍数の頂点は色でも色でも塗れないことがわかる。の倍数に関しても同じ。のべき乗の頂点だけ考えると、頂点は色で、頂点は色で、…という風に、指数の増加に比例して色の種類数も増えていく。
つまり、ある頂点がという風に素因数分解できるとき、頂点の色はであることがわかる。これを以下の整数すべてに対して求めてやればよい。これは例えばエラトステネスの篩を用いた素因数分解などでで解くことができる。
感想
A問題よりB問題やC問題の方が簡単だと思います