ACPCVC20200210 復習メモ

not-522.appspot.com
難しい

A: Coins

まず、 でソートすることを考えてみると、金のコインをあげる人は、銀のコインをあげる人よりも左に来ることがわかる。
もし、銀をあげる人が金をあげる人より左にいた場合、もらい方を交換することで、必ず正の差分が生まれることから言える。
ここからは0-indexedで考える。
すると、 までの人が金のコインと銅のコインをもらい、 までの人が銀のコインと銅のコインをもらうことになる。
この時、 というように を大きくしていき、追加した人が金のコインを上げるべきかどうのコインをあげるべきかということを選んであげると、これはpriority_queueなどで処理ができるので、 で処理が出来る。 銀のコインに対しても、後ろから同じことをすれば良い。
それぞれ最大化した に関する和を求めることでこの問題は解くことが出来る。

小さい問題で考えてやると良いなと思った。面白いなあ。

B: Namori Grundy

閉路でない部分の の部分は一意に定まる。葉の部分は0になり、順番に子の値に書かれていない値の最小の値が になるためである。
すると、このグラフは閉路の部分だけ残る。
閉路の部分にあり得る値は、閉路ではない頂点の値に書かれていない最小の値と、2番目に小さい値しかない。2番目に小さい値を採用するときは、閉路側の出力ノードの値が1番目に小さい値の方になっているとうまく成立している。
最後に矛盾するケースが現れる。2回試して頑張ると、そこを判定してどちらか矛盾していなければ、POSSIBLE、どっちもダメだったらIMPOSSIBLEかを出力すれば良い。

解が一意に定まる部分があることを見ておけば、問題が簡単になったかもなあ。

C:Young Maids

辞書順最小にしなければならないので、小さいものから取っていくために、一番最後から処理をしなければならないと考察できる。
どのように処理を行えば矛盾がないかというと、「２つの辞書順最小になる値を取り出しても、取り出して出来る3つの区間の大きさが偶数になっている」ことである。
あと、２つの値を取り出すには、中を先に取らないといけないので、答えとしては後に出てこないといけないことに注意する。
3つの区間に分割統治して、priority_queueを使って辞書順最小の値を取り出しながら処理していくと良い。
高速に小さい値を取り出すには、奇数番目の値だけ持ったRMQと偶数番目の値だけ持ったRMQ を使ってやると、矛盾のない条件で辞書順最小の値を取り出すことが出来る。

説明意味不明になってしまった。　うーん

感想

発想自体はそこまで難しくないようにおもえる。
問題の言い換えとか色々としてみて、解法を考えていくと良いのかな。