[ARC129] C - Multiple of 7

[Q] https://atcoder.jp/contests/arc129/tasks/arc129_c
1. 7で割れる組み合わせ数を稼ぐには、"777...777"を作ればいい。nC2通りの組み合わせが作れる。
2. nC2を作ってNを消費させる。Nがまだ残っているなら、いったん7以外の文字で区切って、再度"777...777"を作る。
これを繰り返せば、効率よく解答文字列を作れそう。
3. ダミー文字を何にしよう？(3WA)

Q. 20
20をどんどん削っていく。
1) 6C2 = 15
ans = "777777" // "7" を6文字付与。
N -= 15 // 5

ダミー文字 "1" を付与。
ans = "7777771"

2) 3C2 = 3 // "7" を3文字付与。
ans = "777771777"
ans -= 3 // 2

ダミー文字 "2" を付与。
ans = "7777717772"

3) 2C2 = 1 // "7" を 1文字付与
ans = "77777177727"

ダミー文字 "6" を付与。
ans = "777771777276"

4) 2C2 = 1 // "7" を 1文字付与
ans -= 1 // 0

ans = "7777717772767"

Q. ダミー文字？
A. 7以外の値を挿入して7の連結を切りつつ、新たに7の倍数を生まない値を指定しないといけない。

もしどこかで 1 をダミーとした場合。

・2桁目を考える。
1x が 7 で割れてはいけない。
14 がダメ。

(10+x)%7 == (3+x)%7

・3桁目を考える。
10x が 7で割れてはいけない。
(100+x)%7 = (2+x)%7
なので、
105 がダメ。

1xxxxx
 4がダメ
  5がダメ
   ...
として、桁ごとに、NG値 を更新する必要がある。

Q, 何文字くらいダミー文字はくる？
A. せいぜい4文字くらいかも

Q. 1000000
A. 
1000000
-> 1009
-> 19
-> 4
-> 1
ans
= 77777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777717777777777777777777777777777777777777777777727777737767

ダミー文字は4文字。

Q. ダミー文字の選び方によっては、1~6のダミー選択肢が早く消滅してしまう？
A. 1文字置くごとにNG文字が１つずつ増えるので、どれを置いても変わらない。ダミー文字は6文字までしか置けない。けど6文字までで十分。

Q. ダミー1,2を使っていて、
1727x
という状況が来た場合。

xには、
(10200+x)%7 != 0 // 1+x
(200+x)%7 != 0   // 4+x
を満たすxならなんでもいい。

すでに 1,4 がng値として設定されている。
x = 3,6 がダメ。(7-1=6, 7-4=3)

・x=1を選んだ場合
1自身
1+1=2
1+4=5
1,2,5 が 新たな ng ケース。

・x=2を選んだ場合
2自身
2+1=3
2+4=6
2,3,6 が 新たな ng ケース。

・x=4を選んだ場合
4自身
4+1=5
4+4=8%7 = 1
1,4,5 が 新たな ng ケース。

・x=5を選んだ場合
5自身
5+1=6
5+4=9%7 = 2
2,5,6 が 新たな ng ケース。

どれを選んでもバリエーションの増加量は変わらないので、とりあえず1を置く。

実装

void zurashi(bool ng[7]){
 bool nng[7]{};
 rep(k, 7){ // 桁ずらし
   if (ng[k]){
     ll kk=k;
     (kk*=10)%=7;
     nng[kk] = true;
   }
 }
 rep(k, 7) ng[k] = nng[k];
}

int main(){
 cincout();
 
 ll N;
 cin >> N;
 
 ll n=N;
 string ans;
 bool ng[7]{};

 while(n > 0){
   ll bi=sqrt(n*2); // kC2をみたすkは、rootの近くにある
   bi+=2;
   while (bi*(bi+1)/2 > n) --bi;
   rep(i, bi){
     ans += '7';
     zurashi(ng); // 桁ずらし
   }
   n -= bi*(bi+1)/2;

   if (n>0){ // ダミー文字挿入
     zurashi(ng); // ダミー文字が入ると、もう1桁ずれる
     for(ll j=1; j<=6; ++j){ // jを挿入すると仮定
       if (ng[7-j]) continue;
       bool nng[7]{}; // 次のngいれ
       rep(x, 7) nng[(x+j)%7] = ng[x];
       nng[j] = true;

       rep(x, 7) ng[x] = nng[x]; // 新しいng
       ans += '0'+ j;
       break; // 1個見つかったらおしまい
     }
   }
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/arc129/submissions/27439729