Rustコトハジメ

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

AOJのBalls and Boxesを全クリして感じたこと

前に、AOJのコースをやっていて、その理由は網羅性があって学習の効率が良いからという話をしました。組み合わせ最適化(DPL)の問題の中に、Balls and Boxesというのがあり、

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5

f:id:akiradeveloper529:20190307173830j:plain

ひたすら色々な問題設定でボールを箱に入れていくんですが、

f:id:akiradeveloper529:20190307173552j:plain

これを全クリして思ったことを共有します。

たかだか1つしか入れない系は簡単な傾向がある

例えば、DPL_5_Kなどは、「ボールの数がボックスより多い場合はだめ」ということがわかれば、ただの条件分岐でおわります。たかだか1つしか入れない系は、他にもただコンビネーションを計算して終わりというものもあり、問題が簡単な傾向があります。

1つ以上入れる系は、制限なし系の応用であることが多い

全12問中、私が一番苦戦したのはDPL_5_Cですが、この考え方は「全く制限がない場合から、制限に関する項目を排除する」という考え方です。これについては先日のブログで紹介しました。

https://www.rustforbeginners.com/entry/ja/2019/03/06www.rustforbeginners.com

他にもむずかしめのものとしては、DPL_5_Gで、これは制限なし系なのですが、この1つ以上入れる系は、この制限なしであるDPL_5_Iは、これを応用するだけで解けます。同様に、DPL_5_Jは制限なし系で、分割数を解くだけですが、

https://www.rustforbeginners.com/entry/ja/2019/01/26www.rustforbeginners.com

これが解けると1つ以上入れる系のDPL_5_Lが解けます。例えばここでは、「1つ以上入れなきゃいけないならまず1つずつ入れてしまってから考えれば良いよね」と考えればよいです。

このように、1つ以上入れる系は、制限なし系の応用であることが多いと感じました。逆にいうと、「1つ以上入れる」という制限を見た場合には逆に、「じゃあその制限を取っ払ったらどうなのだろうか」と考えることで解法を思いつく可能性があるということです。

問題設定は正規表現と関連がある!?

制限の3パターンは

  • 制限なし
  • たかだか1つ
  • 1つ以上

ですが、これはそれぞれ正規表現では*, ?, +に相当します。

これから思うことは、この制限自体が原理的にすべてのパターンを網羅しているということです。そういう意味では、AOJのDPLはやる価値があるのでオススメします。

特に、以下の3問

  1. DPL_5_C
  2. DPL_5_G
  3. DPL_5_J

は比較的難易度が高いので、時間がない人はこの3問だけでも解いておくと良いと思います。(この3問を解くなら全12問解いても時間は変わらないとも思いますが)