RUPC2024 参加記 - zawatinはてなブログ

はじめに

3/23, 24に開催された立命館大学プログラミング合宿2024 RUPC2024 に参加してきました。day2の問題セットのWriter, Testerも担当しました。本記事はこれらの参加記です。

運営のRiPProの皆さん。今回は貴重な体験をすることができました。ありがとうございました！

注意事項

問題内容のネタバレ(RUPC2024day1, day2, ABC346, ARC175)を含みますので、これからセットを解こうと思っている人は注意してください。
ですます調なのか、タメ口なのか、口調が統一されていない

はじめに
day0, それ以前
day1
day1 立命館セット
day1コンテスト後
day2
day2 コンテスト後
day3 (ちょっとした一人旅)
day2 コンテスト
おわりに

day0, それ以前

day2の問題をせっせこ作ってました。難しめの問題が1問、簡単めの問題(day2のB, H, Lより簡単なやつ)が1問AtCoderに爆破されました。どうして.....

day2のコンテストのルールについて、「5h並列なし」と「4h並列あり」で部内で意見が割れていました。自分は後者、特に「並列あり」を推していて、もう一問高難易度があれば5hでもいいんじゃないかと主張していました。最終的に「4h並列あり」になりました。 0ACが2問生えてしまったので、5hの方が良かったなぁ。 <- ワシが戦犯か... ?

前日は問題文の最終チェックを行いました。今までも何回か問題文校正を行っていたのですが、ここでもガバが結構見つかって肝が冷えました。

問題文が読みづらかったという感想をいくつかもらいました。まだ校正が足りなかったようです。すみません

前日は23時に就寝

day1

午前3時30分に起床 <- 助けてくれ

移動に関してのTips: 新幹線は指定席券を買うと良い

電光掲示板の新幹線の名前を確認することで、何処の乗り場に移動すれば良いかがわかりやすい
確実に座れる。自由席より隣の席との空間が大きいかも？
自由席券よりちょっと高いが、それだけの価値があった

昼ご飯はコンビニでおにぎりを食べた

day1 立命館セット

https://onlinejudge.u-aizu.ac.jp/services/room.html#RUPC2024Day1/info

pitPさんとAbeshi君と組んででることになりました。外部の人とチームを組むのは初めてで、ちょっと緊張しました。

RUPC2024-day1@HISHO_NO_KISEKI @Linaria57315311 (敬称略)でRUPC_Engine_Pとして出ていました。 6完
A 8分かけた。すみません
B Abeshi pitP
C Abeshi
D dp、悪方針引いて手間取った
E pitP
H Abeshi pitP

F 私が嘘解法伝えた後、Abeshi pitPが頑張っていた。
G 実装間に合わず。01BFSがっちゃんこ
— カスタネット (@zawakasu) 2024年3月23日

問題文を読んで、とりあえず $r$ と $S$ について等式を建てた。 $r$ について解いてそれを実装したが、全然サンプルが合わない。ﾀｽｹﾃｰ

$\frac{1}{6}$ を逆につければ合うやろ -> 合わないな。え？？？

二人に助けを求めたあと、 $\sqrt{}$ を付け忘れていたことに気づく。

-> AC

Aですいません。1/6は左辺右辺どっちにつきますかとチームメイトに泣きついていた時間。プライスレス。
— カスタネット (@zawakasu) 2024年3月23日

....何しているんですかね？

関わっていない。チームメイトの二人が通していた。

https://atcoder.jp/contests/abc308/tasks/abc308_g をMoにすると解けるみたいな話がチームメイトから聞こえていた。ルートにlogをつけるのは間に合わないだろとツッコむか迷ったが、無言を貫いたらいつのまにか実装終わらせて通っていた。

後から確認したが、 $n$ や $q$ が $2\times 10^{4}$ 程度だった。それは通りますねぇ.....

チームメイトが通していた。実装でバグらせていたので、デバッグに参加した。

問題文見てすぐdpを考えた。 $(i, 1)$ からわかるマインスイーパーの情報は $(i - 1, 2), (i, 2), (i + 1, 2)$ にしか影響しない。 $(i, 1)$ の情報を参照している時に $(i, 2)$ のマスの地雷の有無を決定しようと思ったが、うまく遷移が立たない。困った。

CのデバッグをしたりHの話を聞いたりしながらぼんやり考えていた時間が長かった。 $(i, 1)$ の情報を参照している時に $(i + 1, 2)$ の地雷の有無を決定するように考え直したら、いい感じに遷移がたった。 $(1, 2)$ の地雷の有無は全探索すれば良い(円環上のdpのように、 $2$ 周同じdpをする)

わりとすんなり書けた -> WA 助けてくれ〜

愚直やランダムケースまで書いて、自明なケースで枝刈りした際にプログラムを終了させることを忘れていたことに気づく -> AC

....何しているんですかね？

チームメイトが解いていた。

素数は必ず美しい数であり <- 天才

素数砂漠が小さいことから $N$ 以下の素数は $N$ に近い -> $N$ から愚直に美しいか判定すれば良い

自分がかなり嘘を言った。 <- 助けてくれ

かなり迷走したあげく、自分はGにまわることになった。2人がFの考察をしている間にGの実装を進めた。

Fが解けて、実装も間に合いそうということで、(こちらは逆にデバッグも大変そうだし)二人に託すことにした。どういう解法に至ったのか聞き忘れてしまった。後で提出コードを確認してみます。

スタートとゴールから01BFSをすればあとはちょっとした調整を頑張るとできそうと主張した。チームメイトから「板を置いた後すぐぶつかるような移動のみ考慮すれば良い」と予想をもらった。これを信じて実装を始めた。

01BFSまで書ききったところでFの考察が終わり、そっちにパス。

コンテスト終了後に通そうと思ったが、やる気が0になってしまった。AOJ上でidが振られたら復習の時にやります。(ほんとかな？)

チームメイトが解いていた。

$N$ が偶数の時はAliceが必勝とチームメイトが主張していた。納得できた。その後はもう一人のチームメイトが逆形のNimをすれば良いと主張 -> チームメイト二人で実装してAC

逆形のNim自体初めて聞いた。ABCで殺される前に知れて良かった。

問題文開いて謎の曲線が見えて^^になって閉じた。

day1コンテスト後

疲れすぎて目眩がしていたので、懇親会は欠席。空腹もあったが、とにかく寝たかったので夕食は抜くことにした。

立命館の懇親会参加勢がおにぎりを買ってきてくれた。本当に助かりました。ありがとうございました。

仮眠をとった後、ABCに参加

面倒でない。助かる。配列を使わないで実装しようか少し迷ったが、結局配列で入力を受け取ることにした。

実装ミスって1WA。何をしているんですか？

$K$ より大きい値もsetに突っ込んでしまい、解が合わず首をかしげていた。

dp。

後ろからやると簡単になる。これ気づいた時自分天才だなと思ったけど、そうでもないらしい。

$W$ 確保すべき配列を $H$ 確保してしまい1WA。何をしているんですか？

かなり実装に手間取った。解法に至るまではあまり苦労しないけど、実装に手間取る問題はチーム戦でやると楽しいんだけど、今回は個人戦。

1WAしたあと、すぐ死亡ケース「aaaaa aa」に気づけたのが運が良かった。

1800diff出てて助かった。私は実装下手こいたけど、皆も下手こいたんだなぁ。親近感。

何をしているんですか？

区間種類数クエリをやる時と同様に「 $i$ 以上の $A_{i}$ と同じ値が出現する最小のindex」を管理することで解けたつもりになった。間に合わず。upsolveはまだしていない。

同じ宿の人と感想戦をして、24:30就寝

day2

起床時間忘れた。同部屋の中では遅かった方だと思う。

会津・立命館の人と喫茶店にいった。トーストとコーヒーを一杯。お腹が空いていたので写真を取り忘れてしまった。

JOI・PCKの話や競プロの実装の話をした。基本的に競プロの話を他人としないので、こういう機会は貴重だ。楽しかったです。

day2 コンテスト後

コンテストの話・セットの問題の思い出は長くなってしまったので、後に回しました。

解説発表前に立命館の人から感想を伺いました。コンテストが終わった時は0AC2問、0完チーム発生ということでコンテストとしては少し失敗だったかなと感想を聞くのが怖かったです。そんな中立命館側から話しかけてきてくれて嬉しかった。

解説・講評をしてそのまま解散。解説の時にN問題のスライドがすっぽぬけるというアクシデントが発生しました。申し訳ありません。

南草津駅周辺のビジネスホテルを予約していたので、そこに移動。夕食はコンビニのざるそば。ぼーっとして体を休めた後、ARCに参加。

やはり一問目から難しい。ARCだなぁ。

10分くらいお絵描きして、人 $P_{1}$ がスプーンを取ると、以後の人の取るスプーンが固定されることに気づいた。そこまでわかったが、公式解説通りの「全員がL, またはR」みたいな見通しの良い解釈はできなかった。どうして.....。とはいえもう解けたのでとりあえず実装。サンプルが揃わない。少し悩んだのち愚直書いてデバッグ -> $N = 3$ でのhackを見つけて修正 -> 全部揃う -> AC

こっちは以外と？

最初はとっかかりに悩んだ。5分くらい考えて「()を取り除いて)))...((((....みたいな場合のみ考えれば良い」と気づく。この場合はswap1回かreplaceをhoge回でかっこを一つ崩せる。

-> 実装 -> サンプル3が揃わない

サンプル3でswapが何回、replaceが何回行われているか数える。ここで最適解の構造を完全に理解したのでコードを修正 -> AC

うーーん。何もわからない。

C: 総和の最小化問題すらちんぷんかんぷん。助けてくれー
— カスタネット (@zawakasu) 2024年3月24日

Xをぼんやり眺めたりして、1:30に就寝。

day3 (ちょっとした一人旅)

8:00に起床。朝食はホテルのバイキング。ちょっと仮眠を取った後、10:00にチェックアウト。

電車で大津市に移動。

琵琶湖を見てきました。あいにくの霧、小雨。

セイコーマートでお土産を調達

昼食は京都駅周辺のフードコート(京都タワー地下1階)で出汁茶漬けを食べました。

まず、フードコードの雰囲気が良い。黒を貴重とした店達を暖色系のライトで照らしている。千と千尋の神隠しの舞台の様な(良い意味で)怪しげな雰囲気がある。
丼のおかずを二品好きに選べる仕様。今回は鮭と明太子を選んだ。鰹やすき焼き、ホルモンなども選べた
明太子がめっちゃうまい。ピリピリと心地良い辛味が舌全体に広がって、旅の疲れを癒やしてくれる

その後は何事も無く帰宅。滋賀旅行完全終了......

day2 コンテスト

https://onlinejudge.u-aizu.ac.jp/services/room.html#RUPC2024Day2/info

後ろでClar対応をしていました。

自分の難易度予想

C<H<L=B<M=I=K<A=J<G=O<D=N<F (Eは解いてないので知らない)

部全体の難易度予想

C<H<L<B<E<I<M<A<J<K<G<O<D<N<F

解かれた数の多い順

H>L>B>C>E>A>N>M>K>D=I=J>O>F=G

問題順はランダムに決めました。意図的にOO問題をO番に置くなどはしませんでした。

テキストベースの詳しい解説を(部では無く個人として)出したい欲があります。AOJ上でidが振られたらやるかもしれません。

全体的な反省

コンテストは5hにすべきだった

実のところ、作問チーム全体の意見として「このセットで全完は確実に出る」と考えていました。難易度推定力の未熟さ故、今回のセットを5h並列ありにする選択はあり得なかったと思います。次回会津大セットを出す機会があれば今回のセットを参考にして問題数や難易度を調整していきます。

問題数が多すぎた

他の部員がどう思っていたかはわかりませんが、私は問題数は多めの方が良いと考えていました。いろんな分野の問題を揃えておけばコンテスタントが何かしら得意な分野の問題を見つけて、より沢山ACが届けられるかなと思っていました。実際は逆で、問題文を読む時間、どの問題を解くか選ぶ時間が増える一方でAC数を減らす要因になってしまったようです。

簡単枠の発見が困難になってしまい、結果0完太陽のチームが生まれる...という避けるべき事態も発生しました。

上級者相手にも耐えうるセットを作れた

難易度推定は見誤ってしまいましたが、ありありありのルールで4h耐えるセットを作れたのは自信につながりました。

難読

問題文校正はしっかりやったつもりでしたが、まだまだ理解が難しい表現がいくつかあったようです。申し訳ありません。

原案時の問題文を参考にして問題文の初案ができる -> テスター作業時にしっかりめに校正を行うという手順を踏んでいましたが、これが良くなかったかもしれない

原案の問題文に感じた違和を問題文校正時にきっぱり忘れてしまっている。
K問題の「接頭辞かつ接尾辞かつ接頭辞でも接尾辞でもない部分文字列として登場する」も問題文校正時には何の違和感も覚えていませんでした。他の部員からも指摘が無かったので、彼らも違和感を覚えていなかったのでしょう。おそらく原案を読んだ時は読みにくいとは思っていたのでしょうが......言われてみると確かにヤバイ文章だ。

簡単枠をAに置く、簡単枠をちゃんと簡単にする

0完太陽は体験として本当におもしろくない。良くなかったな。

day0のところでも書いたのですが、BHLより簡単な問題が一問爆破されているのがあって、セット全体の難易度が上がってしまったようです。

今回のC問題みたいな問題を一番簡単と公表してAに置くと、問題の魅力が減ると考えていたのですが、そんなことはなさそう。ギャグなのは変わり無いし。

ABC-Aみたいな問題を次回から置くぜ！とはなりませんが、素直な実装問題が一問あった方が良かったと思いました。

解説発表の練習を怠った

あがり症が発動。考察上の大切なポイントを何点かいい損ねた。準備していた小話をすっとばす。まいて解説しなければいけない都合上、早口が増えた。緊張からささくれが爆発して指から出血(?!)。など沢山反省点がありました。

次回からは事前練習しておきます。あとハンドクリーム多めに塗っときます。

運営に意見し忘れたのでこの場に書き留めておきますが、持てるタイプのマイクだと嬉しかったです。

各問題の思い出

原案者から解法をすでに聞いていたので、解答の提供とテストケースまわりのみ参加しました。

$N = 200000,\ M = 0$ というケースを追加しました。本問題は木上の最長路問題に帰着すると思うのですが、連結成分毎にこれを解く時にうっかり $O(N)$ でなにかを初期化していませんでしたか？

カクタスグラフの閉路列挙がDFS1回だけでできるというのが個人的にびっくりポイントでした(そして面白いと感じたところでもある)

解説スライドにそのパートの説明がなかったと思うので、ここでほんの少し補足しておきます。

DFSをすることを考えます。stackなどで今までに通った辺を持ちます
辺をたどることで、ある探索中の頂点 $v$ にたどり着いたら、閉路を発見しています。stack上の辺を $v$ を得るまでpopします -> 一つ閉路を得ることに成功している
辺を辿ってDFSの手続きをした後もstackに辺が残っていたら、その辺は橋です

反対にBCTなどを用いた方法をよくわかっていないで、提出コードを見ながら勉強しています。BCT盆栽にほしいなぁ。Lowlinkしかもっていないなぁ。

14AC。全チームがおそらく最初に読む問題であることを考慮しても、難しい問題なので順当な解かれ具合かなと感じています。

最初は $O(M^{2})$ の解法が提案されていた。SA+LAを使うと準線形に高速化できたので、それを提案。後に原案者から「これは $K$ 取ることだけを考えれば良いです」と聞き、なるほどなとなった。全然気づかなかったな。

別のテスターがロリハを用いた簡単な解法を提案。これで現在の問題の形に落ち着いた。自分もこれに合わせて、最近書いたSWAGを用いた解法を提出。半群ってモノイドよりゆるい制約で、勿論モノイドも乗るし、すごいのよ！

解説スライドではSA+LA解にSparse Table RmQと書いてあるけど、実は不要です。

S[i...|S|]と最もLCPが長くなるTのsuffixはSA上で前か後ろに近いところにあります。そこだけを見れば良いので、前計算でできます。

23AC。11分でFAが出たのがびっくり。異次元の実装スピード。

私が原案・Writerです。これはなんですか？

C問題めっちゃヘイト買ってる。闇討ちにあって明日琵琶湖に沈んでるかもしれん。
— カスタネット (@zawakasu) 2024年3月24日

AOJ2432 に似た問題を作りたいというモチベーションから生えました。この問題はAOJ-ICPC難易度600内で初めて解けた問題で、思い入れがあります。

解説スライドの「解法提供: Luzhiled」の部分にお気づきでしょうか。なんと自分は原案提供時、大真面目にこの問題が解けていませんでした。

有向で考えていて、原案提出時にうっかり無向と書いてしまい、解法をもらいそのインパクトから有向で考えていたことを忘却
本当に勘が鈍くて頭がちぎれていて、解けなかった

のどちらかだと思っています。「一つ前にいた頂点」「今いる頂点」をもって行列累乗しようとして、計算量がとんでもないことになっていた記憶があります。

原案を投稿してから30分後に「誤読していなければ良いですが」の書き出しで解法を頂き、頭を抱えてしまった

とりあえず行列累乗を連想させるような制約にしておきました。

ACコードが数行で終わっているのを見るとニコニコになれるし、ACにコードに行列が入っていると更にニコニコしました。

$N^{2}$ 個の頂点を持って行列累乗すると $O(N^{6}\log K)$ かかり破滅する.... はずだったんだけどこの解法でもACされてるっぽい。あれ..
普通に閉路に関する条件を考慮しない場合でやる行列累乗 $O(N^{3}\log K)$ をしてもAC可能。最適解が常にぐるぐるで達成されるのでそれはそうになる...がそれをわかっていると行列を持ち出さなくなる

FAは52分。皆はやめにFAが出たBHL頑張ってた印象がありました。私達としては気が気でなくて、何回か問題文を有向と書いてないか見直したりしました。

0完太陽回避用の問題として用意していたが、自分が思っている以上に避けられてしまった。グラフ理論の用語の理解や、数式を読み取ることが要求されており、とっつきにくかったかもしれない。

おとなしくA問題に置いておけば良かったと後悔
簡単枠にグラフは避けた方が良かったかも
図を入れる

私が原案・Writerをしました。

こいつめっちゃ難しくないですか？？？？？本セット三大ボスの一角です。

大学の情報理論・符号理論の講義の期末試験で「 $N$ 個の符号語からなる接頭符号からトライ木を構築すると、 $N$ 個の葉ができる」ことを利用して解く問題が出題されました。

全問題解き終わって解答を見直しているときに「この性質競プロっぽいな(?)」と思い、ぼんやり考えているとこの問題とその解法が頭に振ってきたので、いても立ってもいられず試験を途中退席して原案を仕上げました。

Binary Trieをライブラリとして持っていてもどうにもならないタイプだと思ってて、実装が大変な問題です。

私が書いた解法は151行、テスターも同じくらい行数かかっていました。

AC数は $4$ 、IJと同じAC数です。IよりFAが早く、多くの人が目を通したかもしれません。

問題文校正以外何も関わっていないです。未だに解法すらわかっていない。サンプルを見る感じ、解がすごい小さいのでそれを利用するのかな。

かなり難しい問題だと感じています(自分が解けていない以外の根拠はありません)が、Testerは全員簡単めと主張していました。実際沢山のチームに解かれました。

ARCっぽい見た目をしている。自分もこういう問題を作問できるようになりたい。

私が原案・Writerしました。三大ボスの一角にして本セット最強の問題。

JAG2023夏合宿day1(韓国のセットだっけ？)になんちゃってFunctional Graph上の最長trailか最長pathを求める問題が出題*1されていて、そこから着想を得ました。

実情は「単純な観察の後に場合分けを制し切る」という問題です。無限時間あれば(最低限の知識は必要ですが)実力関係無く確実に通せるタイプの問題でした。問題数が多い本セットとは相性が悪かったようです。それも相まって0submission, 0ACでした。温存しておけばよかったか.....

Testerから「解に寄与する $(|A|, |B|)$ の組は $O(\sqrt{N})$ 通りしか無く、愚直にchmaxしても通る」という予想を出されました。実際にそのような解法の実装が高速に動作しており、最後まで落とすことは叶いませんでした。実際に解に寄与する組の数が $O(\sqrt{N})$ になるケースを構築できたのですが、それより組の数を大きくするケースを構築する方法がわかっていません。この予想は真なのかもしれない。

Kuma_and_Foodsチームがコンテスト後over16分でACしていました。惜しい.....。でも着手しACまでしてくれたという事実だけでも嬉しいです。

珍しい枠

操作回数を最小化する戦略は早めにわかって、立式もできたので後は必死に肩にmodintを乗せる方法を勉強していました。modintの肩にmodintを載せるやつは除算をすることができませんが、本問題では除算した値を肩に載せることが無いので、うまくできます。知識だけかと思いきやちゃんと考えるパートもあって、面白いのではないでしょうか？

必死こいて実装したものが最初WAになって絶望したが、落ち着いてこれでverifyしたら落ちてしまい謝りながら修正したという思い出があります。

modintの肩にmodintを載せる方法はこの記事で勉強しました。

hos-lyric.hatenablog.com

中国剰余定理から素べきmodの組と実際のmodの値に対応があるというのがミソだと思いました。

沢山勉強したので、この記事や東工大の記事の行間を埋めたものを記事に出すのも良いかもしれないですね。

ところでこの $a^{b^{c^{\dots}}} \pmod{P}$ みたいなタイプのmodintのverifyはLCにあるのでしょうか？

https://judge.yosupo.jp/problem/tetration_modが該当するのでしょうか？何もわかっていません
もしないなら、LC詳しい人、issueを投下してくれよな！

コンテスト中「Gはこの世の終わりみたいなことを求められている」みたいな会話が聞こえてきて吹き出しそうになった。

0ACでしたが、コンテスト後にACが生まれました。ありがとうございます。Writerもきっとよろこんでいます。

簡単枠

個人的にかなり好きな問題です。 $O(\min(M, N - M)N)$ って珍しくないですか？

$M = N, N - 1$ だけ場合分け(後者は両側累積和)して後は全探索の解法を提案していました。別のTesterからdpでええやろと言われアハ体験。

原案者多忙により私がWriterをしました。

基本的に原案者は問題だけぽんと置いて解法は懐にしまっていたので、この問題もWする前に自力で解きました。実は考察に数日かかってしまいましたが、ABC-EFにありそうな解法に帰着したので「自分が盛大に事故っただけか....」と難易度低めに予想していました。テスター達も青diff程度と予想していました。

蓋を開けるとFA2:32, 4AC。何の何の何？！！！

実装も辺番号とグラフに対応させるのが中々難しい。冷静に考えると簡単な要素があまりありませんでしたね。

図が無い、辺の重みの与えられ方が謎(これは入力の数を減らす以外の理由はありませんでした。これに注目して考察していた人がいたら申し訳無いです)などの非本質な理由で手をつけるチームが少なかったかなと思いました。反省です。

イメージがしやすい様に「ラダーグラフ」という独自の単語を生んでしまったのですが、それをするなら図を置いとけという話でした。

私が原案・Writerをしました。

自分がWriterをした中では一番気に入っている問題です。前々から直径に関する出題をしたい*2と考えており、この問題の構想自体は7ヶ月前にありました。

原案募集期間中にうまく解ける形になったので提出。

Jに提出をしたほどんどのチームが「64/66 WA」のジャッジ結果を見たと思います。これはテスターの一人が用意してくれたケースで、どんなケースかは解説スライドに載せました。直径の端点となりえる頂点を含まない部分木は存在しないものとして扱わないといけないんですね。

このテスターの解法の証明も自分のものよりスマートで「参りました....」って感じでした
このケースが他のテスターを刺しまくっていたようです

4AC。FAがかなり早く、多くのチームに読まれたことを踏まえると、セット内でもかなり難しい問題だったかもしれないです。

The 文字列。

私は10分ちょっとで考察が終わってしまい、Z-Algorithmを知っているか否かがボトルネックになるような簡単な問題と考えていました。他のTesterやWriterは難しめと予想しており、実際6ACだけだったので彼らが正解でした。自分が難しいと考えて実際は簡単だったEと逆ですね。私は推定が下手くそ。

$Q\ \le\ 10^{6}$ と $Q$ が大きめですが、 $O(Q\log Q)$ 解法をハマらせる意図はありませんでした。(そもそもWriterの解法が $O(Q\log Q)$ でした。)原案者は何想定だったんだろう。聞きそびれてしまった。

私もいくつかテストケースを追加したのですが、それで刺せた提出はありませんでした。そもそもsubに対するAC率が高い。

私が原案・Writerをしました。

なんかの機会があって、WkipediaのArgmaxの記事を読む機会があったのですが、競プロに使えそうだなと思いそのまま問題ができました。

解説スライドの式変形のラストのパートはABCでも既出で、記憶に残っている人も多かったかもしれません。でもやっぱりWolfram Alphaに突っ込んでおくのが一番楽。

解説発表の時に「 $f_{i}, b_{i}$ の計算はfenwick treeの典型的な操作」と言った覚えがあるのですが、正しくは「fenwick treeの典型的な応用例」ですよね.... こういう細かな表現をおろそかにするから問題文が難読になってしまう....

私が原案・Writerをしました。

最適化の問題が足りていないことが作問チーム内で問題になり、自分がストックにあったものの中で適当な最適化(最適化というより、フローでできるやつ)を一つ提案しました。それがこれです。

あまりにも典型すぎてサクサク解かれるかなと思ってましたが、(問題数が多すぎるなども相まって)8ACで止まりました。

最初は「Aizu」ではなく「Luzhiled」を書かせる問題でしたが、二問も擦るのは恥ずかしい&申し訳ない気持ちになって「Aizu」に変えました。作問チームには「定数倍がでかすぎて困っているからAizuに変えたい」みたいな最もらしい理由を言って変えました。あれ建前です。ごめん。

コンテスタントのうち何人かはbitDPで通してきました。非想定解です。自分もよくわかっていないので、コード読んで勉強しています。

私が原案を出しましたが、解けませんでした。解法だけ別の人にもらい、Writerしました。

「Luzhiled」の発音が「Luzhil + 度」に思えたので、「luzhil」になにかをこじつけて問題を作ろうと思いました。結果的に縦棒があるl, hに注目して、現在の問題設定ができました。

「l, hの数 - 他の文字の数を状態としてdpする」という初手のステップがそもそも難しいように感じます。「過半数・半数以上という条件に対して半数以上にしたい対象とそれ以外を組にして考えるテク」はこれ(ネタバレ注意)などでも要求される典型的な考察手法だとは思うのですが、自分は思い付けませんでした。

多項式的に解釈するといくつかの $24x + 2x^{-2}$ と $x$ と $x^{-1}$ の総積を求めるという問題になるのでしょうか。総積系でも次数の和が抑えられているので、exp -> logではなく(そもそもexp->logを知らないからなんとも言えん)分割統治の方を使います。

三大ボスの一角でしたが、9ACと他の問題と比較して多くのチームに通されました。人類数え上げが得意すぎるぜ！

解法がわからず、Writerに解法を聞き解説ACという形でTester作業しました。

高校数学の三角関数をいくつか復習しました。受験勉強で沢山触れたつもりだったのですが、忘れてしまうものですね。

二つの点の距離が $H$ や $W$ になるような回転角が存在しないときに、回転角tex: 0で条件を満たすか判定することを失念していて、それに数時間ハマリました。色々罠があったと思うのですが、時間内にキッチリ通してきているチームはすごいと思いました。

問題文の校正が全問題中一番大変でした。展開図の座標の列をどう説明すればいいのかずっと悩んでいました。

おわりに

書きたいことをつらつらと書いていたらこんな文字数になってしまいました。最後までお付き合い頂きありがとうございました。

またどこかで会津大学セットを提供できるように、作問を貯めておきます。

重ねてになりますが、RUPC2024運営の皆様、今回は素晴らしい機会をありがとうございました。

*1: $N\ \le\ 10^{6}$ なのに1secで全然通せなかった記憶がある。少し恨んでいる。

*2:こちらのスライドにある直径のテクニックが好き