うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

ICPC模擬地区予選 2022　準備記

ICPC

ICPC模擬地区予選 2022 参加者の皆さま、お疲れ様でした。ご参加いただきありがとうございました。

以下、各問題に対する貢献（あれば）と個人的な感想などです。

以下、問題のネタバレを含みます

A: Stop & Go

準備されたものを見たら赤になった瞬間に信号に突っ込むケースがなかったので追加しました。
ついでに青になった瞬間に信号に突っ込むケースも追加しました。こっちはいらないかも。

B: 1-Player Concentration

ほとんど何も関わってないです。
難読なのかなと思っていましたがわりとサクサク通されていたのでよかったです。

D: 2-LIS

原案時には {O(N^3)} だったのを {O(N^2)} に落としました。
あとは少しだけテストケース生成をしました。
解説には違う DP が書かれていましたが、自分の解法は

dp[x][y] := (b_{k-2} < x) and (b_{k-1} = y) を満たすような k の最大値

というちょっと変な DP テーブルがうまく更新できることを使っています。これちょっと面白くない？
AtCoder で言うとこの問題が少し近いかもしれません：https://atcoder.jp/contests/abc176/tasks/abc176_f

H: Sloppy city planning

ほとんど何も関わってないです。2
けっこう難しいんじゃないかと思ってましたがかなり通されていました。まぁこのセットの中だとこの位置になるのはそれはそう。
入力サイズが大きすぎて domjudge にアップロードしようとすると 500 が返ってきて困っていたんですが、システム担当者の方がなんとかしてくださいました。本当にありがとうございます。

C: Track Train Trail

データセットを担当しました。
ただ、急遽入った形だったので自分は解いていません。

内部コンテストでの一幕
区間が交わらないマッチングが区間 DP になるのは典型 90 問にもあったはずなのでわりと一直線かなと思ってたんですが、そもそも中国人郵便配達問題の考え方が「次数が奇数の頂点の最小重み完全マッチングを考える」なのを知っているかどうかがかなり大きかったかもしれません。

I: N-1 Truths and a Lie

ほとんど何もしていないですが、一応 {\bmod 2^{32}} で見ると（32 bit 整数型を使っていると）嘘つきが一人もいなくて困る、というケースだけ追加しました。引っかかった人いるんでしょうか。
あとは制約を満たす（嘘つきがちょうど 1 人いる）入力のランダムな生成方法を提案したりしました。
これは、K 頂点 N-1 辺の矛盾ないグラフ（これは各頂点に適当な値を割り振ればできる）に 1 本間違った辺を足すとき、2 頂点の間に直接の辺がないかつ辺素パスが 2 つ以上あること（＝連結かつ間に橋がないこと）が辺を足せる必要十分になるので、二重辺連結成分分解をしたあと成分内で繋げばよいです。
前日の 27 時までテストケースに橋のあるケースが入っておらず、慌てて追加したりしました。翌日の起床時間 8 時。
実は原案時にはこの問題設定の前にもう一つステップがあったんですが、本番 5 日ほど前に改題されて今の問題になったりしています。

L: Tree Automorphism

データセットを担当しました。
木のハッシュについては前回の模擬地区でも出題されていたのでボーナス枠かなと思っていたのですが、思ったより解かれませんでした。
でも確かに子に同じ部分木があったときに具体的に何倍になるのかパッとはよくわからない気もするので難しいかも。
もし根つき木のハッシュはわかるけど根なし木のハッシュはわからない、という方がいたらあとで調べていただけると……。

F: Seimei Handan 999.0

ほとんど何も関わってないです。3
そんな状態で言うことではないですが、もっと解かれると思っていました。
実際に何の文字であるかはかなりどうでもよくて、どの文字とどの文字が同じかという情報だけ欲しいので、「何文字前と同じか」という情報にしてしまいたいのはかなり自然で、そういう情報が一致することと元のパターンが一致することが同値なのもわりと自然なので、あとはウィンドウをずらしながらロリハを更新していけば良い、とかなり一直線だと思っていました（考察だけして実装してないですが……）。

E: Sharp 2-SAT

ほとんど何も関わってないです。4
本当に考察もしていないので何もわからないですが、とりあえず TLE 解を出す、というチームがもっと出てくると思っていました（まぁ FFT の写経が必要になるのでその方針が正しいかは微妙ですが……）。

K: Sort Compressed Strings

データセットを担当しました。
原案時点ではまぁそこまで難しくないでしょ、というような雰囲気だったんですが、実際に実装してみたらかなり面倒でびっくりしました。
その上で、うまく実装すると log が落ちたりかなり高速になったりするのでそれに合わせた制約、実行時間制限にしたら大変なことに……。
これでも展開後の文字列長の最大値が {10^{18}} から {10^{10}} に変更になっていたり（これは実行時間の問題ではなくハッシュの衝突確率が十分に低い証明ができないことが原因ではありますが）、本番 2 日前に TL を 2 sec から 4 sec に変更していたんですがまだ足りなかったようです。
適当なメモ化で現実的にかなり高速になるのでそういうことをした結果通る、というチームが多いだろうという予想をしていたのですが、コンテスタントから見るとどれくらい惜しい TLE なのかはわからないので難しいですね……。
コンテスト中に、1 ケースだけ 4.2 sec かかって TLE、という惜しいチームがありました。
結果的に 0 AC になってしまったのは調整ミスだと思うのでかなり悔しさがあります。

J: Most distant point from the stations

最初は {N \le 100} くらいで準備されていたと思うのですが、いつの間にか {O(N^2 \log N)} の解法が実装されて {N \le 2{,}000} になっており、泣きながら自分も {O(N^2 \log N)} を実装しました。complex<double>.arg() でソートしたら遅かったので泣きながら整数で比較したりもしました。
どうやらまともなボロノイ図のライブラリを持ち込んでいたチームはいなかったようで、0 AC でした。これ {N \le 100} でもよかったんじゃない？ だめ？

G: Avoid bombings

原案、データセットを担当しました。
問題案がなかなか集まらず、ボス問もない（これはいくつかの問題に対する難易度の過小評価もあった）という状態で、問題選定会議の司会をしながら無理矢理捻り出した問題でした。
一週間くらいかけて泣きながら想定解を実装したはいいが他に誰も実装してくれなかったのでこれは出せなさそうかな……、と思っていたのですが、climpet さんが実装してくださり出せる形になりました。
結局提出数 0 だったので我々の努力が報われることはありませんでした。
ちなみに解説スライドにあたかも元ネタかのように置かれている画像は実は元ネタではなく、原案を出したあとにそういえばこんなミニゲームあったな……、となっただけでした。

その他

前回の模擬地区予選（模擬地区予選 2021）から、自分がコンテスト運営責任者を not さんから引き継いでいました（JAG のページ更新してない気がする……）。自分がまとめ役をするようになってからこれで 3 回目のコンテストでした。まだ not さんなどベテランの方々に頼っている部分もかなり大きいですが。
主な仕事としては、コンテストを企画したり、会議を開いたり、スケジュールを管理したり、セット全体の品質を管理したりなどです。その上で他の人と同じように各問題の担当者に入ったりもしています（手を加えた方が良さそうな部分のヘルプに入るのを中心にしたいため、可能な限り入らないようにしてはいますが）。模擬地区特有のことを言うと、icpcsec に連絡してジャッジを貸してもらったり、貸してもらったジャッジにデータをアップロードする、あたりもしていました。そういえば参加者への連絡も（アカウント通達以外は）自分がやっていましたが、それくらいは他の人にお願いすべきだった気もします。
また、今回は久々のオンサイト開催ということもあり、その辺の調整も自分がやっていました。調整、と言っても会場やスポンサーとちょっと連絡取るだけだろ、と思えるんですが、実際には今回はここに書けないような大変なことがたくさん起こり、心が 5 回くらい折れました。
特にオンサイト周りなどで慣れないところが多かったり JAG の人々の時間的余裕ややる気の度合いがわからなかったりで、他の人に責任やタスクを分散できなかったのがかなりよくなくて、特に問題セットのバランスや品質に影響したような気もしていてそこが反省点ですね……。
特に実装量がちょっと多いとかハッシュを取る問題がちょっと多いとかは準備時に気づいていたので何らかのアクションは取られるべきだったかもしれません。
あとどうでも良い寄りのところだと、思ったよりおにぎりの消費が早かったのでおにぎりとサンドイッチが同じくらいの量でもよかったなとなりました。あとお茶多めにする必要もなかったかも。みんな学生なのでジュース飲むっぽい。

おわりに

改めて、模擬地区予選にご参加いただき本当にありがとうございました。
JAG の問題セットは、数少ないまともな問題案の中からなんとか絞り出しているような感じで、バランス等も安定しているとは到底言えない状況です。そもそも問題案が枯渇しかけていて、来年以降問題セットを作れるかどうかすらわかりません。ICPC 引退した人が JAG に加入して問題をドシドシ提案してくれると、とても助かります。ご検討のほど、よろしくお願いいたします。（コピペ）*1

jag-icpc.org

また、JAG のコンテスト運営責任者に興味のある方も募集しています。一応まだ投げ出す気はないですが、興味のある方がいたらお手伝いいただく（もしくは自分がお手伝いする）のもいいかなと思っています。

最近は特に、作問能力の高い人、モチベーションの高い人が他のコンテストサイトなどに吸われてしまっていてどうしても JAG の作問能力が落ちていてこまっています。まぁうちが完全無償のボランティアなのに対しちゃんと正当な対価が支払われるような場所もあるのでしかたないね。

*1:https://climpet.hatenablog.com/entry/2022/11/27/230943#%E3%81%8A%E3%82%8F%E3%82%8A%E3%81%AB

もぎちく2021非公式コメンタリ

ICPC

（この記事に書かれた内容は全て個人の見解であり、所属する組織の公式見解ではありません）

問題文、順位、解説等は以下のページで公開されています。 jag-icpc.org

注意：以下には問題のネタバレが含まれます

自分の想定していた難易度順に問題を見ていきます

A: Harvest（AC チーム数：35）

データセットを担当していました。最も簡単な問題ということもあり境界値データとか用意するの忘れていたんですが、ちゃんと WA や TLE が出ていて（かつ全チーム AC していて）良かったです。

B: Parse the Syntax Tree（AC チーム数：34）

びっくり簡単枠です。最近の ICPC 横浜では A とか B とかに見た目やばいけど実は簡単な問題が出る印象があった（個人の見解です）ので B に置きました。
問題文中に書いてある構文に沿って再帰関数で計算してもいいですが、実は . を全て無視して左下から Queue とかを使って適当に計算してもできます（詳しくは解説 pdf を）。

H: include（AC チーム数：34）

SCC 貼るだけ枠です。意図的に（？）入次数 0 の頂点のみを選択してもサンプルが合うようにしていたらしく、そんな感じの提出が何件か来ていた気がします。

G: Pizza delivery（AC チーム数：29）

隣接した 2 つを swap した方が嬉しい条件を見つけるいつものです。データセットを担当していました。もしかしたら {t_i, a_i \le 1{,}000} という制約に戸惑わされた人がいるかもしれないですが、答えを 64bit 整数に収めるための処置でした。データセット作成係としては何も考えずにランダムに作ってもいい感じの入力が作れて嬉しい。

I: (N+1)-legged race（AC チーム数：32）

すでに AC 数と想定難易度順に逆転が起きていますね…。当初 DP 解が発見されておらず、そこそこの考察をしたのち set を使う解法が想定だったんですが、実はもっと単純な DP 解が存在していました。本番で解いたチームもほとんどが DP だったのではないでしょうか。

K: Zombie Land 2（AC チーム数：20）

ん……？ ちょっと幾何の要素が入った普通枠のつもりでした。ある二人が距離 D 以下になる区間さえ求まれば、あとは {O(V^2)} ダイクストラみたいな要領で各人がいつゾンビになるかわかります。誤差の評価にそこまで自信がないので、もし誤差のみが原因で落ちている人がいたらかなり申し訳ないです。
ところで問題文を担当していました。読み比べればわかるんですが、ほぼ過去の JAG 夏合宿の問題 Zombie Land の丸パクリです。まぁ解法全然違うしセーフということで…。 onlinejudge.u-aizu.ac.jp

あと、コンテスト中に既出？が発覚しました。 onlinejudge.u-aizu.ac.jp

C: Permutation Magic（AC チーム数：24）

最小費用流を流す問題でした。おそらく辞書順最小を求めるところが問題になる気はしますが、そこで {O(M^2)} 回最小費用流を流すのが通ってしまったようです。まぁおそらく遅いフローの {O(M^4 \log M)} と速いフローの {O(M^5 \log M)} を区別するのは困難なため……。

J: Isomorphic?（AC チーム数：25）

データセットを担当していました。輪っかにくっついてる木の hash を求めて、そうしてできた 2 つの hash 列が反転、rotate によって一致するか調べる問題でした。前半部分は「根付き木　ハッシュ」とか調べるといくらでも出てきて、後半部分は Z-Algorithm や Rolling-Hash でできます。
YesNo だと簡単に嘘解法が通りそうだったので実は対応関係を復元する問題にするつもりだったのですが、自分の対応が遅れてしまい結局 YesNo のまま出しました。終わってみれば復元を要求しなくて正解だったかもしれません。
代わりにテストケース生成はちょっと頑張って、最低限適当すぎるコードは通らないようにしたつもりです。本番でも結構な提出を落とせていて良かった（ただ一つ問題があって、問題の性質上木のハッシュが衝突しまくり、みたいな嘘は基本的に落とせない）。

D: MFP: Most Fluctuated Player（AC チーム数：22）

最初に出うる得点を座圧しておいて、自分以外のせいで起こった変動を上手く遅延するといい感じになるやつです（最初に出うる得点を座圧しておいて、自分以外のせいで起こった変動を上手く遅延するといい感じになるやつとは？）。

F: qarentheziz zepuence（AC チーム数：4）

原案と問題文を担当しました。どうやらセグ木とか平方分割に変なものを乗せるのが人よりちょっと得意らしい。
当初想定解が {O(N \log N + Q \sqrt N \log N)} で {N, Q \le 10^5} だったのですが、{\Theta(NQ)} を確実に落とすのが難しく、かつ {O(N + Q \sqrt N)} になったので少し制約が大きくなりました（すまん！）。それでも 3 並列だし 10 チームくらい通すと思っていたので、ちょっと意外ではありました。

準備をしながら、この辺の問題に似てるな思いを馳せていました。 atcoder.jp onlinejudge.u-aizu.ac.jp

自分のジャッジ解を置いておきます（もしどこかバグっていても責任を負いません） jag_regional_2021_F_riantkb.cpp · GitHub

E: Underground's SUNDAY（AC チーム数：4）

問題文を担当しました。原案では日食みたいな問題設定だったんですが、空に浮いたあの多角形はなんだ……？ となって今回の問題文になりました。ちょっとだけ Undertale をイメージしています。
ところで、原案では凸多角形だったり円の中心が通る直線と平行な辺が存在しなかったりしました。どうしてこんなことに。準備段階でも y 軸に平行な辺とかではちゃめちゃバグらせたので、5 時間の間で冷静にデバッグができるかゲーかなと思っています。

自分のジャッジ解を置いておきます（もしどこかバグっていても責任を負いません） jag_regional_2021_E_riantkb.cpp · GitHub

ところで

JAG ではメンバーを募集しています。 やる気がある人やボス問を作れる人や問題準備を手伝ってくれる人やテスターをしてくれる人ややる気以外何もない人などの加入を心よりお待ちしています。 jag-icpc.org

ととりにゃあってなんだ……？

adventar.org

ととりにゃあアドベントカレンダーってなんだ……？

ととりにゃあってなんだ……？

最近巷で話題のととりにゃあとは何なのか、調べてみました！

調べてみたところ、以下の記述にヒットしました！

トトリのアトリエ、やったことがなかったんだけど響きがいいなと思ったのでトトリを貰いました。 にゃあはフィーリングです。「にゃーん」ってやつです。キッショ

20日目(12月21日なので) - ととりがにゃあをする

なるほど〜〜〜


さらに調べてみたところ、なんと㊙️情報をゲットすることができました！

twitter.com

なるほど〜〜〜2

いかがでしたか？

rian_tkb の tkb ってなんだ……？

rian_tkb の tkb って、いったいなんなんだ……

ICPC 2021 国内予選　JSON色付け部門　参加記

ICPC


ICPC 2021 国内予選 JSON色付け 部門に参加しました。
結果は以下です。

github.com

チームメンバー

なお、ICPC 2021 国内予選 JSON色付け 部門は本物の ICPC 国内予選 とは異なり、チーム外の人との相談、問題の開示、闇討ちなどなんでもありなので、チーム外の人に Pull Request を要求する、なども積極的に活用していきます。

A 問題：JSON 生成

JSON色付け 部門だからと言って JSON を生成しなくていいわけではないので JSON を生成します。

国内予選開始の約 22 時間前 に JAG のページにチーム情報を書き込むページが生成され、そこで A 問題が公開されました。 主に以下の手順で、JSON を生成していきます。

  1. JAG のページを見にいきチーム情報を抽出する
  2. チーム情報の各ユーザーについて、AtCoder のユーザーページを見にいきレート情報を抽出する
  3. JSON にまとめて出力する

この辺は Python で行い、ページを見に行って情報を抽出する部分は pandas.read_html と BeautifulSoup のうち楽な方を適当に選んで使いました。
あとは毎回更新のたびに AtCoder に全チームの全ユーザーの分のクエリを投げるのはやばいので pickle を使って response をキャッシュしたり、これ を参考にチームレートを算出したりしました。
その辺がおおよそ以下のコードで行われています。

github.com

こうして得られた JSON を見やすいように静的ページにしたのが以下です（厳密にはそうではなく JSON に含んでいない情報も入っている）。

B 問題：JSON色付け

国内予選開始の約 6 時間前 に国内予選の観戦者向け順位表が公開され、そこで B 問題が公開されました。

当初は A 問題を解いた時点で撤退するつもりだったのですが、解きたくなってきてしまったためさっと取り掛かります。
去年のアジア地区のときに TumoiYorozu さんが同じような userscript を作っていたので、そこからコードをパクリ、適宜今回の順位表のフォーマットに合わせることで無事 AC。 （コードの細かい内容はほぼ理解していない……）

C 問題：通過判定

ここにきてようやく競技プログラミングっぽい問題が登場しますが、見るからにめんどくさいので他の人に押し付けます。

（参考：2021 アジア地区大会 選抜ルールより引用）

手順1 参加チームについて成績順に以下のルールを適用する．いま，該当チームを A とする．

  1. その時点での選抜チーム数が 10 に満たない場合
    Aは横浜大会の参加チームとして選抜される．
  2. その時点での選抜チーム数が 20 に満たない場合
    Aと同じ大学等の所属でその時点で選抜されたチームの数が 3 に満たなければ，Aは横浜大会の参加チームとして選抜される．
  3. その時点での選抜チーム数が 30 に満たない場合
    Aと同じ大学等の所属でその時点で選抜されたチームの数が 2 に満たなければ，Aは横浜大会の参加チームとして選抜される．
  4. その時点での選抜チーム数が 39 に満たない場合
    Aと同じ大学等の所属でその時点で選抜されたチームがなければ，Aは横浜大会の参加チームとして選抜される．

手順2

  1. 手順1 終了後，ホスト大学のチームで選抜されていない最上位の1チームは，横浜大会実行委員会 が認めた場合，横浜大会の参加チームとして選抜される．

その後、見事 TumoiYorozu さんにやってもらうことに成功し、通過判定についても AC を得ることができました（1 WA した気もするけど）。

国内予選終了後にちょっと通過判定の表示方法を変えたりして、ICPC 2021 国内予選 JSON色付け 部門は終了しました。

まとめ

初心者でもデータをクロールしてきて userscript で順位表に色付けする、くらいならまぁできる。

こういうのはたまにやるとたのしい。

JAG 模擬国内予選 2021　参加記

ICPC

模擬国内、正式名称なんだろう

jag-icpc.org

JAG の模擬国内予選 2021 に参加しました。
具体的には、C と E の原案を提供したり、A から F までの解法や想定誤解法を書いたり、問題文に少しケチをつけたりしました。

C 問題

適当な無考察実装枠を置いておいたら採用されていた。 O(HW2^W) の bitDP あたりを想定にしてたけど普通にメモ化しない DFS も速くて間に合うらしく実装したらたしかに速かった。

E 問題

別の問題（これは嘘が見つかり爆発した）の部分問題として出てきた問題を切り出して置いておいたら採用されていた。C 問題くらいの難易度だと思っていて実際最初は C 問題に置かれていた気がするが、いつの間にか E に移動していた。
まぁ dp[i][j] = [0, i), [j, N) がそれぞれ両端でソートされている状態でのコストの最小 みたいな方針（これは嘘）に行ってしまうとなかなか戻ってこれなさそうなのもあるしこの AC 数は納得？

自分の書いた原案ページを見たら解法の欄に以下しか書いてなかった、おいおい

解法

  • コスト k+1 払いある要素を右または左に k だけ動かす、と考えられる
  • 動かす要素数を最小にすると嬉しい
  • よって、p の転倒数 + (N - (p の LIS の長さ)) となる

その他の問題

G, H は気が向いたときに実装しようと思っていたら気が向く前に本番当日になってしまった

いつもの

ところで JAG では人材を募集しています。サイコロを転がす問題を作るのが好きな人やサイコロを転がす問題を作るのが好きな人ではない人などの入会をお待ちしています。

jag-icpc.org