naoya_t@hatenablog

いわゆるチラシノウラであります

【祝】DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選【通過】

AtCoder Programming Contest

今年の本選にはコード部門に加え「装置実装部門」というのがあるらしく
なにそれ？
と思って参戦してみた
www.discoverychannel.jp

11/23(金祝) 21:00-22:30
いつもよりちょっと短い90分
（コンテストページはこちら）

4問目間に合わず3完110位…（22:38:44に4問目AC。あと10分あれば！）
1位〜109位までのお客様の中に2020年卒予定の学生さんが10人以上いらっしゃいましたら予選通過。
→通過しました。1/19(土)の本選「装置実装部門」でお会いしましょう。*1

A - チップ・ストーリー　～無色編～ (100)

*=4をN回
もちろん<<(2*N)でいいんだけど思考の流れに任せた
→AC 1:33
https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3645666

B - チップ・ストーリー　～漆黒編～ (200)

数式考えるの面倒くさいので愚直解

  • N×Nの正方形とする
    • ♢の各頂点は\frac{N}{2}が入る座標なのでintにできないけど\frac{1}{2}ならdoubleでも安全
  • 四辺の直線で不等式を立てて、NxN個の小さい正方形（1×1）それぞれの4隅がすべて♢の中にあるか確認する

→AC 8:37
https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3646307

C - チップ・ストーリー　～白銀編～ (400)

  • p_{max},q_{max}(=\frac{N}{p_{max}})を全て試した。
  • p_{max}側に1つ以上p_{max}が入っていることを保証する形で組み合わせを列挙。
    • p_{max}がいくつ入ってるかを1\le n\le 10まで、どこに入ってるかを_{10}C_nで、残りは自由に(p_{max}-1)^{10-n}
    • q側は自由にq_{max}^{10}
    • これらを（mod 10^9+7で）掛けて足すだけ

→AC 17:10
https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3646835
昨日ARC 102 Eを解いてたのがなんとなく役に立った。

解説読んだら、p_{max}が入っているやつの個数は (p_{max}以下が入ってるやつの個数) - (p_{max}-1以下が入ってるやつの個数) とな。これ他でも見たことあるし定石なのね。
書き直してみた→
https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3683981
17msが6msになった！

D - チップ・ストーリー　～黄金編～ (700)

2進法表記が abcdefgh としたとき、「2進法のときの各桁の和」と「4進法のときの各桁の和」から、(a+c+e+g), (b+d+f+h) それぞれの和がいくつかは連立方程式で求まる。
同様に 3進法9進法、4進法16進法、5進法25進法 の間でも求まる。
けど何の役にも立たね〜〜

ある自然数nについて、その各桁を足した和*2を3で割った余りはnそのものを3で割った余りに等しい、みたいなのあるよね。3とか9とか。
それって a[3] % 3、とか a[9] % 9 とかで求まるよね（嘘）
これで30までの素数（2,3,5,7,11,13,17,19,23,29、で10個ある）について求めてGarner法*3でポン、で終わりじゃね？
→数あわないし、異様に小さい数しか出てこない*4

何でだろう
Garner法に投げ入れる前の a[3] %3 とかの値を見てみたら正答と整合性がとれてない。

あ
3進法における1の位が3で割った余りであって、それより上の位の数は要らない（し、a[3] % 3 では要らない数が混ざってくるから3で割った余りじゃない）

例えば、nの7進法表記が abc (=49a + 7b + c) だったとする。
これを3で割った余りは？49a+7b+c=(48+1)a+(6+1)b+(1)c = 3(16a+2b) + (a+b+c) だから各桁の数の和を3で割った余り、すなわちa[7]%3だ。
5進法だったら？
5進法表記が abc = 25a + 5b + c だったとする。
3で割った余りは... 25a+5b+c = (24+1)a+(3+2)b+c = 3(8a+b) + (a+2b+c) ... これだと簡単には求まらない。
4進法なら abc = 16a+4b+c = (15+1)a+(3+1)b+c = 3(5a+b) + (a+b+c) みたいに (a+b+c) が括り出せて既知の値 (a[4]) が使える。

あ、わかった
mod k に都合がいい (a+b+c) が括り出せるのは k+1 進法のとき、か
a[k+1] % k は常に nをkで割った余りなんだ

これをGarnerに…とかその時点では考えずに、さっきの素数を半分ぐらいずつ（いや7:3で）使って平方分割的に全探索で中国剰余を解いて
→AC 98:44
https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3648932

あと10分あれば、という結果だったけれど、予選通過の可能性がある110位につけられたのは悪くなかった。

Garner法に放り込む実装も試してみた

（コンテスト中に一度書きかけたコードから復元）
あれー？sample case3でinvalidが出る…Garner法の使い方（あるいは実装）が間違ってる？

→これはGarner法でsentinelに使う大きな素数が十分大きくなかったせいだった。答えの最大値 6469693230(=2*3*5*7*11*13*17*19*23*29) より大きな素数をsentinelに指定する必要があった。最初に試したときに「異様に小さい数しか出てこな」かったのはそのためだ。
全探索じゃなくてGarner法を使ったとしてもここではまって時間短縮はできなかったと思われる。

…というわけで、sentinel に 6469693291 を使い*5、sample case3でも正しい値が求まるようになった。
→AC
https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650496

*1:もちろんコード部門にも出ます。前回2017年のDDCC予選では82位で通過しながらも（1日のイベントはだるいからと）辞退していました。「装置実装部門」の訴求力の高さを感じさせます。

*2:10進法ね

*3:Garner法についてはけんちょん先生の中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiitaを参照されたし。

*4:後述

*5:自分で求めなくても、WolframAlphaさんに "primes between 6469693230 and 6469693530" とか聞くと教えてくれる。f:id:n4_t:20181124113331p:plain