Kyo_s_s Homepage

ICPC2023 横浜大会参加記

競技プログラミング

ICPC

順位表: https://icpcsec.firebaseapp.com/standings/

4完で42位でした！

チームメンバー:

きょ (@Kyo_s_s)
えくとくん (@ecto0310)
Ackvyくん (@ackvy)

コーチ:

たゃせんぱい (@cordx56)

前日

おひるごはん

みんなでハンバーグを食べました。おいしかったです。

ぴーす pic.twitter.com/mJZLL7C0jS
— きょ (@Kyo_s_s) November 25, 2023

リハーサル

去年と同じようにえくとくんに最初の環境セットアップをやってもらい、AckvyくんとA問題を見ます。去年と同じ問題だね～となりながらAの実装をAckvyくんにやってもらいます。普段JIS配列のキーボードを使っているようで、このキーはどこにありますか！？って何度も言っていて面白かったです。その流れでB問題も実装してもらいます。手元で少しバグらせたりしましたが、修正し通しました。

D問題を読みます。去年このD問題が解けず、恥ずかしかったので今年は通したいねぇみたいなことをえくとくんと話します。 “Parallel” という単語が出てきます。去年はこれを「(直線の)交点」だと誤読していたのですが、「これって”平行”って意味じゃないの…？」と気づきます。去年は誤読していて解けなかったことが1年越しに発覚しました。かなしい…。競技プログラミングの精進より英語力をあげるべきそうです。“平行”と読むとすぐに解けるので、雑に書いて通しました。

C問題は去年えくとくんが通していたので丸投げしようとしたのですが、Ackvyくんが「 $\textrm{mod } 3$ でよしなにできませんかね？」みたいなことを言ってくれたので考えます。なんかごにょごにょできそうだったのでごにょごにょしたら通りました。わーい！

去年はリハーサル問題をすべて通せなかったのですが、今年は通せて良かったです。

よるごはん

チームメンバーで中華街に行きました。 Ackvyくんが「前来た時ここの焼き小籠包がおいしかったんですよね～」と言っていたお店があったのでそこで食べました。

麻婆豆腐に激辛と書かれていて迷いますが、食欲には勝てずに注文してしまいました。そこまで激辛ではなくおいしい辛さで選んで正解でした。小籠包もおいしかったです。

たべます pic.twitter.com/05VFI86ajB
— きょ (@Kyo_s_s) November 25, 2023

うおー pic.twitter.com/duksHN9PwV
— きょ (@Kyo_s_s) November 25, 2023

カレーです pic.twitter.com/kQDONOqTgt
— きょ (@Kyo_s_s) November 25, 2023

ABC330

負けました。ぼくは、弱い…

当日

あさごはん

朝ごはんを食べていたら shinchan さんたちのチームが朝ごはんを食べに来ました。

おはようございます pic.twitter.com/NYMWcLxHAU
— きょ (@Kyo_s_s) November 25, 2023

コンテスト

リハーサルと同じようにまずえくとくんにセットアップをやってもらい、AckvyくんとA, Bを見ます。

AはDPっぽくすればいいねぇとなります。Ackvyくんが書けそうだったのでえくとくんとペアプロして通してもらいました。

その間にBを読むのですが、あんまりよくわかりません。唸っていました。

Ackvyくんに「Dは構文解析ですよ！！」と教えてもらったのでBを放棄してDを見に行きます。 abababaaaaaを3(ab)5(a)みたいにしたものうち文字列の長さが一番短いものを答えてね、という問題です。構文解析じゃないじゃん～となりますが、文字列の長さが高々 $200$ だったので区間DPをすれば十分間に合うねぇとなり書きます。

提出したら…なんとWAります。困ってしまいました。問題文をよく読みます。提出コードでは aaaaaaaaaa は 10(a) となるのですが、数字部分は1桁でないとダメだよと問題文に書いてあります。問題文は音読して読もう！このケースでは 5(aa) となるべきです。チームメンバーに謝りながら修正し提出し、無事ACしました。

その間にえくとくんとAckvyくんがF解けたというのでペアプロしてもらいます。気づいたらFが通っていました、すごい！

Bを考えたりご飯を食べたりお菓子を食べたりします。

えくとくんがKを読んでくれます。円が1つあり、直線のクエリを投げると重なってる長さが返ってくるので中心座標/半径を答える問題です。 $x, y$ 座標は独立に考えてよくて、最小半径が $100$ なのでとりあえず $199$ おきに聞けば大体の位置は分かるねぇと話します。 Ackvyくんが「独立に考えたとき、円に重なるような異なる $2$ 直線があれば算数で中心座標/半径が求まるはずです！」と言ってくれたので、えくとくんに円に重なる異なる $2$ 直線を求めるパートの実装をしてもらい、ぼくとAckvyくんで中心座標/半径を求めるパートを考えます。

図において、 $a, b, d$ が与えられるので $x$ を求める問題になります。ここで、半径は等しいので次の等式:

$a^2 + x^2 = b^2 + (d - x)^2$

を $x$ について解けばよいです。これは、

$\displaystyle x = \frac{b^2 - a^2 + d^2}{2d}$

なので、これをそのまま求めればよいです。誤差が怖かったので周りをいくつか見る実装にしました。また、半径は、

$r = \sqrt{a^2 + x^2}$

で求めることができます。こちらも周りをいくつか見る実装にします。

バグっている個所があり一度WAりますが、全員でコードを読み修正し無事ACできました！

その後は全員でBを考えました。残り30分位のタイミングでセグ木があれば頑張れそう、となりえくとくんにセグ木を書いてもらいます。去年もえくとくんにセグ木を書いてもらいました、セグハラです。その間にAckvyくんと細かいところを詰めます。解けそう～となったのですが、実装が間に合わず + バグらせてしまい、通すことはできませんでした。えくとくん、ごめん…。

ということで、ADFKの4完でした。Kを通したのが凍結後だったので、YesNoで上がる瞬間が見れました。 4完していた中では1位 + Bが通せなかったチームのうち1位でした。Bを通せていたら5完だったので、悔しいです。でもチーム戦であることを活かし、協力しながら進められてとても楽しかったです。

懇親会

企業ブースを一周したりごはんを食べたりしました。えびと貝柱となにかがはいったなにかがとてもおいしかったです。

企業ブースに来週会う予定をしていた方がいてびっくりでした、来週また会いましょう！となりました。その方が開始前にTwitterで応援ツイートをしてくれていたことに気づき嬉しかったです。

インターン先のモノグサ株式会社がブースを出していたので顔を出さないとなとなります。インターンは殆どリモートでさせていただいていて、あまり面識がない + 髪色が青なので挨拶に行くのこわいよ～とえくとくんにゴネたのですが、連れていかれてしまいました。お世話になっておりますと挨拶をしたりしました。 ~~インターン募集をしていたので、つよい人が入ってきてぼくはクビになってしまうかもしれません。~~

感想

チーム戦であることを活かし、チームメンバー全員で上手く協力できたと思います。去年は誰かが何もしていない時間が生まれてしまってのですが、今年は最後まで全員で考え抜くことができました。終わった後みんなで「楽しかった！！」と言い合えたのがとても良かったです。5時間があっという間で、とても楽しめました。チームメンバーに感謝です。

しかし、Bが通せなかったのはぼくの精進不足です。問題の適切な言い換えができず、またライブラリで殴る手法も最後の最後にならないと出てきませんでした。悔いが残ります。