WUPC2019のお話(解法編) - ツバサの備忘録

ということで、今回は各問題についての簡単な解法と、その感想です。
まだ解けていない問題もいくつかあるので、ご容赦ください…
運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。

emtubasa.hateblo.jp

各問題の方針と感想
全体の感想
コンテスト後の感想
- A
- B
- C
- D
- E
- F
- G
- H
- I,J
最後に

各問題の方針と感想

A - WAsedAC

問題
 提出コード
早稲田の先輩方と言えば、やはりこのチーム名ではないでしょうか。もうすぐWorld Finalもあるみたいなので、頑張ってほしいです！
今回のコンテスト唯一の簡単枠。後ろから貪欲に見ていけばよい、というものです。
実質の簡単枠はこれだけな気がしています(B問題は少し考える必要があるため)

B - 10puzzle

問題
 提出コード
パズル問題です。
基本的な方針ですが、マス全体の最大値を考えます。
全てのマスを全部0にしたいのですが、これはどこかのマスに5が存在する、もしくは最初からすべて0であるかのどちらかが成り立っていないといけません。ので、まずはその条件を満たしているかどうかを調べます。
この後は、上の2種類のうち、前者のみについて考えていきます。
全てのマスの最大値が4以下である場合、5である場合、6もしくは7である場合、8である場合、9である場合でまず場合分けが行われます。5の場合は1回の操作で、6,7の場合は2回の操作で、8の場合は3回の操作で、9の場合は4回の操作で全てのマスを0にすることができます。これは、全てのマスの最大値が5になるように調整する回数+全てのマスを選択して0に置き換える1回、の合計となります。
ですが、これにはコーナーケースが存在します。1行N列、もしくはその逆のパターンです。5が書かれているマスが端以外に存在すると、その左右のマスを1回で選択することができなくなってしまいます(5より大きい数が存在している場合に5を選択すると消えてしまうため)。ので、それぞれの部分に分けて計算していく必要があります。
具体例を出すと、
9 5 9 5 8
のようなマス目があると、左側の3つのマス目をまとめて3回操作を行って
2 2 2 5 8
となり、一番右のマスに対して2回操作を行って
2 2 2 5 2
となります。そして、最後に全部のマス目に対して操作を行うことで、全てのマス目が0となります。
こんな感じの場合分けを行うと、無事ACすることができます。
条件が少し細かいので、バグを抱えやすいかなと思います。
パッと解ける人は解けそうだけど、気づかない人は沼にはまりそうな問題です。まぁ、パズルなので…

C - Permutation City

問題
 提出コード
全然思い浮かばなくて、結果先輩に解法を教えてもらいました。
まず、ある頂点 $v$ についてみた時、そこから1つだけ辺を通っていける隣の頂点の集合を $U$ とします。すると、 $U$ の中から任意に2つ頂点を持ってくれば、この頂点のペアは距離が2以下になっています。また、 $v$ 自身も、この $U$ の中に入れても問題ありませんし、入れなくても大丈夫です。
ということで、基本的にグラフを木とみなしてdfsをしつつ、その戻り際にペアを作成していくことで、うまく答えを作成していきます。
再帰関数を用意します(solve()とします)。引数が次に見る頂点の番号です。
戻り値を以下のように設定します。

今見ている頂点 $v$ を含め、頂点 $v$ を根とする部分木全ての処理が終わっていれば-1
頂点を除く、頂点 $v$ を根とする部分木の処理が終わっていれば $v$

すると、solve関数では次のようなことをすればよいです。

今見ている頂点 $v$ と隣接していて、かつ処理がまだ終わっていない全ての頂点について再帰を行う
再帰をした際、戻り値が-1でないものをリストに記録していく
操作が完了した後、リストの中身同士でペアを作成していく
リストに格納されている頂点の個数が奇数であれば、 $v$ 自身もリストに格納し、同様にペアを作り、戻り値として-1を返す
リストに格納されている頂点の個数が偶数であれば、 $v$ を戻り値として返す

とすると、だいたいはうまくいきます。が、この場合にうまくいかないコーナーケースが存在して、dfsを開始した最初の頂点について呼び出したsolve関数が $v$ を戻り値として返すパターンです。このとき、最初の頂点のみ処理が終わっていないので、このままだと問題の条件を満たすことができません。
そこで、最初の頂点については、どこかしら隣り合った任意の頂点とペア、もしくはトリオを作成するようにコードを書き加えてあげれば、無事にACすることができます。
この問題、思いつくのも理解するのも解説するのも難しい気がします。..........

D - Choose Your Characters

問題
 提出コード
まずは $O(N^{2})$ について考えていきます。
ある区間 $[l,r)$ について、その区間内でキャラ $i$ に対して不利なキャラの数を $cnt[i]$ とします。すると、その区間の幅 $r-l$ に対し、 $r-l = cnt[i]$ となるような $i$ が1つでも存在していれば、その区間は問題の条件を満たしません。逆に、全ての $i$ に対して上の条件を満たさないならば、これは解の候補になります。
あとは尺取り法を用いながら、 $O(N)$ で $cnt[i]$ の更新、および $O(N)$ で確認をしていけば、 $O(N^{2})$ で答えを求めることができます。
さて、これを高速化しなければ、この問題を解くことができません。
今回は、 $cnt[i]$ の確認と更新の部分に注目します。
$r-l = cnt[i]$ となるような $i$ が存在するかどうかの確認は、 $cnt[i]$ の最大値だけをピックアップして確認するだけで、あっという間に行うことができます。これを実現するために、セグメント木を利用すればよいです。
ということで、 $cnt[i]$ をセグメント木に置き換えてしまえば、ある区間が条件を満たしているかどうか、を $O(logN)$ で求めることができるようになり、結局 $O((M+N)logN)$ でこの問題を解くことができるようになります(一見 $O(N^{2}logN)$ に見えるかもしれませんが、相性の更新回数はたかだか $2(M+N)$ 回、最大値を確認する回数も $2N$ 回になるので、このような計算量になります)。
これです(最新作のやつ探したんですけどなかったです…オンラインの専用部屋かどこかでボイスを聞けた記憶があるので、聞きたい人は是非)。
ということで人生初の自作した問題です。
自分が公開した際は、想定解が高速化する前のものでした。気づいたらすごい高速化されていたのでびっくりしました…w
せっかくなので、自分の好きなもので問題を作ろう、とした結果がこれです。~~スマブラ要素がどこにもない…~~
初めは、相性の段階をもっと多くして、ポイントのようなものを計算していくような問題にする予定でしたが、単純に解き方が思いつかなかったのと、相性の表現が伝わりづらい(スマブラをやってる方々なら微有利、微不利といった単語が通じますが、一般的には通じなさそうです)ので、やめました。

E - Artist

問題
 提出コード
まずは、180度という部分に注目しつつ、実験をいろいろします。
そして、i行目の、黒いマスの個数を $b_i$ とします。
すると、(x,y)というマス目で切り分けた時、 $b_{1 + k} = b_{x-k}$ 、 $b_{x+1+k} = b_{M-k}$ がなりたつことがわかります。これはつまり、 $b_i$ を文字列として考えた時、 $[1,x]$ と $[x+1,M]$ の区間が回文になっている、ということです(これは列でも同様です)。
あとは、このような条件を満たす $x$ の個数を調べればよく、回文判定をするのにManacherやローリングハッシュ等を用いれば、時間内に答えを求めることができます。
ハッシュの衝突には注意しましょう。
大学の実話から生まれた問題でした。この問題で一番楽しかったのは、サンプルケースの3つ目を書いているときです…
ちなみにこんな絵を描きます。
f:id:emtubasa:20190313023752j:plain

何の絵かは想像にお任せします。
自作したとき、個人的にはこれめちゃくちゃ面白い！となったのであわてて提案しました。が、先輩方に瞬殺されてしまったので少し悔しいです(流石です)。おそらく、やるべきことに気づく+必要な知識が揃っていれば瞬殺です(そのため、最初はC問題に配置されていました)が、肝心な必要となる知識が普段は見ない(と言いたいのですが、数日前に数問、この知識が必要な問題があったみたいです)ので、この位置になりました。

F - RPG

問題
 提出コード
最小カットを考えます。
「戦闘場面から次の戦闘場面への道のり」にすべて分解します(出発地点から最初の戦闘場面、そして最後の戦闘場面から終着点の部分は捨てます)。
そして、s,tという頂点を用意し、それぞれの道のりについて、

sから道のりの最初の頂点へ容量 $\infty$ の辺を張る
道のりの途中にある頂点を2つに分解し、1つめの頂点から2つめの頂点に向かって、その頂点で回復所を作るコストを容量とした辺を張る
道のりの最後の頂点からtへ容量 $\infty$ の辺を張る

という操作を行います。あとは、sからtへフローを流し、最小カットを考えれば答えとなります。

G - Teishoku

問題
 提出コード
定食の種類がとてつもなく少ないので、すでに準備した定食の種類を、ビットで持つことにします。
$i$ 番目の定食を食べたときに $2^{i}$ のビットがたつとします。
$dp[S] =$ 現在の準備した定食の状態が $S$ であるとき、そこから先に発生する不満度の合計の最小値
とします。
すると、
$dp[S] = min(dp[S + 2^{i} ] + 今i番目の定食を準備した際に発生する不満度の合計 )$
となります。
あとは、今 $S$ の状態の際に、 $i$ の定食を準備するとどれぐらいの不満度が発生するか、を高速に求める方法がわかればこの問題を解くことができます。
$data[i][j] = i$ 番目の定食を準備した際に $j$ 番目の定食を注文した人の中で発生する不満度の合計値
とすると、欲しい情報は、 $\sum data[i][j]$ (ただし、 $j$ は $S$ に含まれない)
となります。
なので最終的には、 $data[i][j]$ を前計算で求めることができればよい、ということになります。これは、累積和を使い、入力された定食の注文の情報を後ろから見ていくことで前計算が可能です。
これを自力で解けたのは結構うれしいです。しかも、考察自体もかなりさらっとでき、実装もすんなりいったので、大満足です。

H - Doki Doki Programming Clubs! (3/11追記)

問題
 提出コード
完全な解説ACです。頭良すぎませんか…？
$X,Y$ というクエリが与えられたとき、 $X$ の部員の方が少なかったとします。その際、 $K_{X}$ 回で計算を終えようとすると、 $Y$ 側のレートの数列を前計算で、長さ $K_{X}$ の数列に縮めておく必要があります。
縮めた後の数列に記録されるレートは、 $\sum A_{i + t_{X}}$
となります。
ということで、あらかじめ前計算をしておき、各クエリに対して $O(min( K_{X}, K_{Y} ) )$ で答えればいい、となるのですが、これだとテストケースによっては前計算で時間がかかりすぎてしまいます。
ということで、前計算をする範囲を、長さ $\sqrt{M}$ までの際のみに限定し、 $X,Y$ ともに $\sqrt{M}$ 以上であった際は素直に定義通り計算するようにすると、どちらも時間内で解けるような計算量で抑えることができます。また、一度行った計算は二回目以降行わないようにメモをするのも忘れないようにしましょう。
詳しくはこちらのツイートなり、後日アップされるであろう解説PDF(に書いてある…と思います)を読んでいただければと思います。