問題紹介

[ぴったり卵を生産 - その2] (https://paiza.jp/works/mondai/forest_contest_017/forest_contest_017__s_egg5)

今回解いたのは、「paizaの森練習問題コンテスト過去問題セット17」から、「 ぴったり卵を生産 - その2」。似たような問題が前にありました。

しかし前座の問題では n の上限は15だったのに対し、その2では上限が30。2 ^ 30 は10億くらいですね。この場合、さすがに総当たりは無理。お手上げーは悔しいので、色々考えて正解までこぎ着けました。

コード

コードの一部を載せます。

// Javascript
// 中略

  // 情報取得
  A = lines[ 1 ].split( " " ).map( Number );
  A.length = n;
  A.sort( function ( a , b ) {
      return a - b;
  });
  cut( A , 0 );
  
  // 再起呼び出し関数
  function search( arr , sum ) {
      // 終了条件（中略）
      
      else {
          // 取る方
          A2 = arr.concat();
          s2 = sum + A2[ 0 ];
          A2.shift();
          cut( A2 , s2 );
          search( A2 , s2 );
          
          // 取らない方
          A1 = arr.concat();
          A1.shift();
          search( A1 , sum );
      }
  }
  
  function cut( arr , sum ) {
      while ( ( arr.length > 0 ) && ( sum + arr[ arr.length - 1 ] > k ) ) {
          arr.pop();
      }
  }
  
 // 実行（中略）
 // 答えを出力（中略）

配列をコピーしまくって、数値を取るか取らないかの場合分けを行っています。合計値を計算しながら2パターンずつ試し、配列を削っていきます。

cut は「絶対に取れない大きな数値」を配列Aの上側から削除する関数。取ると sum が k を上回ってしまう場合は条件を満たせないので、そんな大きな値を消していきます。これにより考えるべき選択肢をさらに削り、計算量を減らします。

基本はそれぞれの数値を取るか取らないかを分けるだけで、総当たりと考え方は同じ。ただしこちらでは暫定の合計値を記憶しながら、取り得る数値を限定しています。選択肢を減らし解答を導きやすくすることで、計算量も現実的な数値になり、無事に正解できました。

ただ、もうちょっとスマートな解き方があるかもしれない。配列の切り取りも雑だし。配列の使い方、なかなか上手くならん。

おまけの話

実は100点のコードを出す前、得点は18点でした。そこに1行書き加えると、100点になるんですね。書き加えた行はどれでしょう？

答えは情報取得パートの、「 A.length = n 」です。

用意されている入力ケースの2行目において、最後にスペースが入っている場合、存在しないはずの A[ n ] に0が入ってしまいます。それで計算が狂って正解できなかったって訳です。最後についちゃった0を削除するために、情報を記録した配列Aの長さを n に限定する必要があったんですねー。

…いや、考え方はほぼ合ってるじゃねえかよ。20分くらい悩んだのは何だったんだ。Aに0があると狂うのかとか、JSの整数値の限界を超えたのかとか、色々考えたけど。実際はもっと原始的な話だった。

慣れているところでも確認を怠ると、恐ろしい罠にハマることがあるんですねー。これからは情報取得ももっと丁寧にしようと思った、というお話でした。