ぱろっと・すたじお

技術メモなどをまったりと / my site : http://parrot-studio.com/

天才火消しエンジニア霧島さんのトラップに引っかかった件

Ruby POH

今回はいろいろ油断があったわけですが・・・

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite

・・・って、よく見たら霧島さん＝挑戦者＝私でしたかΣ(ﾟДﾟ)ｶﾞｰﾝ
それだと美しくないなので、霧島さん（26歳女性）の依頼で問題を解いたという体にしてですね・・・

とにかく今回は油断があったわけです

  • タイトルに「Lite」と入っていた
    • たぶん簡単なんだろうと誤解した
  • 問題が前回に比べて簡単に見えた
    • 前回はまず仕様をどうコードに落とすかが壁で、今回は書くだけなら簡単
  • 前回うかつにもSSSを取ってしまった
  • 最初に書いたコードでCase5を通過してしまった
    • しかも0.02sというかなりのタイムで

特に最後のが致命傷で、「あ、もうちょっとやん」と思ってしまったんですよね・・・
そこからが面倒だったのに(´-ω-)

とはいえ、前回に比べれば比較的シンプルで、
アルゴリズム勝負になっていたのは間違いありません

問題をどう捉えるか？

最初は1回目*1のような簡単な問題だと思ったのですが、
あれは「ペア」という縛りがあったのに対し、
今回は「任意のn個」（n <= 会社数）の組み合わせが存在します

nが小さいうちは総当たり・・・つまり、
全ての組み合わせについてコストを計算したあと、
条件を満たすデータを探す、という手も使えます

result = []
(1..(companys.size)).each do |n|
  # n個の組み合わせを全て抜き出す
  companys.combination(n) do |list|
    # 人数が足りないなら無視
    next if list.map(&:member).inject(:+) < need_member
    # コストを計算
    result << list.map(&:cost).inject(:+) 
  end
end
# 最小が答え
puts result.min

擬似的なコードですっごく雑に書くとこういうことですが、
nがちょっと大きくなるだけでも、
あっという間に組み合わせが発散してしまいます(lllﾟДﾟ) *2

一方で、ある程度総当たりしないと、
「どれが最小か？」はわからないのも事実です

1回目の時は目標金額が設定されていたため、
ある程度答えが見えたら切り捨てることも可能でしたが、
今回その手は使えません

結果的に、見た目は簡単そうでも、
実際には「高速なアルゴリズムを使う」か、
「適切な足切りを探す」か、その両方かが必要だったのです(´-ω-)

いきなりCase5を突破

以上をふまえてコードを書き始めたわけですが、
前回さんざん苦労させられた結果、
処理速度を上げるポイントはだいたいこんなところだろうと

  • データを「リスト」として処理する
    • 前回は盤面をbit化し、数値の配列として処理した
  • （Rubyの）eachで回すより、indexでアクセスした方が早い
    • RubyのEnumeratorは高性能だが、オブジェクトアクセスなので遅い
    • とはいえ、Arrayもオブジェクトなので、Cの実装レベルで最適化されている可能性
  • 無駄なデータを早めに刈り取る
    • 明らかに要件を満たせないデータはそもそも処理しない
  • うかつなソートは遅くなる

リストを探索するルートは以下のようになるはずです

1つ目を起点にする
  2つ目を足してみる
    3つ目を足してみる
      4つ目を足してみる
    4つ目を足してみる
  3つ目を足してみる
    4つめを足してみる
  4つ目を足してみる
2つ目を起点にする
...

1
1-2
1-2-3
1-2-3-4
1-2-4
1-3
1-3-4
1-4
2
...

つまり、ツリー構造の探査になります
で、各探査のタイミングで、条件に見合わないと確定したら切ってしまうわけです
ある時点でわかっているコストより、そこで計算したコストが大きければ無駄です

これを再帰的に処理するように書いたのが最初のコードです(´･ω･)っ

この時点でいろいろ考慮されていたのもあり、
最初からCase5で0.02sを叩きだしたわけですが、
ここからが問題でした(´-ω-)

メンバー数で足切りする

計算量を減らすには、「ここより先は無駄である」ということが、
「明確に言い切れる」条件を探す必要があります
今回の場合、この「明確に言い切れる」の部分が難しいのです

まず思いついたのが、「メンバー数」です
あるノードを見ている時に、あと20人必要だとしても、
その先の全ノードを足しても20人に満たないならそこで切り上げることができます

しかし、「この時点では」無駄でした(´･ω･`)

深さで足切りする

先ほどのcombinationを使った擬似コードにおいて、
例えばn=3の時点で答えの候補が見えているのであれば、
n=4でそれより小さい値が見つかるとは思えません

そこで、「深さ」の概念を追加してみたわけですが、
元々ツリーの途中で適切な足切りが実装されており、
あまり効果がないどころか、むしろループを増やすだけでした(´-ω-)

そもそも、nが大きい場合に、
n=2とか3で組み合わせ数が爆発する問題は解決しないわけで・・・

試行錯誤

この辺から完全に行き詰まったのですが、
やはり複雑なデータ構造を作るほど遅くなるため、
どうにもうまくいきません

問題が良くできているので、「一か八か、データ依存」的な条件を追加しても、
今度はCase5すら通らなくなるのです

コスト効率を考える

ここでいったんしばらく時間をおきまして、
一度頭をリセットしてやり直しました

冷静に考えると、足切りするには何らかのソートが必要です
でも、今回はデータのベクトルが「メンバー数」「コスト」の2次元なので、
どちらかの概念でソートしても、足切りがうまくいかないのです

ならば1次元化、つまり「コスト/メンバー数＝コスト効率」でソートすればと、
一度は考えていろいろ試したのですが、決定打がありませんでした

しかし、冷静に考えれば、「コスト効率×メンバー数＝コスト」です

もしコスト効率でソートされている場合、
ある時点での「コスト効率×残りメンバー数＋現時点でのコスト」が、
最小値を超えてしまうのであれば、それ以降の計算は無駄です

例えば、あるノードの時点で
「わかっている最小コスト100、コスト効率1.2、残り20人、現時点でのコストの和が80」
だとします

すると、「次のノードのコスト効率」は1.2以上であることが保証されており、
コストが「80+1.2*20」以上になることが確実です
なので、ここで切り上げてしまっても問題ないことになります

これを追加したところ、Case6を突破しました(`･ω･´)

もう一度メンバー数で足切り

先ほど一度は棄却した「これ以降はメンバー数を満たせない」という足切りですが、
今度は一次元の概念でソートされており、
うまく寄与するのではと予測しました

ついでに、コスト効率に関してももうちょっと見直しまして・・・

・・・Case7を突破し、S評価を獲得ですヽ(`･ω･´)ノ

まとめ

実は、前回の2回目で行き詰まった際、
「次元を落とす」というのを試していました

前回はうまく当てはめることができなかったのですが、
今回の場合はまさにぴったりだったようです(`･ω･´)

逆に、このような1次元化を導入したので、
探査ロジックを見直すことで、
まだまだ数秒縮められる気がします

「起点」という考え方を捨てて、
全体を一つのツリーとして見なせば、
ループを削れるのはわかっているのですが・・・

（まさにこれを書きながら気づきました
　前回もそうだったのですが、「行き詰まったらBlogに書いて整理」というのも、
　一つの手法かもしれません）

・・・暑いし、やることが他にある*3し、あとはお任せしますΣ(・ω・ノ)ノ


for "https://paiza.jp/poh/kirishima/"

*1: https://paiza.jp/poh/ec-campaign 私のコードはこちら(´･ω･)っ https://gist.github.com/parrot-studio/7763295

*2: ちょっぴりグレーな方法・・・適当なところで例外を上げるようにしただけ・・・で確認したところ、Case5まででだいたいn=10、Case6でn=30程度でした　おそらくCase7は最大のn=50でしょう

*3: 「チェンクロパーティーシミュレーター」を開発中です(´･ω･)っ http://parrot.hatenadiary.jp/entry/2014/07/15/142913