AtCoder ABC 174 C - Repsept (300点)
https://gyazo.com/0e5dd2ba22a4f3a79ffdb9e8979ee270
考察履歴
コンテスト中に考えたこと(筋の悪い方針)
7...7は1...1*7の数字
問題名は Repseptなので、これをもじったもののよう
入力された$ Kを素因数分解して、なんとか求められないかといろいろ考えたが駄目
7...7という数列は、とても大きい値になるので、桁数だけをうまく取得したい、と考えた。
この「ある関数に入れると答えとなる桁数を得る」、みたいな考え方が非常によくない。
結果的にそのような関数の形をとるような可能性もあるかもしれないが
この考え方は全く逐次的でない、問題を解く姿勢として誤っている
この姿勢、思考になったら要注意。筋の悪い方針に向かっている可能性がある
ということで自力では全く解答に近づけず、解説ACさせました。。。 解説pdfも私では理解できず、解説動画でようやく理解できました。
解説動画救い
解説動画からの考察/理解
1項目:7,2項目:77,3項目:777,4項目:7777,5項目:7777,...
Kの倍数となる7...7は何番目(何項目)?という問題
最初は「何項目(コウメ)」という言葉にちょっと詰まった。何項目(ナンコウモク)と読んだりもした。。
「何番目」という問い。
解答にたどり着くには、modの数学知識、感覚が必要。
7からなるものの、数字の性質について考える
おまけ
数式で、代数的に考えると、、、
$ S=7...7とすると
$ 10*S=7...70となり、両辺を引くと
$ 9*S=7...0-7となる。
例
$ S=777
$ 10*S=7770
$ 9S=7000-7(=6993)
$ S=(10^i-7)/9
この$ iの部分が答えになるらしい
漸化式で考える
$ a_{i+1} = a_i*10+7と表せる
この各$ a_iがKの倍数であるかを$ modKで考える★
例 $ K=9で考える
$ 7\%9=7, 77\%9=5, 777\%9=3, 7777\%9=1であるがこれは余りで考えても同じになる!
余りに対して、漸化式で次の項を求める
$ a'_{i+1} = (a'_i\%K)*10+7と考えると
$ 7\%9=7, 77\%9=5, 57\%9=3, 37\%9=1となり、値が$ 0 \leq a_i < Kに収まる!
そして余りの数値の遷移をグラフに表現することができる!幾何の世界へ!
ファンクショナルグラフと言ったりするよう
(ここらへんの解説聞いているとき奮えた)
https://gyazo.com/3c90291e1963cceb2e2e1dfc21c7cb8e
初期頂点から最初に$ 0へ到達するのは何番目であるか?という問題と捉えられる
また、同じ頂点に戻ってきたら、ループが発生しており、$ 0に辿り着けない
他のループ終了条件として、$ K回ループを回す、でも良い
初期値は$ a_1 = 7\%K, ans\_count = 1または$ a_1 = K, ans\_count = 0となる
以上の考察を用いることで解答となる実装ができるようになる!
解説動画が本当に丁寧で感謝しかない。
心に残った発言
「modの数学知識、感覚が必要」
「modKで考える」
「というわけでグラフの問題になりました」
「数列に綺麗な規則があると信じて考えないといけない」
「ソースコードは簡単だが、思考過程はmodの数学に慣れていないと難しい」
ACコード(写経)
code:rust
use std::io::*;
use std::str::FromStr;
use std::collections::HashSet;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
fn main() {
let k:u64 = read();
let mut s = HashSet::new();
let mut x = 7%k; //let mut x = k;
let mut i = 1; //let mut i = 0;でも良い
//重複訪問が発生したらループを抜ける
while s.contains(&x) == false {
if x == 0 {
println!("{}",i);
return;
}
s.insert(x);
x = (x*10+7)%k;
i += 1;
}
println!("-1");
}
手元のSurface Goでやると入力例3が2秒では終了しなかったが、submit先では100msオーダで完了した。