Australia

ウォンバットのブログ

ICPC2021 国内予選 参加記

昨年に引き続き、ぴーよ (holeguma) さん、まさよし (masayoshi64) さんと組んでチームPWMtreeで出ました。4完25位でした。

本番

開始1分くらい問題が見られませんでした。1年前を思い出すいい余興でしたね。

Cの担当だったので見ます。構文解析だったのでとりまガッツポーズ。しかし設定がややこしすぎないか?
なんか普通に木DPをすれば通りそうな気が一瞬しますが冷静に考えるとそんなことはありません。Cで全方位マジ? と半信半疑になりながらも、そこまで頑張れれば行けそうな感じだったので詳細を詰めていきました。

ABを通したぴーよさんとまさよしさんがDEを見ていました。Dは天才系っぽい見た目で、Eはまだなんか行けそうっぽい。
Cの実装を一時中断してDを見てみますがわかりません。これで詰まるのかなり嫌だなあ……と思いながら、とりあえずCを通しました。ここまでの間にお二方の協力プレイでEの解法が生えたらしい。

Eが通ったあたりで、もうここからDを通すだけでは予選通過させてくれない雰囲気を順位表が醸し出していました。無難な順位を狙ってもしょうがないので、僕がDの考察を、お二方がFの考察をすることにしました。

D、全然わからん。Fも流石に難しいみたい。こうしてコンテストが終了しました。

感想

速解きが得意なチームではないので、今回のセットだとどうやっても通過は難しかった気がしますが、Dが解けなかったのは論外ですね……。
でも解法聞いたところで、うわそれなんで思いつかんかったんやとはならず、むしろなんでこんなに通されてるねんの気持ちが強かったので、うーん。
Ad-hocできなさすぎてダメですね。問題をたくさん解かなくては。ライブラリ整備ばかりしてる場合じゃない。このままじゃAtCoderのレートも上がっていかないし。

今回をもってPWMtreeは解散です。寂しさと悔しさが募ります。でも楽しかった。本当にありがとうございました。
東大チームのコーチを引き受けてくださったDEGwerさんにも深く感謝です。

来年以降どうしようかな……。

おまけ


ワインの種類ごとにイメージ芸能人が振られていたので、ガッキーのを選びました。お酒の選び方よくわからないがちなのでこういうのがあるとありがたいです。美味しかったです。

AtCoder Heuristic Contest 001 参加記

はじめに

反省点の一つでもありますが、コンテスト中に記録をつけることを怠ったため、以下の内容は僕の記憶に基づいており、不正確な記述を含む可能性があります。

参加にあたって

AHC は個人的にかなり楽しみに待っていました。その記念すべき第一回ということで、今回僕はガチ参加しました。多少中だるみもありましたが、期間中のかなり多くの時間をコンテストに使ったと思います。


恐縮すぎる。
言語は Rust を使用しました。Rated コンテストで使うのは初めてです。

結果

スコアは 991,112,901,526 で順位は 19 位でした。

解法

「領域全部を広告で埋めた状態で焼きなまし」です。

f:id:packer_jp:20210320010017p:plain

初動で「広告を 1 マスずらしたり 1 マス拡大縮小したりする焼きなまし」を実装しましたが、あまりスコアが出ず、座標がほとんど連続量であるために解空間が大きすぎるのが良くないと考えました。そこで、状態の重要なパラメータを各点の座標というより広告同士の隣接関係にすることで、状態空間を実質的に狭めたいという考えがありました。なお、広告が大きすぎる分には焼きなましの後に削ればいいので全く問題はないです。座標がほとんど連続量であることがここではメリットとして効いています。
焼きなましの近傍としては
① 連なっている線分を動かす
② 2 頂点を共有する 2 つの広告について、境界となる線分の縦横を入れ替える
③ L 字型をなすように隣接している 2 つの広告について、境界となる線分をスイッチする
の 3 つを用意しました。これらがあれば状態空間を結構広く探索することができると思います。(完全に連結かどうかはちょっとよくわからないです……。)

f:id:packer_jp:20210320005910j:plain

ひとつひとつの広告を長方形として持つような実装になっています。隣接関係などは遷移の度に更新するより評価の都度に調べたほうが高速でした。

反省

僕の方針で良くなかったのは、最終的な解を限定してしまっている点と、多峰性が強いのに kick 近傍を取り入れるのが難しい点だと思います。「領域を完全に広告で埋めるのではなく、四畳半の真ん中のような隙間を空けることを考慮する」ことでこれらを同時に解決することが可能だと思っているので、今度実装してみるかもしれません。(隙間を空ける考え自体はコンテスト中からあったのですが、kick 近傍については気づいていませんでした。高速に動作するような実装がかなり難しいので今の解法を詰めるのが優先だと判断してしまいましたが、気づいていれば踏み切れていたかもしれません。)
また今回、マラソン系コンテストに挑むにあたっての事前準備がかなり不足していました。ビジュアライザを作るための何らかのフレームワークに習熟し、並列実行ができる環境も整えなくてはなりません。並列実行の環境ができていなかったために手元で試すケース数が不十分であり、(運良くシステスでは踏まなかったようですが) バグを埋めたことに気づきませんでした。Rust の知識が付け焼き刃すぎて困る場面も多かったです。Rust 自体はいい言語かつマラソンにも適していると思うので次回以降も使っていきたいです。

感想

ガチ参加したので多くの方々に勝つことができましたが、ガチ参加しても 18 名の方々には勝てなかったのが悔しいです。
自分はわりとアルゴよりもマラソンの方に適性があると思っているので、AHC は今後も頑張っていきたいです。

ICPC2020 国内予選 参加記

ぴーよ (holeguma) さん、まさよし (masayoshi64) さんと組んでチームPWMtreeで出ました。5完20位でした。

回想

僕は高専から大学に編入しました。高専ではICPCには出ていません。理由としては国内予選に通る自信がなかったこと、参加する文化がなかったこと (岐阜高専からICPC参加したチームって今までにあるんでしょうか?)、忙しかったことなどが挙げられます。

大学に入って、ICPCに出てみたいとはぼんやり思いつつも、界隈に親しい人がほとんどおらず、数少ない友人を誘ってチームを結成するバイタリティもなかったので、まあ今年は出ずに終わるんだろうなと思っていました。そんな僕をぴーよさんが拾ってくれました。

チーム練

*UPCの類にいくつか出ました。過去のセットを使ってバチャをやりたいですね、という話はしていましたが、やり方がよくわからずズルズルと来て結局本番1週間前に1回やっただけでした。

本番3日前

というわけで構文解析担当になってみました。構文解析の概念を学び、何問か通しました。

本番

始まった! と思って問題を見ようとしたら開けなくて草を生やしていました。

しばらくしたら復旧したので、予め決めていたとおりBを見ました。問題文がなかなか頭に入ってこずに苦労しましたが、普通に実装して通りました。
先にAを通したぴーよさんがDが構文解析だと教えてくれました。一点読み成功! しかもDという丁度解けそうな位置。

意気揚々と取り掛かりますがなかなか解けません。構文解析自体は本質ではないようでした。このときCも詰まっていて、まさよしさんとぴーよさんが色々やっていました。

悩んでいるとこれがよぎってDの解法が生えました。結局全探索を回すことにしたらしいCと同時くらいに通りました。

Dが通った時点で既にぴーよさんまさよしさんがFの考察を終わらせたらしく 、ぴーよさんが実装をしていました。僕とまさよしさんでEの考察をしました。
しかしこれが全然解けません。グリッドグラフの独立集合を数えればいいんですが、斜めに区切ってDPをすると状態数が1.618^30くらいになるし遷移も厳しそうです。他にもいろいろ試しますが、悉くダメ。

さらにFがcase2で落ちたという報告がなされ、肩を落としました。それでもまさよしさんとEの考察を続け、いやこれ縦で区切れば状態数2^15で抑えられるやんけということがわかって草を生やしました。高速ゼータ変換を使えば遷移できるということもすぐにわかりました。僕が実装を始め、まさよしさんにはFのカバーに入ってもらいました。この時点であまり時間が残っていなかったのでかなり焦っていました。

Eの実装を進めようとするのですが、マジで頭が回りません。細かいところがめんどくさいタイプの実装だと思うのですが、1行書く度に次に何を書けばいいのかわからずまごついているような有様でした。

そうこうしているうちに、Fで解答ファイルを取り違えていたことが発覚したようで、投げ直したら通ったようです。あとはEを通せば! 焦れば焦るほど手は進みません。こうしてコンテストが終了しました。

今順位表を見直して気づいたのですが、Fが通ってからまだ20分残っていたらしいですね。本当に僕は何をしていたんでしょうか? しかもこの時苦し紛れに書いた高速ゼータ変換のコードですが、余裕で間違っていました。(ライブラリに、入れましょう)

感想

20位は健闘した方だと思うのですが、やはり悔しいです。自分は残り時間が少ないとべらぼうに弱くなる、ということが再確認できました……。

とはいえ、ちゃんと全力を出して燃え尽きた感はありますし、本当に楽しかったです。来年もこのチームでやろうという話になっているので、是非リベンジを果たしたいです。

チームメイトのお2人、コーチをやってくださったすぎやんさん、ありがとうございました!

第29回高専プロコン 参加記

人力部門に出ました。

4月

問題が発表される。今年も人力臭がすごい。とりあえず暗号化については深く考える必要がないことがわかった。
すぐに市松模様作戦を思いつくが、のちに却下。

5月

学内審査と予選を適当にかわす。

6月

ビジュアライザを作る。メンバー内でSolverコンペを企画するが、僕も含めて誰も何も作ってこなかったので断念。

7, 8月

虚無

9月

流石になんかやろうと思い、タイルポイントと自分の動きのみを考えたビームサーチを書いてみた。この時点で

  • タイルポイントが大事
  • タイル数も大事

くらいの最低限のことはわかっていた。因みに、ここから先何かがわかることはない。

10月

本番一週間前から学校を休んでいろいろやり始める。MCTSやαβを書いてみるが、どうも強くならない。
結局、最初に作ったやつを人力で補助するのが一番強いのではとなった。なんとなくビームサーチからchokudaiサーチにしてみた。

本番

リハーサル、バグで死亡。しかしエージェントが有能だったので勝ち。
予選リーグ、ヒューマンエラーで死亡。人力をする。何故か3連勝。
ホテルに帰ってUIとかいろいろ改善する。応援で来てくれた後輩たちにも手伝ってもらい練習する。
決勝トーナメント1回戦、ヒューマンエラーで死亡。人力する気も起きず、司令塔である僕が勝負を投げてしまう。今考えれば非常に申し訳ないことをした。敗退。
裏プロコン。貪欲に負けてびっくりした。(序盤で点数負けてる状態で競合して、そこから先ずっと譲る一方だった)

感想

人力要素なあ。方向性というのがあるにしろ、流石にもうちょっと工夫の余地があるのではないでしょうか。十分にUIを練って練習を重ねればどうにかなったとは思いますが、如何せん問題自体も水物感が強めだし、一発勝負のトーナメントとあってはあまり長い時間をとって取り組む気にはなれません。多くの人がそうだったのでは。
旅行ができたのと、裏プロコンで他高専の方々と話せたのは楽しかったです。
最後に阿南高専の補助学生の皆さん、本当にお疲れ様です。ありがとうございました。

AtCoder Grand Contest 026 D - Histogram Coloring

解法

高さが同じ 2列のヒストグラムを考えます。
左の列の塗り方が決まっているとき、その塗り方が赤青赤青……のように交互(以下マダラと呼びます)であれば、右の列の塗り方はそれと全く同じにするか真逆にするかの 2通りの選択肢があり、マダラでなければ真逆にするしかありません。
これを念頭に置いて、次のDPを考えます。

 dp[i][j]:=左から i列目までを順に決めた時の、 i列目の下 jマスがマダラである(下 j+1マスはマダラでない)パターン数

先ほど述べたことを使い、次のように場合分けして漸化式が立てられます。

  •  h_{i-1} < h_iの場合

  dp[i][j]= \begin{cases}
    2^{h_i-h_{i-1}}dp[i-1][j] & (j < h_{i-1}) \\ 
    2^{h_i-j}dp[i-1][h_{i-1}] & (h_{i-1} \leq j < h_i)\\
    2dp[i-1][h_{i-1}] & (j=h_i)
  \end{cases}

  •  h_{i-1} \geq h_iの場合

  dp[i][j]= \begin{cases}
    dp[i-1][j]& (j < h_i) \\ 
    \displaystyle 2 \sum_{j'=h_i}^{h_{i-1}} dp[i-1][j']  & (j = h_i)
  \end{cases}

 2冪の計算には繰り返し二乗法を使うとして、このままの計算量は O(N (\max h_i) (\log \max h_i))となります。さらに遷移の仕方をよく観察すると、全ての jについてパターン数を持つ必要はなく、縦軸に最低限の区切り(具体的には、各 h_iの上下)を入れて、区間和をもっておけばいいことがわかります。要は座標圧縮をするわけです。すると計算量は O(N^2 \log \max h_i)となり間に合います。

反省

想定解が横で区切っていたのに対して縦で区切ってしまいましたが、そこまで筋悪ではなかったと思うのでよしとしましょう。

AtCoder Regular Contest 103 F - Distance Sums

全然わからん→解説見よ→意味不明→制約見落としてた→えーん

解法

辺で繋がれたある 2頂点 u, vを考えます。辺を切ったときのそれぞれの連結成分のサイズを n_u, n_vとすると、

 D_v=D_u+n_u-n_v=D_u+N-2n_v

が成り立ちます。ここで、頂点 uを固定したとき 2n_v>Nを満たす頂点 vは高々 1つであることがわかるため、 D_u>D_vなる頂点 vは高々 1つになります。また、 D_u>D_vなる頂点 vが存在しないような頂点 uはちょうど 1つしかありません。
よって、 Dの大きい順に頂点を見ていけば、それに繋がるそれより Dが小さい唯一の頂点を定めることができます。
このようにして木が構築できなかったり、完成した木が入力の Dの値と合わなかったりしたら -1を出力します。

反省

問題文はちゃんと読みたいと思います。

AtCoder Regular Contest 103 E - Tr/ee

解法

木が構築可能であるための、次の必要条件が浮かびます。

  •  s_1=1
  •  s_n=0
  •  s_i=s_{n-i}

実はこれらは十分条件でもあります。具体的には、次のようにして構成できます。

  • 頂点 1, 2間を繋ぐ。
  • 直前に頂点 t, i(t < i)間を繋いでいたとする。 s_{i}=1の場合、頂点 i, i+1間を繋ぐ。 s_{i}=0の場合、頂点 t, i+1間を繋ぐ。

このようにすれば、 s_{i}=1のとき、頂点 i, i+1間の辺を切ればサイズ i, n-iの連結成分ができます。 s_{i}=0のとき、頂点 t, i+1間の辺を切ってもサイズ 1, n-1の連結成分しかできません。

反省

構築は色々なパターンがあって一般論を見出すのが難しいですが、とりあえず手を動かしてみるのがいいような気がします。