うにゅーん、って感じだ

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

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

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

問題文、順位、解説等は以下のページで公開されています。 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 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 参加記

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

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

yukicoder No. 1308 ジャンプビーコン 解説(tester 解)

問題概要

問題ページを参照してください

yukicoder.me

この問題は Advent Calendar Contest 2020 の 5 日めの問題で、自分は tester をしました。 adventar.org

yukicoder.me

tester 解

まず、以下のような DP を考えます

DP[i][j]  := x_i まで訪問して今ビーコンが頂点 j にあるときのコストの最小値

このとき、DP の更新式は以下のようになります。

DP[i][j] = min_k( DP[i-1][k] + cost )
  cost := dist[x[i-1]][x[i]]  ( j == k のとき )
  cost := min( dist[x[i-1]][j], C + dist[k][j] ) + dist[j][x[i]]  ( j != k のとき )

これをそのまま実装すると {O(N^{2} Q)} になるため、高速化する必要があります(ここまでは yukicoder の方の解説に書いてあることと同様)。

上の DP の遷移をよく見ると、以下の値がわかっていれば遷移が減ることがわかります。

D[i][j]  := x_i まで訪問して、今ビーコンがどこにあっても良くて自分が頂点 j にいるときのコストの最小値

実際の遷移は以下のようになります。

DP[i][j] = min( DP[i-1][j] + dist[x[i-1]][x[i]], D[i-1][j] + dist[j][x[i]] )

ここで、D[i][j] は以下のように求められます。

D[i][j]  = min( min_k( DP[i][k] ) + dist[x[i]][j] ), min_k( DP[i][k] + C + dist[k][j] ) )

まだ {O(N^{2} Q)} のままなので意味がありません。

ここで D[i][j] に思いを馳せると、これは例えば以下のような問題と同等な最短路問題のような形をしていることがわかります。

あなたは N 頂点 M 辺のグラフで表される町にいます。

各頂点ではメダルが売られており、頂点 j で売られているメダルの値段は P_j です。
また、各辺には通行料が定められており、辺 j の通行料は C_j です。

各頂点 1, ... , N について、その頂点からスタートしていずれかの頂点でメダルを買う、という行動にかかる金額の最小値を求めてください。

この問題はどうやって解けばよいでしょうか。結論から言ってしまうと、これは全頂点を始点とする Dijkstra をすることで {O(M \log M)} で求めることができます(超頂点を用意し、その頂点から各頂点 j に対し長さ P_j の辺を張る、というように考えてもよいです)。

よって、D[i][j] も全ての j に対し {O(\log N)} で求めることができ、全体で {O(NQ \log N)} で求めることができました。

なお、解説で触れられている「遠回りをしてビーコンを設置することはない」という事実を用いて、最短路を x[i] に近づく方向にのみ更新することで {O(NQ)} にすることも可能です(想定解は {O(NQ)} でかつそもそもの定数倍がそこそこ重いため、C++ 以外の言語では {O(NQ \log N)} だと通すのは難しいと思います)(tester したときは {N, Q \le 5{,}000}, TL: 2 sec だったため、C++ でも {O(NQ \log N)} は通らなかった)。

ソースコードは以下です

{O(NQ \log N)}

yukicoder.me

{O(NQ)}

yukicoder.me

まとめ

全頂点を始点とする Dijkstra、よく考えるとそれはそうなんだけど始点を増やしても計算量が変わらないのは少し非直感的?