潜入(ZONeエナジー プログラミングコンテスト “HELLO SPACE” E) 別解

f:id:kort0n:20210505183927p:plain

最も思いつきやすい解法は、O(RC)頂点 O(R^2C)辺のグラフ上でのDijkstra法を実行するものだが、これはO(R^2C)\log(RC) timeで、実行時間制限に間に合わせるのは非常に難しい。

想定解は上手くグラフを作って辺の数をO(RC)本へと減らしたグラフ上でDijkstra法を実行するものだが、ここではグラフの作成は工夫せず、最短路の計算を工夫することにする。

(1, 1) から (R, C)までの経路長を ans とおく。

ansとして考えられる最大値に等しい数のvectorを用意し、それらにDijkstra法におけるheapの役割を担わせることにより、Dijkstra法と同様の動的計画法を行うことが出来る。ただし、本問題ではコストが 0 の辺が存在することに注意が必要である。

この手法はO(R^2C+ans) timeである。ここで、ans = O(RB_{\max} + CA_{\max}) であるから、この解法は実行時間制限に十分間に合う。

 

atcoder.jp

 

関連アルゴリズム:Dial's algorithm

dic.kimiyuki.netこのアルゴリズムを用いることも出来る。本記事の手法もこのアルゴリズムも、辺のコストが大きくない点を活用している。

ICPC 2020 Asia Yokohama Regional Contest 参加記

コンテストで非常に冷えて、書き手も読み手も得しない記事しか書けなさそうだったので書くか迷ったんですが、ICPC引退という節目なので書くことにします 後ろ向きな内容の記事が苦手な人はブラウザバック推奨

メンバーはいつものQWE_QWE

 

コンテスト前々日～

 

 

 

朝9時からの殺人的スケジュールコンテストに対抗するべく、朝バチャで慣らす

受付の時間になったので受付のZoomミーティングに入る

チームでDiscordで通話し、雑談をしていると

Rubikun「こるとんさん、Zoomのマイク切った方が良くないですか？」

 

え？

 

あっ...

 

 

すみませんでした...

 

 

 

クソガキばかりなので「あたまさん」でTLが大いに沸く

f:id:kort0n:20210318150440p:plain

あたまさんでゲラゲラ笑っていると、弊チームも呼ばれる

「くえくえさん」

TLでクソバカにされてキレた

 

Practiceで時間を持て余していると、宅配便が来る

折角なのでネタツイをする

 

 

そこそこふぁぼが付くのをニヤニヤしながら眺めていると

 

 

 

 

すみませんでした...

 

午後8時頃に眠気が来る これで翌日5時や6時に起きて、CF Div.2 あたりのバチャをすればアップも済んで完璧 おやすみ！

 

目が覚める うーん、窓の外が暗いな？

時計を見ると午後11時だった

完全にやらかしたことに気付く

 

 

その後寝ようとして布団でゴロゴロしていると、3時頃にようやく寝付けた 8時頃にアラームで起きるも目覚めが最悪 非常にまずい...

 

 

コンテスト

 

初動は

Rubikun:A

kort0n:B

risujiroh:後ろ

 

コンテスト開始してBを読むと分かったので実装するとFAで通る(0:07)

 

risujirohに聞くと、「K得意なんじゃない？」と言われたので考えることにする この辺でAも通る(0:14)

 

暫くKを考えたところで、問題内容の伝達ミスに気付く 仕方が無いので一旦放置することにする Jをrisujirohがやっており、Gが通り始めていたのでGをやることにする RubikunはIを始める 暫くしてこの3問が通る (J(0:52), G(0:53), I(1:06))

 

一旦残っている中でACが出ている問題をチーム内で概要共有することにする risujirohがE, kort0nがK, RubikunがCに着手することになる 暫くしてEが通る(1:24)

Kのまともな解法は分からないが、未証明エスパーを実装するとサンプルが合ったので投げてみることにすると、 TIME LIMIT が返ってくる 自明に O\left(N^3\right) 解法だった 完全に頭が死んでいる...

 

結局正しいのかよく分からないので、手元で小さいケースについてストレステストを回すと落ちない 多分答えは正しくて、これを高速化すれば良いんだなという話になる これが完全に地獄の始まり...  恐らくこのエスパー解法は単に落ちづらいだけの嘘解法で、周りを巻き込んでこれに拘泥したせいで、チームとしてKの進捗が長時間ストップしてしまった

 

Rubikunに「Cは右手法とかやればかなり短い行数で出来るはずで、5行以下くらいの答えは全探索出来る 右手法は何手で出来そうか？」と聞かれる 暫く考えると6行の右手法を作れたので、任せることにする

 

暫くしてRubikunが実装を終えたらしく、サンプルを試していた途中(多分？)で突然叫び始める

「やば！！！これFORWARDのスペル違うじゃん！！！」

 

f:id:kort0n:20210318153204p:plain

気付いてくれてありがとう...

Cがちゃんとノーペナで通る (1:50)
(後で知ったけどこれ右手法5行で書けたみたいですね 結局短い答えから全探索するだけで通る問題だったのか...)

 

Hがそこそこ通っているのでrisujirohと色々喋ると解法が生えたらしく、任せる 暫くすると通る(2:36)

 

残りがD, F, Kの3問になる Dは明らかにヤバイので放置するとして、Fも一応内容を把握する 暫くすると、

 

1.全点対間距離を O\left(N^2\right) time で計算する

2.全点対間距離を O\left(N^3\right) time で計算する

3.各クエリの答えを O\left(1\right) time で計算する

 

という解法が生える N \leq 2000 だが、 ボトルネックの2. の部分はシンプルな処理をするループを回すだけで、手元で最大ケースを実行すると 4sec で終わることが分かる

TIME LIMITの心配は不要だと確信して、実装して提出する ジャッジは遅いが着実に進んでいるようなので、安心して「Kどうしようかな～」等と考えていると

 

F WRONG-ANSWER

 

ストレステストを掛けるが、バグが発生するケースがある程度大きいテストケースしか出てこない Rubikunとデバッグをしようとするが、完全に不可能

 

risujirohはKを進めていたがそちらも通らず、そのままコンテストが終わる

 

コンテスト後

コンテスト中は順位表全体を見渡す余裕は無かったので、Yes/No タイムになって初めてeat-iceの奇行を知ってウケる

 

凍結後1問も通していないので、当然だが次々と抜かされる 最終順位は8位と酷い順位に...

 

f:id:kort0n:20210318165337p:plain

コンテスト後はGatherTownで懇親会をする

初めは広い部屋でどうすれば良いか戸惑っていたが、やがてピクトセンスグループを発見して、乱入する

 

クソガキの群れなので小学生レベルの下品な落書きで大いに盛り上がっていると、突如keymoonが

「てかこれ通話はGatherTownでしてるから会話周りに丸聞こえじゃん」

と言い始める GatherTownの画面を見る 当然周囲に丸聞こえだった 何ならGoogleブースの隣で小学生レベルの会話をしていた

 

 最終的に落書きが何故かkyuridenamidaさんのアイコンに採用される

f:id:kort0n:20210318165743p:plain

 

その後GatherTownが閉じられるまで適当に雑談し、撤退 ボードゲームの二次会を経て就寝しました

後書き

今年はチーム練を頻繁に行っていて、互いの得意分野の把握や立ち回りの最適化もかなり行えており、順当に行けば3位以内はまず間違いないし、2位も普通に取れるチームだと思っていたので、今回の結果は正直非常に悔いの残る結果でした

前日に十分寝られなかったことや問題の伝達ミスが発生したことは不運と言えば不運ですが、強い競技者はちゃんと生活リズムをコンテストに合わせる能力も高いし、そもそもそういう要素を抜きにしても本番中に思考停止で嘘解法を信じようとしたり、最後に難易度予測を見誤って問題の担当ジャンルをいつもと変えてゴリ押そうとした結果ハマッたりした時点で、到底勝てる状態ではなかったなと思います

最後のコンテストはオンライン開催であったという点においても、コンテストの内容としても不完全燃焼という感じではありますが、それでも自分が競プロ沼に深くハマるきっかけになったコンテンツであることは間違い無いし、良いチームメイトに恵まれて楽しくチーム練が出来たことも良かったと思います

幸いチームは解散しないようなので、今後も何かチームコンテストで勝負する機会があったら他所のチームの方は是非宜しくお願いします

来年以降出場される皆さんは是非頑張ってください

ICPC2020 模擬地区予選 参加記

メンバーはいつものQWE_QWE(risujiroh+Rubikun+kort0n)

risujirohいね～とか言ってたが開始直前に通話に入ってきた セーフ

 

コンテスト

 

よく分からんけど多分例年のアジア地区予選通り最初の方に簡単な問題があるんだろうということで、A:Rubikun B:kort0n C:risujirohで読み始める

読むと、右に区間を伸ばしながら中央値を取得し続けたい気分になる 「priority_queueのlogを乗せれば出来るな～」と言いつつもやや大きい N \leq 3000 が気になる

結局「う～ん、まあ通るやろW」と言って実装する AのAC(0:08)に少し遅れてAC(0:09)

 

Cは瞬殺問題では無いらしい 去年は最初の2問が難易度順だったのでそういうことだろうと判断する RubikunがDを読んでいたのでEを読むといつものやつだったのでAC(0:21) FAだった 開いた問題運が良かった

 

特に順位表も動きが無いので、周りの2人が手を着けていない問題を適当に漁っていると、Hが出来そうだと思ったのでHに取り掛かる 実装を始めて、序盤にこの問題に手を着けたことを後悔する アジア地区予選2019Iから何も学んでいないことがバレた

泣き叫びながら実装しているとFが通される(0:46) その後Hの実装が終わったのでsubmitするもWAで終わる

ストレステストを始める この間にIが通される(1:08) Hも何とかバグが見つかって通る(1:41) FAだけど、これは手を着ける順番を間違えた結果のFAという感じがするので何とも...

 

Hが終わった時点でCとGは担当が決まっていたようなので、残りのDJKを眺める 全部無理やろこんなんと叫んでいると、C(1:43)とG(1:52)が通る

 

暫く考えていると、Jの解法が生えた気になって、雑にrisujirohに伝えて実装してもらうことにする 更に、何とRubikunがDの設定そのままの問題(制約だけ少し違う)をCSAで発見し、コードの読解を始める

 

そういう訳で手を着ける問題がKしか無い状態になったので取り組む 暫く考えると、 \sqrt{A^2 + B^2} \geq 2のときは上手くいく解法が生える  \sqrt{A^2 + B^2} = \sqrt{2}のときも上手くいってくんねーかな～とか言いながら実装してsubmitすると無事WAが返ってくる

 

この辺で、Jを実装していたrisujirohから「こういう場合はどうすんの？」と詰められまくる しどろもどろになりながら受け答えしていると、解法が破綻して無事戦犯となる

「ご゛め゛ん゛な゛さ゛い゛」と謝っているとrisujirohが無事Jの解法を出した ありがとう

Kに戻って、 \sqrt{A^2 + B^2} = \sqrt{2} のときに生成される \left(s_i, t_i\right)を眺めてみると、めちゃくちゃ性質が良いことが分かったので、場合分けで解けそうだと分かる この辺でDが通る(3:41) 暫くしてKも通る(4:06)

 

最後にRubikunと2人でJの応援をする サンプルが合ったので提出するが、WAが出る 3人掛かりでデバッグしたりストレステストしたりした結果無事バグが見つかり、提出するとACする(4:35)

 

結果

f:id:kort0n:20210307194909p:plain

全完内最下位で、全体2位

何と、この結果だとWFには進めません！(は？)

AtCoder 赤になりました

f:id:kort0n:20210110055211p:plain

f:id:kort0n:20210110055222p:plain

f:id:kort0n:20210110055229p:plain

f:id:kort0n:20210110055238p:plain

 

ARC111で赤になりました

「精進は大事！皆も精進しよう😭😭😭」みたいな記事は需要が無いと思うので、お世話になったツール等について書こうと思います

 

精進サポート系

AtCoder Problems

これ使ったこと無い人、いる？

知らずに水色以上になった人がいたら教えてください

 

AtCoder Rivals

他のユーザーの精進状況を監視出来る

対抗心の強い人におすすめ

人生が忙しい時に見ると危険

 

clist

コンテスト情報や諸々の順位等の情報収集に便利

 

AOJ-ICPC

AOJ-ICPCは実装ゲーのクソ問ばかりという風潮があるが、そうでもない 面白い問題もかなりある

青帯以下は定型文の反復トレーニングの場

黄帯は典型テクを身に着ける場(と実装力を身に着ける修業の場)

橙帯は高度典型テクを身に着ける場

として良いと思う

ここを埋め始めてから(AtCoderのレベルで)実装力負けすることは殆ど無くなった気がする 

 

Contest Mania

CF合同バチャで誰もやってない回を探すのに便利 というかこれが無いとやってられない

 

gym

コドフォはやっているがコドフォのgymは触っていない人が多い気がする

チーム戦向けのセットが山ほどある

 

コンテスト用便利ツール

online-judge-tools

特におすすめ！！！全人類導入しろ！！！

サンプルの一括テスト・ストレステスト・ターミナルからのsubmit等色々出来る

online-judge-template-generatorと組み合わせると、コンテストディレクトリの作成・サンプルのダウンロード等も行ってくれる

 

ac-predictor

コンテスト中に暫定パフォーマンスとレート変動値を表示してくれる

立ち回りの参考に出来るが、却ってプレッシャーを感じる人もいそう 自分の性格を鑑みてどうぞ

 

配列のサイズと型を入力すると何MBか教えてくれるうし

MLの計算をするのが面倒な人に

 

ライブラリ

ac-library

最近始めた人には割と知られていないようなので載せる

競プロが強い上にパソコンにも強い人がガチで作ったライブラリ これ使ってダメならもう定数倍改善は諦めようという気になる

ei1333

beet_aizu

kactl

ICPC用にコンパクトにまとめたライブラリらしいが、LinkCutTreeとかDirected MSTとか普通に入ってる

 

情報収集

ARMERIA

一押しの解説ブログ 質量丁寧さどれもトップクラスだと思う

 

kmjp's blog

解説記事の量圧倒的全一

 

noshi91のメモ

高度なネタについて時々書かれている

コンテストへの即効性を期待して読むものではないかも

 

maspyのHP

形式的冪級数導入の丁寧さ全一

普通の問題の解説記事でも圧倒的な数学の知識量に基づいた新しい視点が紹介されていることがあって、すごい

 

Library Checker

ここを埋めるのは上級者向けコンテンツだが、どういうことがどの程度の計算量で行えるのか眺めるだけでも為になる

最大限活用したい人は、頑張ってください...

 

 

あと思い出したら適当に書き足すかも

 

 

チームコンテストを、やろう

自分の場合、チームコンテストの頻度を高めてから明らかに実力が伸びたと思ってます

自分とは得意分野が異なる人と組むと様々な知見を教えてもらえて非常にお得です

皆もチームコンテストを、やろう

(効果には個人差があると思います)

 

ICPC2020 国内予選参加記

チームメイトは

risujiroh(去年に引き続き)

Rubikun(今年から)

 

ICPCに参加する為に...

f:id:kort0n:20201107010753p:plain

え？

弊専攻は毎週金曜日に輪講があり、何と自分の担当日が国内予選当日になっていた

当然これでは参加出来ない

まあなんか個人間で適当にswap交渉さえ出来れば日程変えてもらえるだろう

 

...と甘く考えていたのだが、日程変更の許可が降りない 国内予選エントリー部門敗退です。有難うございました...

 

結局あの手この手こねくり回したら何とか日程swapが通った 良かった(同期のICPCに参加しない競技プログラマに変わってもらった ありがとう...)

 

コンテスト前日

 ？笑

 

ノリと勢いで†ASCII Expression†まで通してしまった　これで構文解析も万全だな！

 

コンテスト当日

早めの1時間前集合 色々話しているとコンテスト開始時刻になる

...が、ログイン出来ない

これうちだけなのか？ICPCは初動が大切なのに...

かなり空気がピリピリしてくる

 

冷静になって緊急連絡先に電話をすると話し中になっているので、少なくともうちだけではないと考えて落ち着く

暫くするとログイン出来るようになる

「『不具合があった為開始しませんでした。○○分からコンテストを開始します。』とかアナウンスあるんだろうね～」とか言いながら適当にリロードしていると突然始まってビビる

 

このチームはずっと初動をレート順で

A:Rubikun

B:risujiroh

C:kort0n

にしていたが、模擬国内等でRubikunの低難易度問題の方針の選び方が上手いという話になり、AとBの担当をswapすることになっていた。

 

開始して即Cを読む 多分遅いけどまあ待てそうだなという解法を考えて実装する

サンプルは通ったのでテストケースをダウンロードして実行する

 

...流石に遅くないか？

 

とても待てないレベルだったので考え直す こういうことをしているうちにABが通っていて、他の2人はDEを考え始めていた

 

暫く考えるがまともな解法が全く思いつかない

(初めから分かっていたことではあるが)約数列挙を高速に行えばまあ待てる程度の実行時間で終わるコードは書けるので、高速素因数分解ライブラリを持っているrisujirohに泣きついて担当を変わってもらう

その間にRubikunがEの解法を出し、あまり実装に自信が無いので実装してほしいと言われる 実装を始める

暫くしてCが通る この時点で完全に冷えていて、空気がとても重かった 見ると余計に焦りそうで順位表を見る気にもならなかった

 

Eを実装しているうちにRubikunがDの解法を出したようで、risujirohとRubikunで適当に分担してDの実装を始める

Eのサンプルが合い、提出すると通る その数分後Dもサンプルが合ったようで、通る

 

この時点でムードがやや明るくなったが、序盤のペナが重いのとFを通しているチームがそこそこあるということで、まだ油断は出来ないという空気に(結果的にはこの時点で通過が確定していたが...)

 

流石にあと1問通せば通過確定なのでGHは放置して3人掛かりでFに取り組むという話になっていた(これは最後F担当とG担当に分かれてしまった模擬国内の反省が生かせていた)

 

暫くするとrisujirohがFのかなり見通しの良い図示を行う それを見ていると解法が生えたので、実装を始める

サンプルが合う 1度提出するとWAだったが、小さなバグに気付いて修正して提出すると通る

この時点で流石に通過を確信して、かなり気楽になった

その後はGHをやる

 

risujiroh「H、未証明エスパーだけどこんな感じで出来そう！」

kort0n, Rubikun「うーん、GO！W」

 

その間にGをとりあえず線型計画問題に緩和して立式してみる 双対問題を取ろうとしたが、何か凄いことになって天を仰ぐ

いやそもそもこういうのはrisujiroh担当なんだよね あいつ今何やってんの？

→Hをやってました ごめん...

 

暫くするとrisujirohが実装を終えるが、サンプル4が合わない

図示すると、最初のエスパーが明らかにヤバいケースが見つかる

 

kort0n「じゃあ、新しいこういう未証明エスパー解法！」

 

と適当なことを喋って実装してもらう

実行するとサンプルは合うが、何故かバカみたいに遅いらしい

怪しい枝刈り等をしつつテストデータを実行してみるがWAで、そのままコンテスト終了

 

f:id:kort0n:20201107013903p:plain

3位で国内予選通過！

Cで詰まったときは完全に心が終わっていたが、結果チームメイトに助けられて通過出来たので良かった

「去年は4位で今年は3位だから順位1つ上がったね～」等と言っていたが、自分の上にいるチームのメンバーを考えると実は去年と本質的に殆ど変わっていないことに気付いて泣く

 

ちなみにGの立式を後でrisujirohに見せたら「これ何もかも間違ってるよ」と言われる 計算用紙を捨てる さようなら

 

 

横浜でお会いする皆さん 宜しくお願いします

ACPC2020 参加記

会津行くぜ！

 ACPCは毎年懇親会が大盛り上がりということで非常に楽しみ

どうしてこんなことに...

 正直そんな気はしてたよ

HUPCと同じノリで全日いつものチームで

Day1(農工大セット)

 例の如く

A:Rubikun

B:risujiroh

C:kort0n

でスタートして、後はよしなにやる感じになる。

Cを読む。

「各頂点ペア(i, j)について、街iから街jへ移動するときの必要なコストの最小値を出力？各ペアについて道やテレポーターの選び方を変えろということ？でもそれテレポーター1つで良くない？」

サンプルも見つつ読み直す。ようやく「強連結にする為の最小コスト」を聞かれているのだと分かる。

Aが即通る。Bも少し面倒な方法を取ってしまったようだが、まあそれ程掛からずに通る。

その後実装を始める。何かサンプルが合わない。読み返すと、vector<edge> e(M)を宣言した後、読み込んだ辺をpush_backして空の辺がM個生まれていた。これやらかすの100回目くらい。

 こういうのどうやったらやらかさないように出来るんですかね...

修正してCを通す。この時点でRubikunがD, kort0nがE, risujirohがFを解けていたので、そのまま各自取り組むことに。

Dは一回同じ値の扱いを間違えてWAが出たようだが、すぐに修正して通す。

Eを書き始めると、問題の前半パートまでしか解けていなかったことに気付く。周りに介護を求めつつ後半パートも解いて提出する。REが出る。NがクソデカいときのNCKを前計算テーブルを使って求めようとしていたせいだった。これやらかすの1000回目くらい。愚直に計算するようにする。TLEする。バカなので毎回逆元計算にO(log mod)掛けていた。その後Fも通る前になんかREが出てた。合計5ペナで順位が完全に壊れる。

D, Eの実装中にrisujirohがGを解いていたらしく、そのまま実装を始める。

その間にHを考え始める。最初はルール①における最適解とルール②の最適解のうち良い方を出すものだと勘違いしており、「ルール②を選ぶ意味が無くないか？」とか言ってた。clarを見て完全理解する。

そういうことをしているうちに、Gの実装が終わる。探索範囲のミスでWAが出るが、修正して通る。

 

 

...ところでこの弊チームのG、区間の場所を確定した後左右吸い込む点の距離を二分探索で決定してるんですが、これケースによっては余分に1個吸い込んでしまうのではという気がしている...でもhackケースを作ろうとしても、他の区間で上手くいってしまってhack出来ない これ大丈夫なのかな

 

 

Hは「Nが小さいときは解けるね～」と言っているうちに無限時間経過して、コンテストが終わる少し前にNが大きいときの解法が生えたが、当然間に合うはずもなく...

 

f:id:kort0n:20200922023051p:plain

うーん...

結果は8位だった。個人勢にも結構負けていて、まあまあ冷えている...

 

f:id:kort0n:20200922023216p:plain

このパチモンチーム許せねぇよ...

 
問題の感想

B:これ普通に難しくない？XXORの難しい方に似てる

C:これも難しくない？うっかり嘘貪欲やりそうになる

D:B, Cより実家感がある

E:AtCoderの500点が2問飛んできた感じだ

F:

お ま た せ

い つ も の

ハ コ の 魔 女

G:添字あたまこわれそう

H:何でこれすぐに出来なかったんだろうね 本当に何で？

 

Day2(会津セット)

問題の感想

A, Bが本当に爆速で通っていた。そのままCを通す。

Fを読むと解けたので通す。

Eが得意そうと言われたので読むと本当に得意なやつだった。通す。

その後は暫く止まるが、Gの解法が生える。区間に辺を生やす実装が出来ないのでrisujirohに頼み込んで実装してもらう。

その間にKを読むと解法が生える。bitsetで色々やる実装はあまり得意ではないので、Gの実装を終えたrisujirohに頼み込んで実装してもらう。

残りがDIJの3問になる。Dは「こんなん無理やろ」という気にしかならない。Iもある意味「こんなん無理やろ」という気にしかならない。Jは結構通されているがよく分からないな～と言っていると時間が結構経ってる。

暫くしてRubikunがJの解法を生やす。聞くがよく分からなかったので、risujirohに頼み込んで実装してもらう。

しかし全く答えが合わない。残りの2問が諦めモードなので、3人がかりで必死にデバッグをすると、バグが見つかる。辺を削除する際に、辺を追加する際の各操作を逆順に逆操作することにしていたが、このときに「この辺が存在するならば」というif文の条件式も反転させて「この辺が存在しないならば」としてしまっていた。初めて見るタイプのバグだ... 何にせよJが通る。

この時点で残りが50分程度で、DもIもsubmitさえされていなかった。「DもIも不可能にしか見えないし、もう無理じゃね？」という空気になる。

 と言いつつ何もしない訳にもいかないので、Dで雑に愚直解を書いて実験していると、「実はsum(B)ってせいぜいPの数倍程度しか見なくて良いのでは？」という感じがしてくる。とりあえずそのエスパーを認めて考えていると、Aの種類数に着目することで更に計算量が落ちて、TLに間に合いそうだということが分かる。この時点で残り10分程度だった。

必死に実装を始める。途中の算数パートを周りに投げつつなんとか実装して提出するとACが出る。

 ...が、5分間に合わなかった。途中半ば諦めてダラダラする時間が無ければ間に合っていたかもしれない...優勝はしたが悔いの残る結果に

f:id:kort0n:20200922025611p:plain

(+0)
問題の感想

C:これ面白いけど乱択通っちゃうのちょっと残念感あるね M<=2Nくらいにすれば通らないように出来ないのかな

D:ビックリ性質と計算量削減から作られるビックリ解法 何だこれ...

なんかチーム作問中にどんどん計算量が落ちたらしいね 凄い

E:こういうの好きです

F:そろそろここも実家になりつつある

G:区間に辺張るやつ書くの、滅茶苦茶大変じゃない？

ところで解説スライドの改題あまりよく分かってない気がする

I:こんなん無理だろ

J:大変ねっとりしております...

K:これマジで面白い つぶあんすげーよ

 

Day3(北大セット)

Aを読んでいるRubikunが「は？ヤバくないか？」と連呼している。ヤバそうなのでBとCを先に通す。会津セットのノリで問題をmod 3で読み始めて、risujirohがEを、kort0nがFを読み始める。

RubikunはどうやらAの誤読に気付いたらしく、その後すぐに通す。

Rubikun「これ今どれが解かれてるんですか？」

kort0n「Eはrisujirohが解いた Fは今解けそう Dは多分誰も読んでない」

Rubikun「Dを誰も読んでない！？！？！？」

Rubikun「難易度順なのに何で前のやつ誰も読んでないんすか」

kort0n・risujiroh「ごもっともでございます」

と言いつつrisujirohがEの実装を始めて通す。

その後Fを実装する。途中でcombinationが前計算テーブルの結果を使えず、愚直に計算しないといけないことに気付く。二日前の反省が生きている。えらい。submitするとWAが出る。バカがよ。

読み直すと、遷移計算が間違っていたことに気付く。修正すると通る。

Dが解けていなかったようなので、読む。

kort0n「これN頂点NM辺くらいのグラフを作ってSCCしたグラフがパスグラフになってれば良いってことだよね。パスグラフ判定だから各頂点の入次数と出次数とか見とけば良いのかな。じゃあ実装頼んだ。」

と言って実装してもらう。ACする。

 

 

 

 

 

 

 

 

...これは嘘解法です。正しくは「頂点数が元のグラフと同じであるパスグラフを部分グラフに含むかどうかの判定」をしないといけない

後でhackケースが作れた。本当にすみませんでした。

 

 

 

 

その後risujirohとRubikunがHを始める。その間にやや苦労しつつGを通す。

ここから3人がかりでの最強AIとのバトルが始まる。

とりあえず実験コードを書いて、各(N, K, H)についての勝敗判定を書き出してみる。規則性が全く見出せません本当に有難うございました。

 

...全く見えないというのは少し嘘で、H >= KのときH += (K-1) で答えは不変とか、その他諸々の細かい周期性のようなものは見当たる。しかし、あまりに多すぎてどれに着目すべきか逆に混乱し始める。

結局判定問題すら解けないままコンテスト時間が終了する。

 

f:id:kort0n:20200922031612p:plain

2分差で負け、何？

 

問題の感想

 

 C:はい、実家

D:一見数学ゲーと見せかけて実はグラフゲー まじかー

ちなみにrisujiroh曰く数学ゲーとして突き詰めると制約をかなり厳しく出来るらしい

E:見た瞬間解けなかった。これ忘れがちだよね。

F:遷移計算をノリでやったら間違えた。反省してます。

G:a_nへの水やりは必要でしたか...?

H:謎

 

 

 

楽しコンテストでした。運営の皆様、有難うございました。

HUPC2020 参加記

 

北海道行くぜ！

f:id:kort0n:20200916234736p:plain

北海道楽しみ～2020

どうしてこんなことに...

どうして...

 

チームはどうしようか悩んでたんですが、TLで全然募集ツイ見かけないし皆組んじゃったのかなと思って全日いつものチームで

前日当日に人々がチームメイトを募集していてウケた

Day1(北大セット)

 全問(想定)難易度順らしい 初手は

A:Rubikun

B:risujiroh

C:kort0n

で、後はよしなにということに(結局3日ともこれに)

Cを読む 変わった制約に頭を悩ませるが、結局前20個だけ上手くやれば良いと分かる。

AをRubikunが通す。Bは暫く詰めたいとのことだったのでCを先にやることにする。変な探索をしようとしていたので再帰関数で実装を始めるが、素直にfor文で調べれば良いことが分かる。まあわざわざ書き直すものでもないしこのまま再帰関数で...

実装し終わったので提出する RE は？

一旦PCをrisujirohに譲りデバッグを始めるが、バグが見つからない。Bを通したrisujirohにもデバッグに参戦してもらうと、

「これスタックオーバーフローとかしてんじゃない？」

と言われる。いや、まさか

for文で書き直す AC は？

 

この間にRubikunがDを解いていたらしく、実装を始める。

Eをやれと言われて考える。

 

各ノードを頂点倍化

各ノードのin -> 各ノードのout

source -> 偶数番目のアルファベットに対応するノードのin

偶数番目のアルファベットに対応するノードのout -> ワープ可能な奇数番目のアルファベットに対応するノードのin

奇数番目のアルファベットに対応するノードのout -> sink

のグラフの最小カットが答えに一致するな！よし！

 

 

 

...絵を描くと分かるが、これ頂点倍化がマジで無意味。二部マッチングの辺を分割してるだけ。

 

 

こうして、これが最小頂点被覆問題であることに気付かずに最大フロー最小カット定理を振り回して解く は？

 

Dが割と炎上していたが無事鎮火したようなので、満を持してEの実装を始める。

サンプルが合ったので投げる。WAが出る。は？

コードを読み直す。

f:id:kort0n:20200917000817p:plain

あっ

何と、距離がKより長いところもワープ出来るようにしてしまっていた。

修正してsubmitする。WAが出る。何で？

慌ててコードを読み直す。

f:id:kort0n:20200917000935p:plain

？？？？？？？？？？？？？？？？？？？？？？？？？？

"A or B and C" という最悪コードを書いていた 初心者か？？？？？？？？？？？？？

kort0n「andとorごちゃ混ぜで書いてたわ...」

risujiroh「あー まあでもandが先に評価されるように書いてれば問題無いよ」

kort0n「andが先に評価されると困る」

risujiroh「じゃあ終わりだよ」

終わってたので修正してsubmitする。ようやくAC。

 

risujirohがGを解いたと主張していたので、Fを考える。暫く考えると解けた気になる。

risujirohがGを提出し始める。WAやらTLEやらが出て明らかに「「「始まって」」」いた。

暫くしてFが解けた気になったのでPCを奪い取って実装する。提出する。WA は？

考えるが全くバグが分からない。risujirohもGとバトルを続けるが通らない。そのままコンテスト終了...

 

後で確かめると

F:数え上げの係数を1つ掛け忘れていた

G:計算量は想定解と同じだが、定数倍で落ちていた

だった...

 

f:id:kort0n:20200917001803p:plain

...

冷えすぎて通話が冗談も飛ばないレベルのお通夜になる。どうしてこんなことに...

 

問題の感想

C:スタックオーバーフロー許さないからな

D:マジで実装方針で明暗分かれそう 問題自体はまあ好きです

E:典型問題のカモフラージュが上手い 最後の条件判定が辺じゃなくて頂点ベースで書いてあるから全然気付かなかった

F:AのsumとBのsumしか関係無いのかなりビックリで好き(これに気付いたのはrisujirohだけど)

G:ねっとりしてる

H:こういうのから逃げ続けて1年くらい経ってしまった...

 

Day2(会津セット)

TLで野良チームを組んでいるlatteとtatyamがcatsatmatをもじって*atを名乗っている。たのしそ～

f:id:kort0n:20200917002437p:plain

 

*atじゃないけど認められた たのし～

 

f:id:kort0n:20200917002323p:plain

 

え？

 

f:id:kort0n:20200917002504p:plain

 

正直紛らわしかった。マジでごめん。

 

 それは違うだろ

 

コンテストの時間になる。

Cを開く。

kort0n「これもうrisujirohに投げたいんだけど」

risujiroh「じゃあswapするか」

持つべきものは得意分野の異なるチームメイトよ

Bを開く。問題文の長さと中身の面倒臭さで今年一番の笑顔になる。

RubikunがAを、risujirohがCを通したところで実装を始める。

Bの実装に無限時間掛かる。この間にRubikunがDとGを解けたと言う。すげー

Bを通してLを読む。「これどんなケースでもlogステップくらいで終わるんじゃない？愚直にやって終わるんじゃね？」とか言う。

DとGのFAを爆速で回収したRubikunに「↑の反例ある？」と聞きつつ他の問題に手を着ける。Jの解法が生える。risujirohがMを通した後Jを通す。

他にすぐに分かる問題も無くなってきたので、Kを実装する覚悟を決める。この間にRubikunにLのNステップくらい掛かるケースを発見されて萎える。

risujirohがIを通すのを待ってKの実装を始める。途中risujirohがEを解いたので通してもらう。

色々苦労しつつもKでサンプルが合う。提出する。

 

kort0n「これ落ちたらデバッグは無理です」

 

f:id:kort0n:20200917004212p:plain

 

kort0n「終わった...」

 

半分くらい通ったところで落ちているので尚の事絶望感が凄い。

しかし、問題文を読み返すとただの誤読であることが分かる。修正してsubmitするとAC 見たか会津

 

残りがFHLになって、割と手詰まり感が出てくる。

Lは賢い計算方法なんてありそうも無いし、シミュレーションを高速に行う方法を考える方向にシフトし始める。「successorが高速に求まれば良いのにね～」等と言っていると、突然risujirohが「そういえばGifted InfantsのライブラリにFastSetってのがあるよ」と言い始める 確認すると、successorがΘ(log_{wordsize}N)で求められることが分かる。

これを使ってシミュレーションする。AC。

 writer、スマン...

残りがFとHになる。暫くすると、risujirohがHを解けたと言って実装を始める。仕方ないのでFを考え始める。

正直あまり解ける気がしていなかったので、ダラダラしながら適当に考えていると、突然天啓が降ってきて解けた気になる。PCを奪い取って実装するとサンプルが合う。submitするとAC 神～～～～～～～～～～～～～～～～

その後ヤジを飛ばしつつHのライブコーディングを見守る。一度WAが出たものの、デバッグとストレステストを終えて再提出するとAC

 1日目はチーム最低レベルの冷えだったが、2日目は序盤から終盤までほぼ失速せずずっと好調で最高レベルの出来だった。良かった...

問題の感想

B:笑顔

C:Cでこのレベルが出るのか...

D:これ速攻で通されてたけど普通に難しくないか？

E:これ途中考えてたんだけど普通に解けなきゃダメなやつだなぁ 問題は好きです

F:3日通しての瞬間最高風速多分ここだった でも解説pdf読んで問題の解釈にビックリ そんなこと考えてなかった 「スコアの定義が人工的で謎だね」とか言っててスマン

G:あ、実家だ！

H:解法が天才だった こういうの苦手だな つぶあんってすげぇよ...

I:こういうの難しいけど答え見ると「当たり前じゃん」ってなるよね...

J:3問ぶりの帰省

K:＾＾

L:これ想定解の計算量の落とし方はセットで一番好きまである でもコンテスト向きではないよね 難しい...

M:想定解好き K<=1e5にしない方が面白くて良いよね

Day3(ごった煮セット)

 らしいので、2時間47分で全完しようと思いますゥ

 

Cを読むと秒で解けたので、Aの後に実装する。2位に4分近い差を付けてFA。冴えてる～

Fを読むと、それっぽい未証明エスパーが生える。Cを瞬殺したことで調子に乗っているので、「うーん、出すか！」と言い始める Bが手間取っていたようなので、PCを奪い取って実装して出す。WA。本当にすみませんでした。

risujirohがBで苦戦していたらしく、途中でRubikunにパスしていた。その間にIMを通す。

RubikunがBで頑張っているが、なかなか通らない。この辺で順位表を見て、どうもBの難易度が異常らしいということを察し始める。この間にrisujirohがEをサクッと通していた。

Rubikunもギブアップして、Bが飛んでくる。こういう算数は苦手なので、初手実験をする。結果があまりに非自明でビックリする。誰だよこれBに置いたの。

実装して2WA吐きながら通す。この時点では順位は酷かったが、実装待ちが3問+実験すれば分かるだろが1問という感じだったので、ここから巻き返していきたいね等という話をする。

Bのデバッグ中にちょいちょい実装を進めていたKをrisujirohが通す。

Fで実験をした結果あまりに良い性質が見つかったので、それに基づいて考えると解けて、通す。

実家のGを通す。

risujirohがHの実装を始める。これは流石に大変そう。

解法が出ていない問題がD, J, Lになる。Jを考えると、細部はちゃんと証明出来ていないが計算量が落ちていそうな解法が生える。

HのACを待って実装する。雑にランダムケースを試すと速そうだが、ランダムケースは雑にやっても速そうなので困る。悩んでも仕方が無いので投げると通った。よし！

この間にRubikunがDの解法を生やす。実装はヤバくなりそうだからやってほしいと言われたので、実装を始める。この間にrisujirohとRubikunがLを詰め始める。

実は並列二分探索の実装をするのは初めてだったので色々とバグを踏む。苦労しつつもデバッグして提出する。WAが取れない。1ケース目で落ちているので何かがおかしい。確かめると出力時に0-indexedを1-indexedに直し忘れていた  そう...  直すとACする。

この間にLが2人によって完全に詰められている。応援していると通る。

 2日続けての全完だし、最後の3問が3人で1人ずつ解法を生やした感じになっていたのでとても良かったと思う。

 

問題の感想

 

B:つぶあんは凄いと言ったな 撤回します

C:秒で解けて自分すげーって言ってたけどAtCoderで類題解いてたことに後で気付いて悲しくなった

D:ザ・やむなく問題感がある やむなく問題すげー

E:これrisujirohの実装方針で感動してた すごい

F:これ実験せずに解けた人どれくらいいるんだろう...

G:

kort0n「これは実家」

risujiroh「君の実家広そう」

H:risujiroh、ありがとう...

I:最初「頂点iと頂点jの間の辺のコストはgcd(A[i], A[j])と誤読して困ってた これ解けますか？

J:シンプルに難しかった 状態数指数的に増えそうに思っちゃう

K:最近帰省回数が多い

L:ステップ数が多い上に各ステップもそれなりに非自明で、ICPCセットの難問枠感がある

M:最後の帰省

 

 

楽しいコンテストでした。運営の皆さん有難うございました。