ICPC2021国内予選参加記 - polyester-kpr’s blog

今年もICPC国内予選に参加しました。

今回のチームメンバーはあめふり君とパーシー君です。

去年と同様オンライン形式だったので、メモ帳代わりにhackmd、通話はzoomを使ってやり取りしました。

A問題

恐らく簡単だろうと思って問題を読まずにパーシー君に押し付けました。ごめんなさい。特に引っかかることなく通してくれたので助かりました。

B問題

あめふり君が解きたいと言ったので任せました。ここで時間を浪費してしまいました。何もアドバイスできなくてごめんなさい。

C問題

去年や一昨年のC問題はそこまで難しくなかったので、今年も解けるだろうと思ったら全然違いました。がっつり構文解析で困りました。+のところはどうしようもないですが、-のところは入れ替えることで値が変化します。引く数をできるだけ小さくすることで最大化できそうですが、それ以上のことは分かりません。

D問題

C問題とは違って問題文も比較的単純で一見解きやすそうでした。実際、A, Bの次に正解チーム数が多かったので、ずっと考えていました。

まず風船を多い順に並べてみました。しかし、実装してサンプルを試すと1人少ない結果が返ってきてしまいました。そこまで単純ではなかったようです。サンプルを手作業で実験したところ、

4 3 3 3 3 4 3 3 1
↓3人に渡す
1 0 0 3 3 4 3 3 1
↓1人に渡す
0 0 0 2 2 4 3 3 1
↓2人に渡す
0 0 0 0 0 2 3 3 1
↓2人に渡す
0 0 0 0 0 0 1 1 1
↓1人に渡す
0 0 0 0 0 0 0 0 0

とすると、9人に渡せるようです。残念ながらここまでしか分かりませんでした。何か法則性がありそうなのですが……

E問題

ここが一番時間をかけるべき問題だったのかもしれません。問題文を一通り読むとダイクストラ法で解けそうです。そこで、手元にあったダイクストラ法のライブラリをこの問題の形式に合うように改造していきました。

途中でpairをtupleに書き換えるところで詰まりました。pairでは.firstなどを使えたのにtupleにはそのようなものは存在しなかったのです。ここで、tieを使えばいいとあめふり君が教えてくれたので、その通りに実装することで要素を取り出すことができました。ただ、最初tie(pf, v, pt) = p;　とすべきところをtie(pf, v, pt)　としていて、segmentation faultが発生していました。

実装が終わってサンプルを試したところ、答えは合いませんでした。残念ながらここで時間切れとなってしまいました。