KSDUPCオンサイト 参加記

競プロ

これは2024年9月15日に京都産業大学で行われたKSDUPC（京都産業大学・同志社大学プログラミングコンテスト）のオンサイトの参加記。前のMMAコンと同じように、移動成分多め。

ioor.connpass.com

オッ関西のオンサイトじゃあないか。申し込んじゃお〜

移動

ぼーっとしているうちに朝になってしまった。さらにぼーっとするとあわや遅刻という時間に。先月のオープンキャンパスには国際会館駅乗り換えで行ったが、今回は時間が惜しいので北大路乗り換えで行くことにした。

京都産業大学は京都市の上賀茂地区にあり、滋賀からはそれなりに時間がかかったりかからなかったり。JR→地下鉄→バスが無難である。叡山電車も一度は乗ってみたいが、こういう具合なので…。

TwitterのTLを眺めてみると、もうすでに何人かが会場に到着しているようだ。早くない？北大路のバス乗り場がややこしいという情報を入手したので、用心することにする。

京都駅にワープ。うっかり地下でスコーンを買いそうになったが、烏丸線で北大路駅へ。どうもバス乗り場と反対側の改札から出てしまったらしく、駅を歩いて縦断することになった。早速のガバ。バス乗り場は聞いていたほどややこしくはなく、むしろわかりやすかった。

烏丸線@北大路駅

バス乗り場で並んでいると、後ろにKSDUPCや競プロの話をしている集団が並んできた。じゅーすいそ（@deuteridayodayo）さんと他に3, 4人居ただろうか。じゅーすいそさんはMMAコンで一度会っているので、一目で認識することができた（初遭遇でもそうだったけど…）。

ややこしいと噂されていたバス乗り場へ続く道

京産大行きのバスは定額運賃後払いで、乗車前に知らずにICOCAをリュックサックから出す田舎者となった。市バスはそうなのか？研究が必要。車内ではちらほら競プロの話題が聞こえてきた。競プロerは10人くらい乗車していたんじゃないかしら。競プロer大移動！老人に席を譲って「人間力最高！」と言われている人がいた（人間力はうろ覚え）。

先月の国際会館駅からとは反対側のルートで、加茂川など外観も新鮮で面白い。柊野別れという変わった名前のバス停があった。山に入ったな〜と思ったらもう到着。

競プロのオンサイトに行くのは2回目である。1回目ほどではないが、人が集まる場所への根源的な恐ろしさはやはり拭えない。会場がある5号館への経路を入念に確認し、オープンキャンパス関連の客引き（？）をガン無視しながら歩いていく。それなりに歩いて「あれが5号館か！」と思ったら、全然違う建物だった。

会場in

会場だ！connpassの確認と会費の支払いを済ませて、「じゃあ好きな席にどうぞ〜」と言われた。どれどれ角席は…と思ったが、当然全て埋まっている。列の真ん中あたりの席が空いていたのでそこに座ったら、隣にFFがいておっとなった（話してはいない）。

iPadやら電源やらの準備をする。電源タップを持ってきてはいたが、いわゆるタコ足配線がどのくらい許容されているのかわからなかったので、持ってきたモバイルバッテリーを使うことに。巣作りが終わって暇になり、Twitterを眺めたり会場内をきょろきょろしたり（不審者）。せっかくなので名札の写真を撮ってツイートした。こういうのやってみたかったのよね。ガハハ！

今回のオンサイト懲りずにiPadとGitHub Codespacesを使って実装を行う。会場で提供されている回線は人数が多いからか不安定かつ低速で、代わりに自前の携帯回線を使うことにした（根は携帯回線なWi-Fiだった？）。

コンテスト開始の14:00になった瞬間、わいわいがやがやしていたのが収まり、強烈にキーボードを打つ音が全方位（？）から聞こえてきた。ぼちぼち問題を開く…

コンテスト

ABCEFの5完で22位だった。うーんもう少し行きたかった！

GitHub CodespacesとiPadの組み合わせでオンサイトに出るのは、色々厳しいかもしれんという気持ちになった。途中固まったり、TabやEnterが効かなくなるといったことが頻発して、コーディングにあまり集中できなかった。やっぱノパソか〜〜〜

MOFEの環境についての情報を見つけられず、ac-libraryやsortedcontainersが使えるのかよくわからない状態で参加したんだけど、今見たらコンテストのページにガッツリリンクが貼ってあった。アホすぎる

A - 天体望遠鏡

京都産業大学にはでっかい天体望遠鏡があります。

らしいわね。先月のオープンキャンパスに行った時、望遠鏡ツアーみたいなのがあった気がする。

距離を比較して頑張る。両辺を2乗して整数で処理（しなくても通るのかしら？）。

B - かき氷祭り

出張高橋くん。頑張って算数をする。変なミスで1ペナ…。

C - 変な家

スペース足りなァァァァァァァァいッッッッッ！！！！！！！栗原ーーーーーッッッッ！！！！！スペース足りねえぞ！！！！！！！！

ソートしてl_{i + 1} <= r_iを判定する。なぜか半開区間だと勘違いして1ペナ。

D - Let’s go to KSDUPC

順列全探索するか〜と思ったら2 <= N <= 17だった。17!はクソデカ！

BitDP感はあるけど、何も思いつかないのでスキップ。

E - 遅刻厳禁

同志社大学今出川キャンパスは地下鉄今出川駅直結です。

何年か前に行った時、確かに地下鉄の駅に近かったけど、直結とは驚き。

天才経路問題か？？？と思ったが、素直に最短経路の長さ（分単位）を求めて、いい感じに表記するという感じ。

F - 駅伝中継

「番号iの選手はどこにいるか？」と(進んだ距離, 選手番号)をsetで持っていい感じに更新していく。この問題はC++で書いた。まともに使うのが久しぶりすぎてcpprefjpと少々睨めっこするなど。今思えばtatyamさんのsortedlistを拝借すればよかったか…。

クエリのあと全ての選手がLメートル進むというのは一旦無視してしまうことにして、回数だけ数えておく。全ての選手が同じだけ進んでも順位は変化しないので、実際の位置を出力する時に帳尻を合わせることにする。

コンテスト後、セグ木で解こうとしたという話を聞いた。ノードに上位いくつかを保持するタイプのやつ。確かになあ…。

G - カラカラしりとり

a: 1, b: 2, c: 3, …, z: 26, aa: 27のように、文字列と整数を対応させて、いい感じにしようぜという気持ち。

先頭の文字と末尾の文字は決まっているので、間を好き放題に決めていく。先頭と末尾をキーに、文字列と対応する整数を持って、インクリメントしながら使っていく…という具合。高橋くんと被ったら飛ばす。

文字列と整数を対応させるという発想はよかったが、その方法が間違っていたわね…。当初文字列を26進法表記の整数とみなすように実装していたんだけど、これでは文字列の中身が全てaである場合に0になっちゃって、例えばaaaaとaaを区別できない。十進法で言えば0000 = 00。これをうまいことする方法が思いつけなくてそのままコンテスト終了した。

ちゃんと調べてみるとA1表記と呼ばれている方法があり、(空文字列): 0, a: 1, b: 2, c: 3, …というように文字列を対応させている。この方法を使った実装に切り替えると無事ACすることができた。

H, I

わからな〜い…

解説

ほえ〜となりながら眺めていたら、不意打ちで岩井星人が出てきてびっくりした（小並感）

コンテスト終わり

コンテストが終わって皆々再びわいわいがやがやし始めたが、自分はとりあえずG問題と格闘することにし、ACした後はA1表記について自分なりにまとめようとObsidianのノートを書いたりしていた。「皆がわいわいがやがやしている中、一人何かをしている人」になってしまった。

iPadに繋いでいたモバイルバッテリーが枯れてしまい、iPhone, iPad共にバッテリー残量が4割と少し不穏な状況。

気付いたら自分の後ろに大量のぬいぐるみが設置されていてびっくりした。

どうしたもんかいの〜と思っていると、ぴぇ（@yaaya8_8）さんに話しかけられ、G問題の話などをした。二人で色々話していると、途中から人が入ってきたりしていい感じに。圧倒的感謝…！んを（@CU_NextStage）さんやMM（@cheMMath6021023）さん、じゅーすいそさんといったFFの人や、そうでない人たちとも話すことができた。

受験がやばいとか、滋賀とか数学の話をしているうちに会場の閉場時間になってしまい、とりあえず建物から出ることに。

おやつとか飲み物があったぽいけど、結局自分は手をつけなかったな。なんで…。

そのままバスに乗って北大路駅に戻り、行きはあまりちゃんと見られなかったバス乗り場を観察。地下に乗り場と営業所がある作りになっているそうで、おもしろい。こういう所は初めてかも。

会場からバス停に向かって歩く

北大路バスターミナル

ぴぇさんと何か食べに行こうという話になり、京都駅でラーメンを食べた。味玉入りを注文しようと思ったのに、間違って違うものを注文してしまいぐぬぬ。

解散し家路。終わり！

あとがき

関西は関東と比べて今回のようなオンサイトが少ないので、こういう機会があるのはとても嬉しい。他の参加者との交流も行うことができた。

コンテストの方はというと、変なペナルティが多かったり解けるべき問題が解けなかったりと少し厳しい結果だったので、今後も精進していきたい。

開催に関わった全ての人に感謝！！！

そういえば会場の写真が無いですね…

2024/09/18 19:20 人物の情報を追加し、より正確と思う表現に修正した。文章全体の趣旨や意図は変えていない（つもり）。