JOI 2019/2020 2次予選感想 - sashimingの競プロメモ

ABCDの4完でした f:id:sashiming:20191210140255p:plain

以下、解いた順に書いていきます

A問題 - ポスター

一瞬ん？となったけど各方向について全部のマスを見るだけです、はい
ところで謎関数書いてないか？

f:id:sashiming:20191210140952p:plain:w400:left

桁和の文字列見た瞬間身構えたけど、そんなに難しくなかった

$1$ から $N$ それぞれについて、もとの数と一回操作した後の数を UnionFind 上で unite させる
すると、 $N$ を含む集合の size をとるだけで答えが求められる

集合サイズを求められる UF のライブラリを持ってたら一瞬で解ける

ところで桁和求める関数の実装がスマートじゃなくない？めっちゃ緊張してますね

f:id:sashiming:20191210142856p:plain:w450:left

Cよりは難しいと思う

最遠点には出来るだけ早く到着しないとダメそうなお気持ちを察したので、とりあえずスタート直後は最遠点に直行
帰りに残りのイチゴを回収していく感じ

そしてクソ実装、まあ通ったからヨシ！

f:id:sashiming:20191210144034p:plain:w500:left

脳死桁 DP 笑　これしか浮かばなかった
多分 10 桁で十分だろうな～、でも一応 15 桁取っとくか～という気持ちで投げたけど、14 桁で落ちるケースがあるらしくびっくり　あぶねー

ところで 15 桁で十分な証明をしていませんよね？ダメですねえ

以下実装 (dist 配列は各キー間の移動距離を埋め込んだ)

f:id:sashiming:20191210144537p:plain:left

ちなみに提出結果はこの通り　時間ギリギリだけど剰余演算最適化したらはやくなりそう

f:id:sashiming:20191210144752p:plain

なにこれ笑

構文解析をやったことないので Google 先生の力で 20 点取ろうとしたものの、めっちゃバグりまくった　うく

終了後に見返したら、20 点狙いより満点狙いのほうがやりやすいと感じた　最初から諦めるのはやめましょう

多分 2 次予選通過ですね、対戦ありがとうございました