UTPC2023 開催記

UTPC2023 を開催しました

atcoder.jp

めっちゃ遅いし今更かな～と思ったら誰も開催記書いてなくないか？？？

各問題の感想+運営面でのザックリとした反省点を書きます。難しめの問題は大体解いてて簡単目はあまり通してなかったりするので短めになるかも。大いにネタバレを含むので注意。

問題の感想

A- Again Make UTPC

U > T > P > C なの気づいてましたか？僕は知らなかったので提案されたときビックリしました。

元ネタの Make UTPC と同じくなんとなく解けそうなことはわかるが場合分けが地獄になる問題。前回以上にヤバかったみたいで開始後しばらくWAしかでてなかった。 Contestant じゃなくてよかった～～～～～～～～～～～～～～～～

B- Black or White 2

構築問題。損失最小 0 じゃないと解けない気がするけど構築できね～～～～ってなってました。しばらく考えて階段状に黒にするのが強いことに気づきなんとか AC 難しめの問題が並ぶ今回のセットの中で、これ考えてもらえば暇しないかな～という枠でした。

C- Contour Multiplication

典型枠だと思ったら思ったより解かれなかった。 2^{N-1} の位が 0,1 のケースでクエリを言い換えればあとは問題が 2 分割されるだけで解けるいつものやつです。

最初は足し算だったけど畳み込みで解けるらしく、一般 mod で逆元をなくすことで対応。

D- DRD String

面白かった。最初 D の長さについて包除原理つかって答え計算してみるか～とやってみると二乗でも解けず崩壊。最初から考え直して解説通りの解法でACできました。

はじめてみる結論でおもしろいな～と思ったら準備中にARC-Fやらゆるふわコンボス問などで急に出題されだした。

E- Equally Dividing

構築問題 2 。両方奇数のケースにしばらく悩んだので黄diff評価出してたんだけどかなり解かれて最初びっくりした。

あとから atcoder.jp

とかで解けることを知った。

F- Flip or Not

ヤバ問題 1 。とりあえずぱっと見だと全然解けなくて \mathbb{F}_{2} [x ] での話になるんだろうな～と思って言いかえを考えるがわからない。結局解説みてあ～となった。最初の言いかえも難しいし後の処理も自分の方針だとかなり大変。

AtCoderとかほかのコンテストでもこの手の問題あまり見なくて

atcoder.jp

ぐらいだったので評価難しかったが、最終的に HoMaMaの 1AC のみとなってしまった…

G- Graph Weighting

最初全域木の重みを共通にできるか？という問題で、これは自分でも考えたことあったので典型かな～と思っていたらいつの間にか魔改造されていた。二重頂点連結成分の頂点数で分けると凸になって、あまりごとに考えると片方凸のmin-plus convolutionになるのすごい。

pypyでだれも通してなかったので二重頂点連結成分分解やmonotone minima・SMAWKを非再帰でかいてチャレンジしたがギリギリ通らず。結局頂点数の昇順に畳み込んでいたのを降順にすると倍ぐらい速くなってACした（ちなみにSMAWKの定数倍がおもすぎてmonotone minimaに余裕で負けてて泣いた）。

H- Huge Segment Tree

最初非再帰セグ木でクエリが分割される過程に基づいて数えようとしたが全然解けない。考え直して木を上からみて左、右に行くパターンと分かれるパターンで分けて考えたら解けました。計算もそこまで複雑じゃなくて比較的簡単目な印象。

I - I Love Marathon Contest

大体集まったから問題セット決めるぞ～！となった1日前にnoimiが投げてきた問題。評価できないからもっと早めに投げてくれ…

かなり面白め+難しめの数え上げだと思うのでぜひ挑戦してください。

最初noimiはラストランナーが累積和最小で一番右のやつとして考察して「最初と累積和最小で一番右の走者を抜かして考えればいい」ととしてましたが、ラストランナーについては嘘で、tokusakuraiと一緒に証明を考え直してました。たまたま結論があっているおかげで「」内の考察がすんなりでてきてますが、実はこれ天才言いかえじゃないか？と思ってます。

J- Japanese Gift Money

エスパー問題？ちょっと悩んだ後に試しに A_i 進数にすると実は単純になる？とエスパーして成功しました。必要十分であることを示すのも簡単ではないと思う（自分はすぐできる思ったけど後で考えると間違ってた）。ただコンテストならエスパーでいいので…

K- Kth Sum

SSRSが2600diffぐらいといって投げてきた問題。全然解けなくて泣きました。解説みてこんなことできるのか～と感心。

コンテスト2日前ぐらいにtorisasamiが賢いけど単純な O(NK^{\frac{1}{3}}) 回を出してきて、落とそうかなやんだけど結局無理でした。

こんな感じで想定解の通りにやるのは難しいと思うけど、3人いればたぶんいろんな嘘や謎ヒューリスティックを組み合わせて通してきそうだなと想像してました。大体想定通りの通り方だったと思います。

L- Large Triangle

簡単枠をつくろうとなってできた問題。一番長い棒に着目すれば結論がそうなるのはその通りなんだけど、最初ヘロンの公式で1辺固定したときの最大化は～とか考えて単純な結論にならず解けなくて泣いた。

M- Majority and Permutation

writerしました。最初は

chineristac.hatenablog.com

のC問題のとこに載せた問題が 「 P を逆順にしてもいい」という風にすると天才構築で N=200000 でも解けそう、と思ってARCに出そうとしたが、adminから「自分のブログで言及しちゃってるとちょっと…」と言われ断念。UTPCで出してもいいか聞いてみるか～と思って出したところ、tokusakuraiから「貪欲で普通に解けない？」と指摘されて愕然としていました。

その後「 （のちのP問題）を部分問題として経由すれば O(N^{4}) で解ける！」となって数え上げの形で出したのですが、またしてもtokusakuraiから「実はこれが必要十分条件で O(N^{2}) で解けない？」と指摘されてめちゃくちゃビックリしました。集団作問の醍醐味って感じでいいですね。

ゴミサンプルにしたけどどれくらいエスパーされるのかな～と思ったら4h経っても全然解かれなくて焦りました。

N- Number of Abbreviation

（比較的）簡単枠。たとえば ARC-B,C にあると想定解にたどり着けるかもしれないが、5hで難易度シャッフルでだされると suffix array とか使いそうに見えっちゃって面白い問題だなと思いました。最終的には順位表でわかるし解かれるだろ～と思ってたので AC 数が E > N になったのは想定外でした。

O- Optimal Train Operation

こういうのはまずオンラインオフライン変換！（脳死）をしたらうまくいった。ARC-Fで何回か出ているし高度典型としてみんな（とくにJOI勢）解いてくるかな～とおもってた。実際にforestedさんがFAで予想どおりだ～となったけどAC数は思ったほどは伸びなかった。これまだ典型じゃないのか？

P- Priority Queue 3

writerしました。Mで考えた部分問題がいらなくなって16問セットの予定だったから捨てようかと思ったけどもったいなくね？となって17問に増やして出題。この予定調和dpそこまで天才！って感じじゃないしE8さんとか解いてくるかな～と思ったけど最終的にHoMaMaだけで悲しい… Priority Queue の別verって感じでワンチャンmaroonさんのストック爆破できるか？と思ったけど見た感じそもそもストックになかったっぽい。

Q- Quotient Sum

もともと用意していた問題が一週間前にまさかの爆破。想定解は全然違ったけどX上に別解として流れているのを観測したため出題を断念。

そのあとにtokusakuraiが「簡単枠」として提案した問題。言いかえも遷移の絞り込みもむずくね？となったけどdiscordで誰もつっこんでないから俺がアホなだけか…となったが当日みんなQヤバいでしょと話してた。不安になるからdiscordですぐにつっこんでくれ！！！

運営面での反省点

挙げるときりがないが

  • コンテストの告知が遅い

コンテストページが全然公開されなかったしオンサイトの募集が始まったのが締め切り1週間前とかだった気がする。ヤバすぎ

  • 会場がわかりにくい

今回MCDさんの会場を貸していただけたのですが（ありがとうございます！！！）、地上から入れないというのがあまり伝わってなかったみたい？で迷子が多発した。次回以降は地上から地下へのルート案内も流しておこうと思います。

  • 重要な連絡がうまく伝わっていない

上記の会場の件だったり、名札につかうconpassのアイコンの画質が低いのを変えてほしいといった連絡があまり伝わってない気がした。

これはたぶん連絡をXでの公式アウのpostに頼ったのが原因で、そもそも公式アカの存在を周知していないのもヤバいのですが、postしたタイミングでTLにいなかったらそれっきりなんですよね。次回以降はオンサイト参加者専用のdiscordサーバーを立てることなどを検討しています。

  • 懇親の時間が取れなかった

これの原因なんですが、撤収時間を把握したのが2,3日前とかでした。MCD側との相談はもっと前からやっていましたが撤収時間を交渉役が全体に共有していなかった+交渉役に聞いておくのを全員忘れてた Ω＼ζ°)ﾁｰﾝ

来年以降はもしかしたらコンテスト時間をずらして対応するかもしれないです。

ARC165を書きました

atcoder.jp

久々に作問記

問題の解法のネタバレを含むかもしれません。

A: Sum equals LCM

元ネタは箱さんのこの問題です。

yukicoder.me

「順列 P を N 回かけて P_i=i が成り立つのは P が長さ N のサイクルからなるときのみ」が成り立つと思い込んで証明してみようとしたら全然嘘でしたがARC-Aっぽくなったので出しました。

なんで300じゃないの？って言ってた人を観測しましたが、これは自分のAがだいたい炎上しがちだったので怖くなって高めにつけたからです。testerには300評価の方もいました。

B: Sliding Window Sort 2

ARC-Aつくりたいな～と思って適当に作ったら難しくなっちゃった枠。自分で考えたときは割とすぐに後ろ K 項ソートがつよいな～になって時間かけずに解けたのですが、難しかったらしい。B-Cのtesterの評価が分かれてたのでB=Cにしたけど自分は B > C 派だった。

 

嘘解法が通ってたのはマジですいません…

postしたように P_{n-k} \gt P_{n-k+1} のケースしかなかったのが1つの原因です（これを解消するテストケースは追加したがそれでも落ちない嘘解法があるらしい…）。

こういうミスはシステム的に防ぎたいのですが、マルチテストで小さいケース全部いれるなど小手先の対策以外に思いつかないので厳しい。

…と思ったけどこれ条件追加したりすれば数え上げにできたしそれなら嘘考察は通らなかったかもしれませんね。今度からARCは6問全部mod 998244353にします。

C: Social Distance on Graph

適当に作った枠。Social Distance ~ っていう題名の問題をちょくちょくみかけたので自分も名前から作ってみました。二分探索から考えれば素直な考察だと思うし、同じ点数のBとばしてC解く人多いんじゃないかな～と思ったけどそこまで解かれなかった。JAG合宿で他の人に話を聞いたところ序盤だとさすがに解かなきゃダメだろという気持ちになって飛ばしずらいらしい。なるほどなあ。

D: Substring Comparison

お気に入り枠。「部分文字列の辞書式順序比較によってminimum cyclic shiftを求めよ」というインタラクティブ問題を考えた後 adaptive にできるかな～と思ってでてきた問題です（元問題は非想定が強くて廃案）。最初は比較が定まる位置を決め打つとかして解けるわけね～ってなった後考え直したら解けてびっくりしました。

白状すると自分は500点ぐらいかな～と思い「考察要素ないかも…」っていうコメント付きでadminに投げました。adminからは「考察要素あります」というコメントが返ってきました。冷静になるとそれはそう。

解法が全然見たことない感じの問題でどれくらい解かれるかは全然わからなかったですが、想像よりは解かれました。

E: Random Isolation

適当に作った枠2。AGC058F をみて指数個状態がある期待値問題作ってみたいと思って作ってみた問題です。期待値の線形性は指数個に分けても最終的に状態をまとめられれば計算できるんだな～というある意味教育的な問題にもなったかなと思います。Dと比べるとこっちのほうが典型的だしmod998だしAC数多くなるか？と思っていましたが結構差がでました。

余談ですが N\leq 1000, K\leq 10 とかで出題する案もありました。\Theta (N^2(N-K)^2) を \Theta (N^2K^2) にしてね～という意図の案で、本質からすこし離れた改善を要求するのでめっちゃ文句いわれそうだと思いやめました。ただ \Theta (N^5) をやっている人が多かったのを見るとこれもありだったかもしれない。

F: Make Adjacent

本棚の整理をしているときに考えた問題です。最初は良い数列にする最小の操作回数を求めろ、という問題でしたがあまりに無。最終状態には自由度があったので辞書式順序最小化できるか考えてみたところ、時間はかかったものの解けたのでこの形で出題しました。

いわゆる「低い項」の管理ができるデータ構造をつくれという問題で、典型そうな見た目のわりに自分は見たことなかったのですが、adminにみせたところ有名といわれました。やっぱりそうなのかー

データ構造ゲーなのでJOIerが有利だろうなと予想したところやはりCyanmondさんが解いて銀パフォ決めてました。予想あたってうれしい。

全体の感想

ようやくまともな難易度のAが出せたと思ったらBでチョンボしてしまいました…

4-6-6-7-7-8という異様な配点で騒がれてましたがB=Cにする都合で両方6がついただけなので C5 にすればちょうどよかったのかなーと思っています。

後半は優しめ（当社比）なので全完で1ページ目が埋まったり、Fが金属diffを回避できるかなと思いましたが、残念ながらそうはなりませんでした。くそー

来年度はさすがに国試勉強に集中することを考えると、writerはあと2,3回で終わると思います。もうすこしお付き合いください。

ICPC2023 国内予選 参加記（chinerist視点）

チーム　The Raspberry Candies で出場しました。乱文許してください。

チームメンバー

rniya 最近調子よくてレート爆上がり中 そのせいかまったく緊張をみせない

tabr ありとあらゆるコンテストに出まくっている 環境構築のプロ

chinerist pythonistaなのをいいことに考察だけして実装丸投げする係 楽しい

チームメンバー間で得意不得意の差はあまりないと思う。ただ全員構築が苦手で去年は2h30m時点でEが解けず予選落ちしかけました。

チームの戦略としては自分が考察得意よりとされた（本当？？？？？？？？？）+普段pythonメインなので、実装にはかかわらず考察を投げまくるのに徹していた。

当日までの練習

おもに土曜ののUniversal Cupでチーム練習。去年は本郷にきて対面で練習していたが rniya が本郷に行きたくねえと駄々をこねたので1か月前まではオンラインでやっていた（まあ本郷遠いし気持ちはわかる）。2週間前には自前のパソコン禁止、プリンター持ち込み禁止などの制約に合わせた動きの確認とかやってた。

当日

自分は実習の試問が直前まであったので終わった後急いで浅野キャンパスへ向かった。遠い…。 到着した後は東大生チームの多さに改めてビビり、予選突破できるか不安になりながら動きの確認をした。 10チーム分の印刷を1台のプリンターでやる以上、紙で届くのは時間がかかるので

  • tabrが環境構築している横でrniya、chineristでA,Bざっと見、C以降の問題文をじっくり読む
  • 環境構築おわったらrniyaがA実装、chineristはこの段階でC,Dの考察を始める
  • rniyaがA倒したら tabr がB実装
  • この辺で問題文が届くだろう、以降は考察できた順に

っていう感じで決めて臨んだ。

他には練習中に問題文誤読したのを又聞きして2人で全く別の問題を考えて時間を浪費するのを何回かやってしまっていたので、問題文の又聞きは禁止してダブルチェックすることに。

コンテスト

開始後、tabrが環境構築している横で問題文を読む。

A,B:ぱっと見Bはめんどそうだけど自明ではありそう

C:構築 去年のトラウマがよみがえる　ICPCで構築出すの禁止してくれ

D:変な問題　答えが小さくなること以外はパッとはわからない

E:n<=6000で総和が105以下？変な問題ではなくて通さないとダメっぽい

とEぐらいまで読んだところでtabrが作業を終えrniyaがA開始。自分はCを考えてみる。左右をひっくり返したりしたがどうしても1個だけやばくなるなあ、ぐらいの考察でとまっているうちにrniyaがAを倒したのでrniyaにCを押し付けてDの考察を開始。

D

Cが構築で動揺していたが冷静になると部分和問題でまともな貪欲とかが成り立つ気は全くしない。じゃあ全探索路線で考えるか→6個以下に分けるのだけ探索すればいいしそんなに時間かからずにおわるだろうと考えtabrに伝える。

この辺で問題文が届いたのでF,Gも読んでみる。

F:ここで幾何か～　面白そうだけどこんなんできるか？

G:サイコロ！？ライブラリ持ってね～、と思いきやそういう問題ではないらしい　読み終えた段階でABC257Exが想起され難しそうな気がしてくる

そうこうしているうちにCできたかな？と思って聞いてみると、行けると思った解法に穴があったらしい。ということでいったんtabrがDを実装することに。途中総和がnを忘れていたり部分和問題の結果がsと完全一致判定になっていたりしたが、わりと早くに指摘できAC。

この後はrniya+tabrでCの修正、chineristがEの考察を行うことに。コンテスト開始1hぐらいでCの修正案がでてきてAC。この時点でわりと出遅れてそうだな～と思い焦る。

E

Eは片方だけならLISだな～と考えて以降はn2テーブル必要になってダメだな～と思ってしまいあまり進まず（Eは勝負枠になるだろうという心づもりだったので無意識にn2はダメとしてしまっていた）。以降しばらくEとFを行ったり来たりしていた。しかしrniya,tabrがCから帰ってきたところでこれを伝えるとn2でいいんだからこれでよくね？となったので詳しい考察と実装を2人にまかせてFの考察を再開した。

F

サンプル1ができてサンプル2ができない理由を考えてみる。サンプル1はスライドで埋めれているからサンプル2はスライドしても無理なのか？と考えてみる。しかしサンプル2の図にいろいろ書き込むと凸にできる気がしてあれ？となる。考え直してみると配置する個数有限個になってないですね。じゃあサンプル1はなんで有限個でスライドみたいなことができるのか？と考えてみるとどうもへこみの前後の線分のおかげでできてるっぽいことがわかる。ここまで考察した段階で合流したtabrが

tabr「サンプル2Yesじゃね？？？」

と自分と同じ勘違いをしていたので考察を伝えると

tabr「じゃあ前後の線分が同じ直線ならいけてそれ以外無理なんじゃね？」

といわれる。他に条件がある気もしたが言われてみればたしかにそれで必要十分になってそう。ということで実装をtabrに任せてGの考察を開始。たしかこのぐらいにrniyaがEを通してくれた。

G

Gは不公平さへの各さいころの正確な寄与を把握しないと始まらないのでとりあえず式を展開してゴリゴリ計算していくと、結局サイコロの出目の期待値の総和2人分をkeyにしてdpで最小化すればよさそうというところまで行く。これだけだと606ぐらいだが

rniya「手元ならそれでぶん回そう」

と言われたのでとりあえず考察中にぶん回してもらうか、となり詳しい計算を説明…している最中に自分が書いた式をみるとどう見ても差だけでいいです（バカ1） まあでもこれでも7200n2mだからもうちょい改善考えようかな～

rniya「いや…これで間に合ってない？」

と言いたげだったのであれ？と思い見直すと7200にnが入っているのでn1個余計で7200 * 3600です。余裕やんけ（バカ2） ここまで話したところでtabrのFの進捗をみるとどうも凸包ライブラリが他のいろんなライブラリに依存してて思ったより大変そう、となったのでGを先に実装してもらうことになった。 途中2乗の期待値の36倍が2乗和になると勘違いしているのになかなか気づかず、答えが負になって首をかしげていたがなんとか気づいてAC

ハプニング

その後 Fの実装を再開したが、他のいろんなライブラリに依存してて思ったより大変そうというのを聞いて

chinerist「凸包ぐらいなら自力実装したほうがはやいんちゃう？」

と言ってしまった。結果的にこれで凸包構築の段階でバグらせてしまい、たぶん普通に写すより時間がかかってしまった。デバッグ出力をしまくりどうも外積の符号で余計な場合分けしているのがヤバそう、と特定しさあ直すぞ！とパソコンに向かうと

プツン…

PCが落ちてしまった。自分らだけかと思いきや周りの東大生チームのパソコンも全部落ちている。どうやら教室のパソコンは19時になると全部電源落とされるらしい。19時とか一番大事な時間帯に落とさないでくれ～～～～～～～～～～～～～～～～～～～～～～～

5分後くらいに再起動できたので修正。Yes,Noしかないので不安になりつつ見守るとそこにはCongulaturation!の文字が! というわけで7完に成功しさすがに通っただろうということで大喜び。

H

順位表を見るとまだ誰もH解いていなかったので時間内では無理やろな～と思いつつ一応Hに取り組んでみる。1個以外固定して最適化するとバス停は4辺上とか言えないか？とか思ったが、いろんなパターンを考えるとどうもあまり単純なことは言えなさそうな雰囲気。というかそもそもコスト関数がヤバくてこれをどうにかしないと意味なさそう。フローじゃね？と考え、双対問題とかに直した後 |x_i-a_i|+|y_i-b_i| <= r_i ってどうすればいいんだっけとなったところで終了。

感想+反省

7完4位でした。最近の練習だと失敗多めだったので不安だったが事故らず地区予選進出できて本当に良かったです。MCDigital賞うれしい。

反省点はありまくりで

  • 凸包自力で書いたほうが早いんじゃね？とかいってバグらせて結果的に遅くなった。本番で突飛な行動をするべきではなかったしライブラリももうちょい整備+把握してるべきだった
  • EGあたりで勝手に難しい問題だろうと思い込み解けていることに気づかなかった 難しいと勝手に思い込んでやらかすのは去年の横浜でもやっていたはずなのに…

地区予選までにはなおしてWF狙いて～ 頑張ります

yukicoder No.1933 ABCstring 別解

yukicoder.me

おもしろかったです。writer/testerの方法より多少思いつきやすそうな&文字の種類増やせる別解で解いたので書きます（というか解説の固定方法よく思いついたな…）。

問題の一般化

以下のような問題が解ければいいです。

N 種類の色 i があり、色 i のボールは A_i 個、色 i の筒は B_i 個あります。同じ色の筒には同じ色のボールを入れることができませんが、すべての色のボールが入れられる特別な筒が 1 つだけあります。ボールの入れ方が何通りあるか求めてください。

解法

S=\sum A_i,\ T=\sum B_i,\ U=S+T とします。簡単のためにまず 1 \leq B_i とします。

ボールは同じ色であってもすべて区別します（最後に \prod_{i=1}^{N}A_i! で割ればいいです）。そして「同じ色のボールは同じ色の筒に入れてはならない」という条件について、条件違反をボールごとにみる包除原理で考えます。

色 i のボールのうち、確実に条件違反しているボールが a_i 個であるものとします。ボールの筒への入れ方ですが、確実に条件違反しているボール→残りのボールの順に考えます。

まず確実に条件違反しているボールの入れ方ですがこれは色ごとに独立に考えることができて \prod_{i=1}^{N}\frac{(a_i+B_i-1)!}{(B_i-1)!} 通りです。

この後残っているボールを挿入しますが、これは \sum a_i + T 個のものの列に S - \sum a_i 個のものを挿入と考えれば \frac{(S+T)!}{(S-\sum a_i)!} 通りです。

よって \sum a_i ごとに最初の総積の総和が求まればいいです。これは包除原理による符号や最初に違反する a_i 個の選び方も考慮すると f_i(x)=\sum _ {k=0}^ {A _ i} \binom{A _ i}{k}\frac{(k+B _ i-1)!}{(B _ i-1)!} (-x)^{k} 　の総積をみればよく、 O(U\log^ 2 U) で求まります。

B_i=0 の i については違反しようがないので f_i(x)=1 として同じ計算をすれば求まります。

ARC141 writer やりました

はじめまして

Atcoder Regular Contest 141 で writer をやらせていただいた chinerist です。 yukicoder などで何回か出題や単独コンなど開いていましたがついに ARC の writer をすることができました！

この記事では出題した問題がどのようにして作問されたかなどの作問裏話を紹介していきたいと思います。問題に関するネタバレを含むかもしれないので注意。

作問の経緯

  • A問題

作問したことがあるとわかると思いますが、簡単で面白い問題（かつ既出でない問題）をつくるのは結構難しいです。はじめは ARC141 ということで回分数を題材に作問しようとしたのですが、回文の処理ということで難しい問題だらけになってしまいました。結局1週間前まで粘りましたが思いつかなかったので回文→周期的な数に変えて出題しました。ちょうどコーナーケースもあるし。

 

  • B問題

数え上げの問題出したいな～と思い、「XOR」「増加列」のワードを適当に組み合わせて考えてみたところ、いい感じのギャグになったので出題しました。6問の中では作問にかけた時間が一番少ないです。

 

  • C問題

（難易度めちゃくちゃ外してしまいました。DEFが赤diffやら金diffになった元凶はこの問題だと思います。参加者の皆さん、ごめんなさい…）

お気に入り枠です。原案は

順列 \displaystyle P が与えられる。長さ 2N の文字列 S=S_1S_2\dots S_{2N} であって、 S 、 S_{P_1}S_{P_2}\dots S_{P_{2N}} がいずれも「正しい括弧列」になるものを構築してください。

という問題でした。 O(N^3) で解けます。

ただ本質がまあまあくだらないのでどうにか改造できないかなと思い、まず「正しい括弧列」 S から S_{P_1}S_{P_2}\dots S_{P_{2N}} が「正しい括弧列」になる P を求める問題にしました。次に、これをひっくり返して「辞書式順序最大の P から S を求めろ」という問題にしました。

この段階でもういいかなと思いテストケースを作り始めますが、なぜか P_{2i-1} \gt P_{2i} が成り立つような自明なケースしか作れません。このわけを考えたところで問題の本質に当たる部分が思いつきました。このままだとギャグ問にしてもお粗末なので S が一般のケースでも同じように解けることを確認して出題しました。

こういう風に答えから作った問題だと難易度評価外しがちですね…

 

  • D問題

お気に入り枠です2

競プロで約数・倍数に関する問題を解いているとたまに入力が「良い集合」のときだけを考えればいいことがありますが、僕は「良い集合のサイズは実は小さいので解けるのでは？」と勘違いするのを100回ぐらいやりました。もちろん要素の最大値が 2M のときは M+1,\ M+2,\ \dots,\ 2M で「良い集合」を作れてしまうので特に小さくはなりません。

さて、こういう反例を考えると「良い集合の最大サイズは半分なのか？」ということが気になります。証明を考えてみると 2^k n にわけるといい感じになります。この段階で「元の集合が \{1,\ 2,\ \dots,\ 2M\} でなくても解けるのでは？」と思い考えてみると典型問題に落ちています（ビックリ）。

ただこのまままだとdilworthの定理を用いて無考察で解かれるかもしれません。これを防ぐために「すべての良い集合の和集合、積集合」あたりを求めさせるようにしました。

 

  • E問題

この問題の作り方はB問題に近いです。たくさん頂点、辺があるグラフを考える→「(u,k),(v,k)を結ぶ」というクエリを考える→それだとつまらないのでずらしてみる→考えてみると解ける、といった感じで作問しました。

 

  • F問題

お気に入り枠です3

競プロではたまに文字列削除の問題が出ます。例えば

 

atcoder.jp

や

atcoder.jp

 

です。この2問の大きな違いとして「どのように削除を行っても最後に残る文字列は一意か？」という点があげられます。僕は一意に定まる場合の証明をしたことがなかったのですが、AGC055Bの解説に載っていて納得できました。

さて、証明を読んだ後は「どういうケースで証明が破綻するか？」というのが気になります。一番わかりやすい例としては ABC, BCD などのように suffix と prefix が重なる二つの文字列があるとまずそうです。このような考察をするととりあえず多項式時間の解法は思いつきます。ここからさらにテストケースを作ろうと考察したときに解説の内容にたどり着けました。

結構「こんなの解けたらダメだろ」って見た目になってるし、ARCではあまり見られなかったゴリゴリの文字列問題が作れて個人的には満足です。

 

感想

参加してくださった皆様ありがとうございました！yukicoderでも出題はしていましたが、やはり1000人超の人に解かれたりTLで議論されるのは楽しいですね。次回はもう少し崖がないようにしたいです。

あと今回テストケース作りが結構大変でした（特に F は文字列の問題ということでTLE解法に対応するケースを考えるのが意外と難しかったです。二度と文字列問題作りたくねえ）。こういうのを体験しているとほかのwriterにも優しくなりそうです。

今度がいつになるかはわかりませんが原案がそろったらまたやりたいと思っているのでよろしくお願いします！