C++で解くセンテンス・スクリーンフィッティング：文章がスクリーンに収まる回数を求める

問題概要

rows × cols のサイズを持つスクリーンと、空でない単語からなるリストで表現された文（センテンス）が与えられます。このとき、与えられた文がスクリーン上に何回完全に収まるかを求めます。この問題には以下の条件があります。

• 単語が2行にまたがって分割されることはありません。
• 文中の単語の並び順は変更してはいけません。
• 隣接する単語の間にはスペースが1つだけ入ります。
• 文に含まれる単語の総数は100を超えません。
• 各単語の長さは1以上10未満です。
• 1 ≤ rows, cols ≤ 20,000 です。

例として、rows = 3、cols = 6、文が ["a", "bcd", "e"] である場合の出力は 2 となります。

解法の考え方

この問題は、各行の開始位置ごとに「その行に何個の単語が入るか」をキャッシュするメモ化を用いることで、効率的に解くことができます。手順は以下の通りです。

• マップ dp を用意し、ret := 0、n := 文の配列のサイズ とします。
• row が 0 でない間、以下を繰り返します。
  • start := ret mod n、len := -1、cnt := 0 と初期化します。
  • start が dp に存在しない場合は、次の処理を行います。
    • 「1 + len + sentence[(start + cnt) mod n] の長さ ≤ cols」が成り立つ間、次を繰り返します。
      • len := 1 + len + sentence[(start + cnt) mod n] の長さ と更新する。
      • cnt を 1 増やす。
    • dp[start] := cnt と記録し、ret := ret + cnt とします。
  • それ以外の場合は、すでに計算済みの値を使って ret := ret + dp[start] とします。
  • row を 1 減らします。
• 最後に ret / n を返します。

開始位置（start）ごとの結果をキャッシュしておけば、同じ開始位置が再び現れた際は O(1) で処理できるため、rows と cols が最大 20,000 に達するような大きな入力でも高速に動作します。

C++での実装例

理解を深めるために、以下の実装例をご覧ください。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        unordered_map<int, int> dp;
        int ret = 0;
        int n = sentence.size();
        while(rows--){
            int start = ret % n;
            int len = -1;
            int cnt = 0;
            if(!dp.count(start)){
                while(1 + len + (int)sentence[(start + cnt) % n].size() <= cols){
                    len = 1 + len + sentence[(start + cnt) % n].size();
                    cnt++;
                }
                dp[start] = cnt;
                ret += cnt;
            }
            else{
                ret += dp[start];
            }
        }
        return ret / n;
    }
};
main(){
    vector<string> v = {"a","bcd","e"};
    Solution ob;
    cout << (ob.wordsTyping(v, 3, 6));
}

入力

["a","bcd","e"]
3
6

出力

2