Javascriptで競技プログラミングに参加してみた2

Javascriptで競技プログラミングに参加してみた2 | GUARDIAN Creative BLOG | 株式会社ガーディアン｜141億のデータで中小企業を勝たせるWEB戦略データ・カンパニー | 株式会社ガーディアン｜141億のデータで中小企業を勝たせるWEB戦略データ・カンパニー

2022/11/22

GUARDIAN Creative BLOG

前回の記事の続きです。

さて前回の記事にて書いた通り、アルゴリズム初心者のワタシがLeetcodeのプログラミングコンテストに参加したところ

4問中最も易しいEasyの１問しか解けず残りは問題文の意味を理解することで精一杯だったというのが前回までのあらすじです(´・ω・`)

下記がそのときのコンテストにおけるNormalレベル問題です。

2466. Count Ways To Build Good Strings

Integer型のzero, one, low,highが与えられた時、空の文字列から始まり以下のステップで文字列を構成していきます。
文字'0'をzero回追加する。
文字'1'をone回追加する。
これらの手順は何度でも行うことができるものとします。
上記の処理によって作られた文字列のうち、長さがlowからhighの間のものを「良い文字列」と呼ぶものとします。
これらの性質を満たす良い文字列を何通り作ることができるかを、返り値として返しなさい。ただし答えがとても大きくなる可能性があるので、その量を1000000007 で割ったあまりを求めること。

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
条件を満たす文字列のひとつとして "011" があります。 
これは次のように構成することができます。 : "" -> "0" -> "01" -> "011". 
この例では、二進数の"000"から"111"までのすべての値が「良い文字列」となります。

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: 「良い文字列」は "00", "11", "000", "110", 及び "011" です。

（いずれも筆者訳）

( °᷄д°᷅) ・・・

(つд⊂)ｺﾞｼｺﾞｼ

（；ﾟДﾟ）…？！

ナニイッテルカワカラナイ・・・

問題文の意味をなんとか読み解こうと色々調べた結果、腹落ちするまで45分もの時間がかかってしまいました(^^;

そんなこんなで問題文を読み解こうと四苦八苦しているうちに、どうやら「ただし答えがとても大きくなる可能性があるので、その量を1000000007 で割ったあまりを求めよ。」という部分は競技プログラミングお決まりの文句のようだと気づきました。

このあたり、競プロ特有の言い回しや発想の仕方があるため、慣れるにはとにかくひたすら問題を解く練習をする必要がありそうです。

幸いLeetcodeには過去のコンテストの問題や、カリキュラムが豊富にあるので解く問題には困りません。

回答例

コンテスト終了後、他の参加者の方々のコードを見るとだいだい以下のような感じで解かれているものが多かったです。

var countGoodStrings = function(low, high, zero, one) {
  let answer = 0;
  const dp = Array(high + 1).fill(0);
  dp[0] = 1;
  for(let i = 1; i <= high; i++) {
    if(i >= zero) {
      dp[i] += dp[i - zero];
    }
    if( i >= one) {
      dp[i] += dp[i - one];
    }
    dp[i] %= 10**9 + 7;
    if(i >= low) {
      answer = (answer + dp[i]) % (10**9 + 7);
    }

  }  
  return answer;    
};