2020/09/23に行われた秋分コンテストに参加した。
0時から16時までと、22時から24時まで頑張った。結果としては2338点で全体7位。
運営陣による解説ブログは次の通り。
秋分コンテストの問題解説 (tozangezan 担当分: NPQRSTUV) - tozangezan's diary
秋分コンテストの問題解説 (kagamiz 担当分) (ピクトセンスと絵しりとりの解答もあるよ) - Lilliput Steps
以下、各問題の感想を書く。
※問題名の横には、満点と自分が取れた点数を記載している。
A問題（0/200）
何もわからなかった。とりあえず114514とかそういう例の数字が入力に含まれていないか調べたところ、含まれていないらしい。なんで問題文はこんな口調なんだ？
多項式補完してみたけど、当然のように自然数が列をなして現れた。それはそうだね。
B問題（100/100）
なんでもいいと思って、サンプルの"Autumnal Equinox Contest"を出力したらWAになった。自分のアカウント名を出力したらACした。マジで草。
C問題（200/200）
絵を見て書いてある単語を当てる問題だが、出題範囲がリストになっていて、かなり狭い。（あとヒントで文字数がわかるのが嬉しい。）絵もそこそこきちんとしているため、満点を得ることができた。回答の一部を紹介する。
- 問7（ちきゅう）
丸しか書いていない。4文字の単語を上から下まで見て、丸いものを全部試した。
- 問9（きょくがくあせい）
まあそういうことするよね……。末尾が「い」の四字熟語は少ないし、どれが当てはまるかは一発でわかる。
- 問10（りゅうとうだび）
竜……？狐だろ。緑ければいいってものじゃない、というか体を描くのを待ってから回答してくれ。
- 問11（ひよくれんり）
男女なのはわかるので、それに関連する四字熟語を全部試した。
D問題（200/200）
重み付き無向グラフが与えられるので、頂点
38から出発して、頂点1から10をすべて訪れるのにかかるコストの最小値を求める。ただし、途中で頂点25を通ってはならない。また、2回だけコストを1/4にすることができる。
普通に難しい。最初はコストと最大値2つを持つダイクストラを書いたけど、まあそういうのはできないよね……。
結局、コストを1/4にする辺を全探索した。頂点番号の最大値がN=50だと決めつけ、訪れるべき頂点を1からK=10として、辺の数Mに対して O(2K NM(K+log N)+N2 3K) で解いた。さっきまでは頂点番号がintに収まらないんじゃないの？と疑ってmapとか使って書いていたが、計算量的にそんなことをしている余裕はない。
時間制限1 secに対してACコードは0.99 secだった。定数倍高速化が本当に厳しかった、と思っていたが、よく考えたらオーダーを改善してACしていた。コストを1/4にする辺を決めるとき、スタートから1本目、1本目から2本目……と計算するとオーダーにMが出現してしまい間に合わない。正解は、スタートから1本目と2本目から最後までを全探索したあとに組み合わせる。
E問題（300/300）
botに対して質問して問題文を探り当てる。botは「入力・問題・制約について聞く」→「特殊な応答をする（対応するモードに入る）」→「単語で聞く」→「答える（モードが終了する）」という動きをする。
まず入力の最大値を聞くと、66であるらしい。また応答文からOEISが関係していて、問いの数列が66項しかないことがわかる。次に問題文を聞きたいのだが、対応するモードに入るための質問文がわからない。結局「問題文に素数は含まれるか？」みたいなことを聞くと対応するモードに入ってくれることが分かったので、日本語通じてないけどこれで進めることにした。ちなみに、書いてる途中に試してみたけど入ってくれなかった。ACした瞬間タブ閉じちゃったので会話の内容はうろ覚え。
数列について聞くと、やはりOEISが関係していることがわかる。先ほどは黒塗りで4文字だったが、今はOとEくらいが見えていた。また、秋分に関係することもわかるので、次に秋分について聞くと、数列の番号が関係するらしい。
このあたりでA000922とかA200922を調べたところ、A200922が確かに66項の数列なので、これを出力して終わり。
途中で問題に素数が関係することも判明していたが、埋め込むだけなので使わなかった。
F問題（0/100）
何もわからなかった。通知のタブを見ればよかったらしいが、コンテスト中は一度も訪れなかった。これは誕生日コンテストに参加するものとしては失格。
G問題（42/100）
くそなぞなぞを解く。4問目は東京23区が答えであることがわかるので、全部試した。
H問題（100/100）
変体仮名。このサイトを見て頑張る。
2行目は＿なりあ＿ふ＿つのすう＿が＿＿いにそで……のように読める。これは復元できて、「隣り合う2つの数字が互いに素で」だ。
あとはエスパーする。1行目にNが、2行目にN項の数列が与えられると決めつけて、隣り合う数が互いに素なペアの個数を数えて出力したら通った。
I問題（0/100）
変体仮名の字母だと思って調べてみたのだが、全然埋まらない。自分の考えた読みを当てはめようともしたが、あまりにスカスカだったので放棄した。
J問題（40/300）
Try It OnlineにJ言語があるので、それで試しながらやる。最初2つはわかるが、3つ目でボックスが出現してもうわからなくなった。
2つ目の入力がinvalidだったらしく、途中通らずに苦戦していたが、リジャッジされた。
K問題（0/100）
38を出力したが、ダメだった。この38は適当に考えた数値だと思っていたが、思い返せばD問題のスタート地点の番号じゃないか。遠隔操作されている。
L問題（100/100）
入力を調べてみたが、どうやら与えられていないらしい？なんてしているとひらめいた。正という単位がある。
M問題（0/200）
なんも考えてない。
N問題（100/100）
とりあえず絶対値を出力すると、3ケースだけACする。入力はちゃんと数値だけ（.to_i.to_sするともとに戻る）。しばらく考えて、ふと絶対値記号に違和感を覚えて問題文をコピペしてみると、vmatrixだった。これなんだっけ？……行列式！1 x 1行列の行列式は要素そのままなので、そのまま出力してAC。
O問題（100/100）
つい最近Twitterで話題になっていた通り、wikipediaにオートマトンが書いてあるので、正規表現やるだけ。→RE……。
RubyでUTF-8を含む正規表現を書いたのだが、ジャッジの関係でエラーになっていたらしい。すでに解決済みだが、解決する前に通した。
カタカナは.bytesすると3つの数値になるので、3つ区切りにして要素を比較しながらif-elseを書きまくる。「イ」の次に「－」がないのは、一方通行っぽい矢印が書いてあってダメだと考えていたものの、wikipediaの例を見る限り良いらしい。
P問題（0/200）
東京？どこだよそこ。さすがに解ける気がしない。
Q問題（20/200）
スカイツリーだけはわかる。
R問題（120/200）
最後3枚の写真はそれぞれ富山駅、富山城、総曲輪（これは「そうがわ」と読む）のものだ。地元なので無限回訪れたことがある。かなり興奮した。まあ緯度経度を調べるのにミスりまくったんですが……。
最後の写真の場所はここだ。このアーケード好き。でもダイワデパートにここから入ったことはない。
移動しながら撮影していることを鑑みると、電車は高山線だろう。これは利用したことがないが、富山駅に乗り入れている電車で見覚えがないものは逆に高山線に絞られる。これ関係の2つも分かった。
高山には朝市があるので、それを探したが、街灯も橋の形もどうも合わない。あきらめて川の柵だけ合わせ、適当に出したら通った。以上で6つ正解した。
あとから知ったことだが、どうやらストリートビューの写真が撮影されたあとにできた橋と街灯らしい。
S問題（0/100）
問題文からsが削除されているのは分かったが、何をしたらいいのかわからない。解けず。
コンテスト後に聞いた話によれば、ソースコード中からsを削除すればよいらしい。数式に必要なsが抜けているとばっかり思っていた……。
T問題（100/100）
あみだくじを頑張る。画像をダウンロードしたりすると罠があったらしいが、原始人であるところの僕はスクリーンキャプチャをしたので気づかずにACした。
線が適当に書かれていてビビったが、つながっているとしてよいようだ。これも質問タブに明記されていたが、僕は気づいていなかった。半分くらいあみだくじを進めたところで、微妙につながっていない線に気づいて真っ青になった。
U問題（0/200）
なにもしなかった。
V問題（20/200）
equinoxとprogrammingだけ。
W問題（140/200）
これ↓をインストールして、含まれる文字を全部表示して目grepした。
呂官不糸＿各上少行阜歩＿＿
X問題（0/100）
なにもしなかった。
Y問題（100/100）
とりあえず出すとWA。詳細を見ると、メッセージで/を使用してはいけないと書かれている。次にRubyのdivを使って出すと50点。メッセージにはdivを使うと減点と書かれている。
ちゃんと真面目に繰り返し二乗法を引き算でやってAC。
Z問題（100/300）
最初の3問だけ。チェスの特殊な移動を知っていれば、ガチャガチャするだけで解ける。あとは……ナオキです
[問題（10/100）
適当にYesと出力したらメッセージでなんか言われたのでNoと出力したら10点もらえた。
これコンテスト中10点しか見てなかったので10点満点だと思っていたけど、本当は100点満点で、どうやらYesで0点の時に提出の詳細画面から得点をクリックすると自由に値をいじることができて、それで100点にできるらしい。本当に草。
\問題（0/100）
普通に書いて微妙に通らなかったので、あきらめた。逆に11stとか書くのかな、とも考えたけど試さず。
本当は日付を約分するらしい。呆れかえった。
]問題（100/100）
OEISに投げると1件だけヒットするので提出すると微妙に違う。多項式補完してみたが全然ピンとこない。
1,2,5,7,11,15,21,26,32,39 - OEIS
なんだかややこしそうなことを計算している。また、2014年にいくつか間違っている項が修正されたらしい。まだ間違ってるんじゃないの？と思って、WAしたケースのうちn=12を手で構成してみると、1多くなった。提出するとそのケースが通った。マジで草。
それ以上手で計算するのは嫌だったので、ほかのWAのケースも1だけ増やしてみたら全部ACになった。
これ本当にすごい。感動してしまった。メッセージ性すら感じられる。
^問題（0/100）
なにもしなかった。
_問題（200/-135）
問題文には「200点満点です」と書かれているが、問題一覧から見ると-135点満点になっている。よく確認せずに解いた人を罠にはめるいつものやつだろう、と思って、あえてgets putsを提出した。
そのあとしばらくして、この問題で200点を取得する人が増えてきた。あとテストケースが謎に100個もあってジャッジを詰まらせている。不思議に思って提出の詳細を見ると、部分点が細かく設定されている。
多分対応するケースだけ狙い撃ちすることで正の部分点をかき集めると200点満点が得られるのだろう。対応するケースを計算するのは、100ケースもあることだし、何らかのアルゴリズムを適用する必要がある。
よく見ると、負の点数がついた部分点は、対応するテストケースがそれぞれ1つしかない。これを利用すれば燃やす埋めるで解けそうだ。以下解法。
これに従って解く。まず各テストケースに対応する命題変数を用意した。「真ならば解かない」ことにする。
正の部分点に対しては、まず答えに点数を足しておき、関係する命題変数のどれか1つでも真⇔「必要な問題のどれか1つでも解かない」ならばペナルティを受けると表現する。「または」の形なので表現できる。
負の部分点に対しては、命題変数が真でなければペナルティを受けると表現する。これは関係する命題変数が1つなので表現できる。
これで作ったグラフの最小カットを求めて、先に足しておいた点数と合計すると、見事200になった。あとは残余グラフでsourceから到達不可能な命題変数をリストアップし、それだけechoするようなコードを書いて満点を得た。フローを流すのにはACLを使った。
`問題（0/300）
なにもしなかった。
a問題（116/200）
簡単なものは一瞬だが、わからないものはとことんわからない。7番の「いのうただたか」は言われてみれば納得だが、コンテスト途中は天気図にしか見えていなかった。
最後に7番に「いっしゅう」と提出するとクエストキーを得られたのだが、ジャッジが詰まっていた影響ですでにコンテストが終了してしまっていた。
b問題（30/0）
E問題でクエストについて聞くともらえるやつと、しりとりの「おちば」と「むかで」。
