はじめに
kureha といいます。AtCoder 黄色です。この度 ICPC2023国内予選に参加してきましたので、その記録を残すことにしました。
チーム紹介など
チーム名は頭文字 + AtCoder のユーザー名についている数字です。
shinchan さんに誘われて大学内の競プロサークルにお邪魔させてもらってチームを組みました。本来はチーム内で私が会話などを引っ張ったりするところなのでしょうが、残念ながらそんな能力はない...。
コンテスト当日
ライブラリは大学の研究室で印刷しようとしたのですが、wifi がつながらず苦戦。研究室にいた同級生の力を借りて何とかなりました。(本番では1ページも見なかった...)
自分のパソコンを使う予定だったのですが、wifiがつながっているのにコンテストサイトに繋がらず、急遽使うパソコンを変更しました。(いろいろとご迷惑をおかけしました。)
A,B,Cをそれぞれ一人ずつ解く予定でいたのですが、印刷の都合上A,B,D を一人ずつに割り当てて、A を解いた sakasuさんが C を解くことになりました。
C 問題
A,B問題は関与していないので飛ばします。
パズル問題でした。DE問題を見ていましたが途中でやめてこちらに少し取り掛かりました。市松模様的に分けて、一方をそのまま上へ詰めて他方をそのまま下へ詰めるのかな、でもダメな部分もあるな、とか思っていたら sakasu さんが解法を持ってきてくれました。解法を聞いて行けそうだったので実装してもらいました。(ダメならダメで考えたらいいだけなので...)
実装でなんやかんやあったようですが、ペナルティなしで AC でした。
D 問題
1,2,4,8,... を持つとすべての得点を作れるので答えは 7 以下となります。なので長さ 6 以下、合計 N の広義単調増加列について考えればいいというのを思いついたのですが、時間的に速いのかが分からず、実装も面倒そうだったので後回し。E をちらっと読んで C を味見する時間へ。
C を実装してもらっている間に E が解けたので、実装が楽そうだった E を先に解いて、その間に D の検討を shogoさんにしていただきました。
広義単調増加列を再帰で実装しがちなのですが、長さが短く、十分速くできそうということで5重for 文を実装し、判定問題は bitsetで書いて一発 AC でした。なお途中でバグらせた模様。
E 問題
ちらっと読んだときに、広義単調減少列にすればいいことには気づいたのですが、dp を思いつくのに少し時間がかかりました。dp の内容は公式解説通りなので略。C の実装でバグったらしいので、DとEを天秤にかけて E から書くことに。途中で頭が混乱したり、実装をバグらせたりなどしましたが、一発 AC。
その他
A~E の 5 完を達成した後に順位表を見ると大学内1位でした。そしてF,Gを少し見ました。F は幾何とかいう苦手分野だったので見なかったことにし、G は制約が小さいなぁとか思いつつ期待値は知らない子なのでネグレクト。結果何もすることがない状態へ。
F 問題は今考えると有限回が重要だったんですね。そのとき気づいても何もできませんが。
結果
全体17位、大学内2位により国内予選突破しました。
初遠征になるのですが不安しかないです。
月末に院試があるのでそれまでは競プロ中断になるはず。