ACPC2020 3日目 - ツバサの備忘録

最終日！です

内容
- A(0:05)
- B(0:07)
- C(0:11)
- E(0:37, 2ペナ)
- D(0:56, 2ペナ)
- F(1:27)
- G(2:49)
結果
おしまい

内容

通した順です。

A(0:05)

なんで4方向じゃないのだろう…とぼやきながら頑張って実装しました。
幸いバグらせることはほぼなかったのでよかったです。Bに先実装を渡すか悩みましたが書いた方がはやいかなと思い先に書きました。

B(0:07)

とまとさんが累積和ーと言いながらサクサクとおしてくださりました。ありがとうございます。

C(0:11)

$\mod{K}$ を状態に持ってDPをしてくださいとるぎうさんに言われたので、バトンタッチしてサクサク実装しました。これは結構はやく書けたと思っています。

E(0:37, 2ペナ)

最初僕が読みましたがわからず、Dをやっていたとまとさんと問題をスワップ。これがうまくハマり、とまとさんが方針をパッと出してくれて、そのまま実装→AC。
剰余をとると値が半分以下になる、言われればそれはそうですが気づきません…

D(0:56, 2ペナ)

とまとさんとるぎうさんで最初に出した方針が2ペナしたので、とまとさんと僕をスワップしました。と、考察ミスにるぎうさんが気づき修正してもらい、実装がまるっきりかわるので1から実装しなおしました。
scc上の頂点idと元の頂点idを混在させてしまいバグらせたので少し時間はかかりましたが、なんとかACでした。

F(1:27)

Dをやっている間にとまとさんとるぎうさんが考察をしてくださっていたので、その最後の詰め部分から参戦でした。
とまとさんがModIntを持っていなかった(PCが普段と違う)ので僕が実装しました。~~るぎうさんに、僕がやる意味ある？って言われましたが、実装がしたくなってしまったのであんまり聞こえなかったことにしておきました。~~
とまとさんに実装を見てもらいペアプロをしつつ、無事ACしました。

G(2:49)

3人でいろいろ考えるも何も方針が立たずだったのですが、るぎうさんが $O(N)$ の計算が $O(M^{2})$ くらいに圧縮できることを伝えてくださったあたりから考察が動き始めました。
僕が $O(M^{2}2^{M})$ くらいのDPを思いついたので画面共有をONにして一人で実装を始め、ガリガリ書きました。
バグらせ(答えるときにdp配列を参照せずreturnするという凡ミス)つつも、なんとかサンプルを合わせ、提出。

3人「ありがとうありがとうありがとうありがとうありがとうありがとうありがとう…」
ジャッジ「AC」

やったぁ！
ありがとうと連呼するの、噛みませんか？