メンバー

yes (この記事を書いている人)

学部2年生。C++使い。エナドリを週3〜4ペースで飲んでいる。実装と考察担当

なお

学部4年生。Python使い。パソコン関連の知識が凄い。環境構築と考察担当

けいと

学部4年生。C++使い。ゲーム開発の実績が凄い。考察と実装の監視担当

事前準備

ACL+自分が使っているマクロを全て乗せたcppファイルと普段使っているスニペットファイルを持っていきました。

本番で使用するPCに上記のファイルを送った後、なおさんに「こういう環境でやってるんだよね〜」と教えたら全て環境構築を行ってくれました。本当に、ありがとう

ちなみに、僕の環境は下の記事を参考に作らせて頂いてます

リハーサルで試しに問題を解きましたが、普通に実装ミスをしてしまいめちゃくちゃ焦りました(´･_･`)

模擬国内はバイトとバッティングしてしまい出ませんでしたが、絶対出た方が良いと思います………………

戦略

僕の大学からは2チームが出場していましたが、プリンターが1台しか無いのでじゃんけんでどちらが先に使用するか決めました。

負けました。ガーン

ということで僕のチームは、Aを3人で実装→僕がB,Cを解いている間にD〜Fを印刷し、先輩2人に考察してもらう→Cまで解いたら僕が合流、ということにしました。

解いた問題数が同じならそれぞれの解いた時間がそのまま足されるため、A〜Cは3人で協力した方が良かったのかもしれません。

本番

開始前は緊張していて、深呼吸しながら自分に落ち着けと言い聞かせてました。

A

開始後すぐ3人でA問題を見ました。ちょっと沼りましたがなんとか通りました。(0:03)
全部0-indexedにして1→12,2→13にしたんですけど、冷静に考えたら無駄すぎるな？？？

B

もう片方のチームの印刷が終わったので印刷して先輩2人にD問題とE問題の考察を託しました。
託した後は僕がB問題を見ました。とりあえず1番左はカバーしないといけないのを考えると、流石に左から貪欲で合ってそうな気がする。実装して通せました。 (0:07)

C

その勢いで僕がC問題を見ました。多分stackで管理するやつなんですけど解いたことない&実装バグらせそうで絶望。他に良い案も無くてさらに絶望。

冷静に考えたら2乗が通るのでイベントソートして良い感じに実装して通せました。(0:15)

D (1)

Cまで通したのでなおさんからDの考察をもらいました。が、なおさんは正しいことを言っていたのに俺の理解力が不足していて全く理解できない。(え？)

このまま見ていると時間が溶けそうだったので別の問題を見ることに。

E

Eはどう？と聞いたらけいとさんが「Eが簡単かも」と言ってました。見てみると確かに解けそうには見える。とりあえずジェムが付いているものの中で最も安いものは最初に買って良さそう。そこからジェムがついてるものを連続で交換していけば、あとは余ってるジェムでジェムが付いていないものを交換していけば良くない？と思いました。ただ、実装するもサンプルが合わない。

ここでけいとさんがサンプルの最後のケースは価格が1番小さいものを全て買った場合が最適解であることに気づきました。そこで僕はこの問題が脳裏によぎり、後でジェムを使うのを取り消し出来れば良いのでは？と野生の勘が働きました。実際買う順番をジェムがついているもの→ジェムがついていないものとすれば達成出来そうな雰囲気はする。実装するとなんと通りました。(1:10)

(実際はもっと簡単に出来ることに気づくのは競技後の話)

D (2)

早めの4完なのでワンチャン通らないかなと思ってましたが、昨年はボーダーが5完だったのでもう1問は解きたいなと思いました。

ここでF問題とG問題を見る。F問題は最初この問題に見えて嘘だろ？？？と思ったが冷静に考えたら障害物が少ないので座圧してどうのこうのしそう。しかしバグらせまくる未来は見える。
G問題は競技中2つの駒がバッティングするタイミングの性質を見抜けなかったため、不可能そうに見えた。

となるとあと1問解くにはD問題を見るが最善と判断しました。この時点でなおさんは解法を理解していたが第 $k$ 項が入っている区間を高速で判定する方法が分からないという状況でした。

一方その頃僕は、あまり数列の性質がよくわかってないが、区間の長さの性質的に二分探索で解けることは分かっているという状況でした。悩んだ結果、一旦なおさんに実装してもらうことにして、その間に僕が一生懸命実験するという謎の状況に。

残り1時間を切るくらいに僕がようやく性質を理解したので実装をバトンタッチしましたが、サンプルがなかなか合わない。$s=6$ の場合は紙に書いていたので、なおさんにテストケースを作ってもらって実験することに。(こういう時Pythonって便利だなーって思いながら見てた)
すごく緊張している中何とか合わせることができ、サンプルも合っているので提出してみる。

正直絶望していたのですが、なんと通りました。(2:52)

AtCoderのレート的にはもっと速く通すべきなのでしょうが、それはそれとして嬉しかったです。ウオオオオオオ　順位を見ると70位台につけていたのでワンチャンあるのでは？？？と思いながらフィニッシュ。

結果

終わった後は上のチームから数えてみるとワンチャン通ってるんじゃね？？？と盛り上がってました。

打ち上げは監督員を担当してくれた教授ともう1つのチームのメンバーと一緒にピザを食べました。写真は撮り忘れたんですが美味しかったです。

今後の目標

本当にD問題でここまで詰まってるのも苦しいし、そもそもABCしか出来ないし、英語も全然分からなくて大変苦しいのですが、今後はいっぱい知らない典型を吸収して未知の問題に対応出来るようになりたいね～～～の気持ちでいます。
とりあえず頑張るぞ！ウオオオオオオオオ

ここまで読んでいただきありがとうございました！