Australia

ウォンバットのブログ

ICPC国内予選2020 参加記

ぴーよ (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の連結成分しかできません。

反省

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

CODE FESTIVAL 2018 qual A D - 通勤

これを通せたおかげで予選通過できました。嬉しい。

解法

 X_0=0とします。DPをします。

 dp[i][j]:=ガソリンスタンド iまで来るにあたって、ガソリンスタンド jで最後に補給するとしたときの、そこまでのガソリンスタンドを書店に建て替えるパターン数

次の3つを考える必要があります。

  • 近くのガソリンスタンド jで補給をしていてガソリンスタンド iで補給ができないとき、ガソリンスタンド iを書店に建て替えても建て替えなくても変わらない
  • やや遠くのガソリンスタンド jで補給をしていてガソリンスタンド iで補給ができるとき、ガソリンスタンド iを書店に建て替えるなら最後に補給した場所は変わらず、建て替えないなら最後に補給したガソリンスタンドは iになる
  • めっちゃ遠いガソリンスタンド jで補給をしていてガソリンスタンド iまでたどり着けないとき、ガソリンスタンド jまでの情報は無意味になる

まとめると、次のようになります。

  dp[i][j]= \begin{cases}
    \displaystyle \sum_{F - T< X_i-X_{j'} \leq F} dp[i-1][j'] & (i=j) \\ 
    2dp[i-1][j] & (0 < X_i-X_j \leq F - T)\\
    dp[i-1][j] & (F - T< X_i-X_j \leq F)
  \end{cases}

これを愚直に処理すると O(N^2)となりTLEします。データを使いまわしてオーダーを落とすことを考えましょう。
列の末尾 n項を 2倍し、その前の m項の区間和を末尾に追加するという操作ができればいいわけです。
さらに、項は「 2区間」→「区間区間」→「無意味な区間」と移動する事を利用し、それぞれの区間をqueueで持ち、区間和も持っておけば、遷移が高速化できます。要は尺取法なので、全体の計算量は O(N)となります。

反省

ARC070 Eでやったのと似たようなDPの高速化でした。勉強の成果が出せてよかったです。
この回のC問題と同じく、方針はすんなり立てられたように思います。DPは得意分野にしていきたいです。
そして何より


精進します!

CODE FESTIVAL 2018 qual A C - 半分

解法

 A_i=0になったら、それ以降は 2で割らないものとします。そうすると、求める答えは本来の「 K回の操作後の数列としてありうるものの個数」に「 K回未満の操作後の 0 1つ以上含む数列としてありうるものの個数」を加えたものになります。

 dp[i][j][k]:= A_1から A_iまで考えたときの、 j回操作してできる数列の個数( kはそれまでの要素に 0があったかどうかのフラグ)

というDPを考えれば、 A_i 2 c_i回割ると 0になるとして、

 dp[i][j][0]=\displaystyle \sum_{j'=j-c_i+1}^{j} dp[i-1][j'][0]
 dp[i][j][1]=\displaystyle \sum_{j'=j-c_i}^{j} dp[i-1][j'][1]+dp[i-1][j-c_i][0]

と遷移が定義できます。あとはここから適切に値をとってきて足し合わせればよいです。
計算量は O(N^2 (\log \max A_i)^2)になります。

反省

DPをDPだと気づくのはけっこう速くなったような気がしますが、詳細を詰めるのが苦手です。