Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ライツアウト系の基本を学ぶ

ライツアウト系の問題は、地道にシミュレートすると100%間に合わないので、フリップするとはその問題でいうとどういう意味を持つのか?ということを考える必要があります。そこまでの累積和的なものだったり、パリティだったり、問題の性質そのものを利用したり。私は現状としてあまり得意ではなく、地力正答率が低いです。

そもそも地力で正答することが難しいのだから、オリジナリティのある問題を作ることは難しいのではないかと思います。だとすると、限られたパターンを学べば良いだけですし、色々な問題を解いて慣れていくのが良いことになります。まずは、

AtCoder 版!蟻本 (中級編) - Qiita

を題材にして勉強します。

問題

POJ3276

問題: N頭の牛が並んでいて前か後を見ている。範囲Kを反転することが許される。全員を前向きにしたい。これを達成する最小の試行回数と、その中でのKの最小値を求めよ。

一番最初に思いついた解法があるKでは貪欲にシミュレート出来ることがわかるので、Kに対して二分探索というものでしたが、Kの最小値は求まるけどそれが最小の試行回数かどうかもわからないので、どの道二分探索の問題ではなく全探索となります。従ってO(N3)でTLE。

この問題において気づくべき性質は、ある牛が最終的にひっくり返されるというのは、Kを固定した時には、K個前から自分のところまで(つまりKがオーバーラップする領域)に範囲の左端がある場合に、奇数回ひっくり返されているということです。従って、K固定の場合にO(N)になるのでトータルでO(N2)に落ちます。

これをノーヒントで思いつくのは天才的な気がしますが、

  1. 自分がひっくり返されるというのは、自分が奇数回ひっくり返されることであるまでは自明(ライツアウトの基本)
  2. そのためには何が起こればいいか?(これが問題によって違う)

と分解して考えれば、自然に思いつけるような気がします。

ARC88 B

D - Wide Flip

問題: 01列が与えられる。長さK以上の範囲をフリップすることがいくらでも許されるとして、すべてを0に出来る最大のKは何か?

K=1は自明です。長くするほど難しくなるということは直感的にわかります。

POJ3276と設定は似てますが、全く別の問題。解説を読んでも理解出来ず。ただ、知っておいても良い性質として、あるkとk+1番目が異なる場合、これらのフリップ回数は異なることになるため、仮にK=k+1としてしまうと、破綻するということはわかります(毎回どちらもカバーされてしまうからです)。

AOJ603

電飾 | Aizu Online Judge

問題: 長さNの01がある。任意の区間を一回だけフリップした結果出来る、最長の101010... or 010101...の長さを求めよ。

よく題材になりそうな性質です。例えば、例題から

1100101110

は、

(1)(10)(0101)(1)(10)

の5つに分解出来ます。例えば2番めの10をフリップすると、1010101という数列が出来るように、その両隣を接続することが出来ます。こうすると、隣り合う3つを網羅的に調べて、最大値を求めろというO(N)の問題になります。

私は地力でも、交互列を調べあげるという発想には至りましたが、残念ながら、上のようにきれいに分解するまでには至れなかったです。

RUPC 2018 day1-C 一致

問題: 長さNの数列がある。これに対して、前からi個と後からi個の集合が等しくなるiはいくつあるか?

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day1/problems/C

差分更新系というタイプのものです。ライツアウトの範疇なのかは不明ですが、何かあるiの時の性質が、それ以前の数え上げによって決まるというゴールの仕方はPOJ3276と似ているため、含まれてるのかも知れません。

前と後が等しいことをチェックするためにマップにカウントを持って毎回チェックしていると、それぞれの試行にO(N)かかるため破綻します。従って「集合が空か」とか「集合が何か小さい固定値か」くらいの判定に抑える必要があります。このために前からの場合を考えると、数が違う場合に集合に入れて、後ろに見つかった時に取り除くということにすれば、空になった時に前後が等しいということになります。

所感

01列と範囲フリップに関する性質を網羅的に学ぶことが良いと思いました。それ自体は限られるような気がします。