ACPC2020 参加記

会津行くぜ！

 ACPCは毎年懇親会が大盛り上がりということで非常に楽しみ

どうしてこんなことに...

 正直そんな気はしてたよ

HUPCと同じノリで全日いつものチームで

Day1(農工大セット)

 例の如く

A:Rubikun

B:risujiroh

C:kort0n

でスタートして、後はよしなにやる感じになる。

Cを読む。

「各頂点ペア(i, j)について、街iから街jへ移動するときの必要なコストの最小値を出力？各ペアについて道やテレポーターの選び方を変えろということ？でもそれテレポーター1つで良くない？」

サンプルも見つつ読み直す。ようやく「強連結にする為の最小コスト」を聞かれているのだと分かる。

Aが即通る。Bも少し面倒な方法を取ってしまったようだが、まあそれ程掛からずに通る。

その後実装を始める。何かサンプルが合わない。読み返すと、vector<edge> e(M)を宣言した後、読み込んだ辺をpush_backして空の辺がM個生まれていた。これやらかすの100回目くらい。

 こういうのどうやったらやらかさないように出来るんですかね...

修正してCを通す。この時点でRubikunがD, kort0nがE, risujirohがFを解けていたので、そのまま各自取り組むことに。

Dは一回同じ値の扱いを間違えてWAが出たようだが、すぐに修正して通す。

Eを書き始めると、問題の前半パートまでしか解けていなかったことに気付く。周りに介護を求めつつ後半パートも解いて提出する。REが出る。NがクソデカいときのNCKを前計算テーブルを使って求めようとしていたせいだった。これやらかすの1000回目くらい。愚直に計算するようにする。TLEする。バカなので毎回逆元計算にO(log mod)掛けていた。その後Fも通る前になんかREが出てた。合計5ペナで順位が完全に壊れる。

D, Eの実装中にrisujirohがGを解いていたらしく、そのまま実装を始める。

その間にHを考え始める。最初はルール①における最適解とルール②の最適解のうち良い方を出すものだと勘違いしており、「ルール②を選ぶ意味が無くないか？」とか言ってた。clarを見て完全理解する。

そういうことをしているうちに、Gの実装が終わる。探索範囲のミスでWAが出るが、修正して通る。

 

 

...ところでこの弊チームのG、区間の場所を確定した後左右吸い込む点の距離を二分探索で決定してるんですが、これケースによっては余分に1個吸い込んでしまうのではという気がしている...でもhackケースを作ろうとしても、他の区間で上手くいってしまってhack出来ない これ大丈夫なのかな

 

 

Hは「Nが小さいときは解けるね～」と言っているうちに無限時間経過して、コンテストが終わる少し前にNが大きいときの解法が生えたが、当然間に合うはずもなく...

 

f:id:kort0n:20200922023051p:plain

うーん...

結果は8位だった。個人勢にも結構負けていて、まあまあ冷えている...

 

f:id:kort0n:20200922023216p:plain

このパチモンチーム許せねぇよ...

 
問題の感想

B:これ普通に難しくない？XXORの難しい方に似てる

C:これも難しくない？うっかり嘘貪欲やりそうになる

D:B, Cより実家感がある

E:AtCoderの500点が2問飛んできた感じだ

F:

お ま た せ

い つ も の

ハ コ の 魔 女

G:添字あたまこわれそう

H:何でこれすぐに出来なかったんだろうね 本当に何で？

 

Day2(会津セット)

問題の感想

A, Bが本当に爆速で通っていた。そのままCを通す。

Fを読むと解けたので通す。

Eが得意そうと言われたので読むと本当に得意なやつだった。通す。

その後は暫く止まるが、Gの解法が生える。区間に辺を生やす実装が出来ないのでrisujirohに頼み込んで実装してもらう。

その間にKを読むと解法が生える。bitsetで色々やる実装はあまり得意ではないので、Gの実装を終えたrisujirohに頼み込んで実装してもらう。

残りがDIJの3問になる。Dは「こんなん無理やろ」という気にしかならない。Iもある意味「こんなん無理やろ」という気にしかならない。Jは結構通されているがよく分からないな～と言っていると時間が結構経ってる。

暫くしてRubikunがJの解法を生やす。聞くがよく分からなかったので、risujirohに頼み込んで実装してもらう。

しかし全く答えが合わない。残りの2問が諦めモードなので、3人がかりで必死にデバッグをすると、バグが見つかる。辺を削除する際に、辺を追加する際の各操作を逆順に逆操作することにしていたが、このときに「この辺が存在するならば」というif文の条件式も反転させて「この辺が存在しないならば」としてしまっていた。初めて見るタイプのバグだ... 何にせよJが通る。

この時点で残りが50分程度で、DもIもsubmitさえされていなかった。「DもIも不可能にしか見えないし、もう無理じゃね？」という空気になる。

 と言いつつ何もしない訳にもいかないので、Dで雑に愚直解を書いて実験していると、「実はsum(B)ってせいぜいPの数倍程度しか見なくて良いのでは？」という感じがしてくる。とりあえずそのエスパーを認めて考えていると、Aの種類数に着目することで更に計算量が落ちて、TLに間に合いそうだということが分かる。この時点で残り10分程度だった。

必死に実装を始める。途中の算数パートを周りに投げつつなんとか実装して提出するとACが出る。

 ...が、5分間に合わなかった。途中半ば諦めてダラダラする時間が無ければ間に合っていたかもしれない...優勝はしたが悔いの残る結果に

f:id:kort0n:20200922025611p:plain

(+0)
問題の感想

C:これ面白いけど乱択通っちゃうのちょっと残念感あるね M<=2Nくらいにすれば通らないように出来ないのかな

D:ビックリ性質と計算量削減から作られるビックリ解法 何だこれ...

なんかチーム作問中にどんどん計算量が落ちたらしいね 凄い

E:こういうの好きです

F:そろそろここも実家になりつつある

G:区間に辺張るやつ書くの、滅茶苦茶大変じゃない？

ところで解説スライドの改題あまりよく分かってない気がする

I:こんなん無理だろ

J:大変ねっとりしております...

K:これマジで面白い つぶあんすげーよ

 

Day3(北大セット)

Aを読んでいるRubikunが「は？ヤバくないか？」と連呼している。ヤバそうなのでBとCを先に通す。会津セットのノリで問題をmod 3で読み始めて、risujirohがEを、kort0nがFを読み始める。

RubikunはどうやらAの誤読に気付いたらしく、その後すぐに通す。

Rubikun「これ今どれが解かれてるんですか？」

kort0n「Eはrisujirohが解いた Fは今解けそう Dは多分誰も読んでない」

Rubikun「Dを誰も読んでない！？！？！？」

Rubikun「難易度順なのに何で前のやつ誰も読んでないんすか」

kort0n・risujiroh「ごもっともでございます」

と言いつつrisujirohがEの実装を始めて通す。

その後Fを実装する。途中でcombinationが前計算テーブルの結果を使えず、愚直に計算しないといけないことに気付く。二日前の反省が生きている。えらい。submitするとWAが出る。バカがよ。

読み直すと、遷移計算が間違っていたことに気付く。修正すると通る。

Dが解けていなかったようなので、読む。

kort0n「これN頂点NM辺くらいのグラフを作ってSCCしたグラフがパスグラフになってれば良いってことだよね。パスグラフ判定だから各頂点の入次数と出次数とか見とけば良いのかな。じゃあ実装頼んだ。」

と言って実装してもらう。ACする。

 

 

 

 

 

 

 

 

...これは嘘解法です。正しくは「頂点数が元のグラフと同じであるパスグラフを部分グラフに含むかどうかの判定」をしないといけない

後でhackケースが作れた。本当にすみませんでした。

 

 

 

 

その後risujirohとRubikunがHを始める。その間にやや苦労しつつGを通す。

ここから3人がかりでの最強AIとのバトルが始まる。

とりあえず実験コードを書いて、各(N, K, H)についての勝敗判定を書き出してみる。規則性が全く見出せません本当に有難うございました。

 

...全く見えないというのは少し嘘で、H >= KのときH += (K-1) で答えは不変とか、その他諸々の細かい周期性のようなものは見当たる。しかし、あまりに多すぎてどれに着目すべきか逆に混乱し始める。

結局判定問題すら解けないままコンテスト時間が終了する。

 

f:id:kort0n:20200922031612p:plain

2分差で負け、何？

 

問題の感想

 

 C:はい、実家

D:一見数学ゲーと見せかけて実はグラフゲー まじかー

ちなみにrisujiroh曰く数学ゲーとして突き詰めると制約をかなり厳しく出来るらしい

E:見た瞬間解けなかった。これ忘れがちだよね。

F:遷移計算をノリでやったら間違えた。反省してます。

G:a_nへの水やりは必要でしたか...?

H:謎

 

 

 

楽しコンテストでした。運営の皆様、有難うございました。