ABC051 B - Sum of Three Integers - ペンギンかっこいい

備忘録

問題

回答

"use strict"
function Main(input) {
  input = input.trim().split(' ').map(Number);
  const k = input[0];
  const s = input[1];
 
  let ret=0;
  for(let x=0; x<=k; ++x){
    for(let y=0; y<=k; ++y){
      let z = s-x-y;
      if(0<=z&&z<=k) ++ret;
    }
  }
  console.log(ret);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

全パターン算出して条件を満たす値の個数を数えるだけ。
しかし、下記のように単純な3重のforループは制限時間を超過する。

// bad
  for(let x=0; x<=k; ++x){
    for(let y=0; y<=k; ++y){
      for(let z=0; z<=k; ++z){
        if(x+y+z===s) ++ret;
      }
    }
  }

xとyの値が決まった時、zは自動的に決まる(s-x-y)ので、算出されたzが
条件の範囲内に収まっているか否かを判定することで、forループを2重にすることが出来る。

3重のforループは全ケース計算する場合、10,000,000,000パターンを超えるが、
2重のforループであれば、6,000,000パターン程度なので、余裕で時間内に処理が終わる。

各言語の1秒間のループ回数を計測した記事各言語の1秒間のループ回数 - Qiita

言語によって1秒間で行えるループ数は区々だが、
目安として、だいたい1秒で10^8回らしい。