DDCC2019予選

A - チップ・ストーリー 〜無色編〜

まあやるだけなのでfor文を書いて提出したが、B問題を読み始めようというときに「シフトで行けた!」と気づき、シフトを使えなかったことを悔いて20秒くらい過ぎた。

B - チップ・ストーリー 〜漆黒編〜

難しそうだ。そうはいってもBだからやるだけなのではとか思ったけど思いつかない。ABCじゃないね。とりあえず簡単そうなNが偶数のケースから。サンプルと手計算を合わせて傾向を見る。等差数列、になるわけない。2乗のオーダーだよボケてるな。2乗だけどN^2の定数倍ではない。図をよく見ると三角数だ。次に奇数。これは相当難しそう。サンプルに2つあるので、5まで手計算して傾向を見るがわからない。サンプルと図とにらめっこする。各マスの四隅が黒い正方形に含まれるかわかればよさそう。そして、中心からのマンハッタン距離(名前がチェビシェフ距離とどっちだかわからなかったので考えづらかった)が一定以下で判定できると気づいた。ということで方針転換。ここまでわかればやるだけなので頑張って書いた。最初に見えた方針を捨てることによる時間のロスが多い。なんともならないのかもしれないけど。

C - チップ・ストーリー 〜白銀編〜

難しそうだけどまあ400点なのでね。たとえばP_1がNだとQ_iは全部1でないといけない。ということで、最大値をN通り試す方針が浮かぶ。ただ、最大値がどう出現するかでかなりの場合分けというか難しい何かが生えそうで怖気づく。最大値じゃなくてもある数以下ならいいことにする?いや、PとQで影響しあうからなあ。しばらくして、端っこから決めていけばよさそうだと気づく。こんなには上手くいかないという感覚だったけど、これでできてしまうようだ。最大値が最初に出現する位置で場合分けする。一応計算量にも気を遣って、毎回全部は計算しないように。改めてソースを見ると計算量を10倍勘違いしてたな(気を遣う必要なかった)。今気づいたが、要らん処理を消して提出したつもりが、コピペの段階で更新せずに出してしまった。これで最低限の結果は残した(といつも安心しちゃうのがよくない)。

D - チップ・ストーリー 〜黄金編〜

定まるわけないじゃんと思うような問題設定。少しして、各桁の和というと3の倍数の判定があるなと。この問題の文脈でいうと9の倍数だ。B進法のとき、秘密の整数とa_Bがmod B-1で一致する。となると中国剰余定理。わからないので困る。これをきっかけに勉強できたらいいかなとか考え始める。Wikipediaを読んで「(素数p0,p1でやるとき)結局、解はp0*p1おきに現れるよな」と思い、この微かな希望を具現化する。30までにけっこうな数の素数があるので、素数だけで絞ってから10^12以下を全検できると思った(具体的な計算量は計算してない)。30未満の素数回だけループすれば解が見つかる保証があるはずなので、絞り込み(具体的には、最小の解といくつおきに解があるかの情報を更新していく)の計算量はかなり小さい。10^12に30とかかけてもオーバーフローにはまだ余裕があることを確認。入力を逆向きに受け取ってたりしてたが、直してサンプルが合ったので提出。AC!
全完。これは嬉しい。ブログを書く時間が余ったのが感激だ。