結果

問題 No.4 おもりと天秤
コンテスト
ユーザー らっしー(raccy)
提出日時 2015-08-22 21:05:19
言語 Ruby
(3.4.1)
結果
AC  
実行時間 980 ms / 5,000 ms
コード長 2,324 bytes
コンパイル時間 81 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2024-06-26 09:16:59
合計ジャッジ時間 4,050 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

# coding: utf-8
# おもりのリストのクラス
class Omoris
  # 初期化時にソートする。
  def initialize(list)
    @list = list.sort
    # その前での合計リスト
    @sum_list = @list.inject([]) do |m, i|
      m << m.last.to_i + i
    end
    # 結果のキャッシュ
    @cache = {}
  end

  # おもりの合計を返す。
  def sum(index = -1)
    @sum_list[index]
  end

  # end番目以前の組み合わせで合計がtargetになるか？
  def check(target, last)
    if @cache.has_key?([target, last])
      return @cache[[target, last]]
    end
    # 0なら合致しているのでOK
    return true if target == 0
    # 最後の前まで調べる。
    (0..last).to_a.reverse.each do |i|
      if target > @sum_list[i]
        # 全部足しても届かない
        @cache[[target, last]] = false
        return false
      elsif target == @sum_list[i]
        # 全部足すと一致
        @cache[[target, last]] = true
        return true
      elsif i < last && @list[i + 1] == @list[i]
        # 2回目以降で前と一緒なら調べる必要なし。
        next
      elsif target < @list[i]
        # 越えちゃったので次を調べる。
        next
      else
        # 少ないときはtargetから今の分を減らして、さらにcheckする。
        if check(target - @list[i], i - 1)
          # 合致したのでOK。
          @cache[[target, last]] = true
          return true
        else
          # あわなくても次を調べる。
          next
        end
      end
    end
    # 一致なし
    @cache[[target, last]] = false
    return false
  end

  # 重りのインデックス
  def [](index)
    @list[index]
  end

  # 重りの数
  def size
    @list.size
  end
end

# 1行目はRubyでは不要。
gets
# 数字のリストを取得。
omoris = Omoris.new(gets.split.map(&:to_i))
sum = omoris.sum
# 合計が偶数で無いと組み合わせは無い。
# 2個以上重りが無いと組み合わせは無い。
# 一番大きい重りが半分以下で無いと組み合わせは無い。
# 合計の半分の組み合わせをチェックする。
if sum.even? &&
    omoris.size > 1 &&
    omoris[-1] <= sum / 2 &&
    omoris.check((sum / 2 - omoris[-1]), omoris.size - 2)
  puts "possible"
else
  puts "impossible"
end
0