TTPC2019参加記

東京工業大学プログラミングコンテスト2019 - AtCoder

risujirohさんJoe先輩とチームを組んで5位(オンサイト2位)でした。

最初はrisujirohさんとの2人チームだったんですが、僕がJSC2019の予選で橙から黄に転落したことで、3人でチームを組めることに。会場でもう1人拾うかとなった時にJoe先輩が加入してくれました。

戦略

というとオーバーですが、開幕はrisujirohさんがBDF、Joe先輩がACEを担当し、僕がG以降の問題を読んでました。AからFはコンテストのなかで一番簡単な問題だということが事前に公表されていたので、僕よりも速解きが得意な2人に担当してもらうのが良さそうということになりました。


G以降の所見の感想

G:これは解けるタイプの10^9+7だなぁ。
H:問題分が長いW
I:なんだこれ。制約がでかい数学はやめてくれ。
J:操作が謎すぎる。数学だし飛ばし。
K:AGCっぽさを感じた。解けるかも。
L:構文解析はまだしも多項式に関する問題はNG
M:全ての根について求めるんだから全方位木DPじゃないですか。
N:問題文が長くてよく読みませんでした。でも後から見返すと無理数を使ってゲームをしていて無理を極めてる。
O:構築ということしか把握してなかった。

なので解けそうなGKMの中でもGは簡単そうだったので着手しました。

ABD
問題文を読んでいるうちになんか2人が爆速で通してました。

E
これも知らない間にJoe先輩が通してました。

C
Joe先輩に問題と実装内容を説明してもらったんですが、どうやらa_i<=Xを忘れていただけっぽかったです。そのままAC。
あと__builtin_clzの仕様(0を代入された時の挙動は未定義)でハマっていたっぽいんですが、オセロのbitboardを実装したこともあって偶然知っていたので、伝えられればよかったなぁとちょっぴり後悔しました。

I
risujirohさんがlogを2つつけたものを提出したんですがTLE。WAもあってよくわからない。ここで一旦Iから離れたのは英断だと思います。

G
どうやら本質的には3つの値しかなくて、K回の操作である回文を作れたら、その回文はK+1回でも作れることはわかって、あとは1つの値を固定してコンビネーション+累積和で通るなぁと思って実装したんですがサンプルが1つ合わない。そのサンプルを精査したところKが2未満の時はコーナーケースっぽいことがわかったのでそれを除いてAC。(しれっと1WA出しているのは内緒)

F
risujirohさんがわからんと言っていたので僕も見たんですがわからない。Joe先輩がひらめいて、risujirohさんと解法を共有してからACしてました。ここからチームプレイ感が高まってきます。

M
Gの次に解けそうなのがMだったので、risujirohさんにも読んでもらって相談しました。僕は全方位木DPでしかないと思ってたんですが、risujirohさんに「ここは一旦全方位木DPから離れて部分木に足したり引いたりすればできるのでは」と言われてからあぁ…なるほど…となりました。実装で複雑になりそうなところがあったのでJoe先輩に問題概要から説明することに。なんかうまく日本語がでなかったり説明が飛んでしまったりしたんですが、簡単な実装方法を教えてもらい書き始めました。書き終えるのにはそんな時間がかからなかったのですがサンプルが合わない。手計算でやっても出力結果と同じになったので、ここで解法が間違っていたことに気づきます。一瞬青ざめましたが少し修正するだけで済んだので良かったです。

O
risujirohさんがマジックナンバーが大量に入ったコードを書いててデバッグやばそうとなりましたが、すんなり通しててウケました。正確すぎる。


ぱっと見てもロジックがわからなくててどうやって思いついたんだという感じです。

H
Joe先輩がsegtreeのモノイド付きpriority_queueで二分探索すればできるとか言ってて、流石にそんなヤバ問なわけがないだろうと思って読み始めたら本当にそうでした(絶望)でもJoe先輩がAdvent Calendarですごい二分平衡木を書いていたことは知っていたのでそれを使えば出来ないことはないだろうくらいに思っていたんですが、知らない間に実装完了していてそのままACしてました。すごすぎる。二分探索パートはその場で書いたと言っててそれもヤバイ。

K
あんまり通されていなかったんですが、残ったIJKLNはそもそもどの問題もAC数が少なかったので考え始めました。操作を末尾の要素を好きな要素と入れ替えてから、shiftすると言い換えられることはすぐわかって、もうちょっと考えると必要十分っぽい条件が生えました。実装はfftになりそうだし、実行時間が2.5sなのもそれっぽいなぁと思い、risujirohさんに説明した所、そもそも値が0or1なのでbitsetで行けそうとなりました。risujirohさんに実装してもらい提出した所順調にjudgeが進んでACになりました。

J
最後の1時間risujirohさんと相談していましたが解けませんでした。畳み込みっぽい式が出てきてちょっといけるかもとなりましたが、解説を読んでみるとそもそも発想が間違っていました。残念。

スタバ
慰労会の後、会場の近くのスタバでChokudai Contest 004に参加しました。マラソンはおそらく初めてなのでなにをすれば良いのかわからず、めちゃめちゃな山登りを実装していました。全くスコアが伸びなかったので上のマスから順番に貪欲したものを提出したところ128万出て、あとはマスを埋める順番を変えてみたりしたんですが改善されませんでした。かなしぃ。

感想
うまくいって楽しかったです。risujirohさん、Joe先輩、慰労会で話してくれた人たち、運営さんありがとうございました。