ARC062-E『AtCoDeerくんと立方体づくり』をRubyで
2018-03-05
Tech会社のAtCoder会でARCのE問題をやったのだけど、解説を見て実装してもなかなか通らなくて大変だった。
「同じカードを複数の面に使うことはできない」という制約をうまく実装する方法がわからなくて、問題名で検索したところ、いくつか解説が見つかった。
- AtCoder Regular Contest 062 - E - AtCoDeerくんと立方体づくり - アルゴリズム忘備録
- AtCoder Regular Contest 062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer · うさぎ小屋
- AtCoder ARC #062 : E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer - kmjp's blog
方法はいくつかあるようだったが、使ったカードの一覧を持っておいて引くという実装が、簡単かつ速度も悪くなくて良さそうだった。
最終的なソースコードは以下。
usedというハッシュが上記の処理に相当する。上下の面も使用済みとしてカウントしないといけないのに注意。
速度チューニングはそんなにしてなくて、最後にhashnメソッドを書き直したくらい。このメソッドはかなりの回数呼ばれるので影響が大きい。Array#rotateを使わずべた書きすることで速くなった。
