[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;
}