shu8Creamのブログ

競プロブログ。

ABC196に参加しました

競プロ解説

ABCで絶賛伸び悩み中なので、しっかり復習をしようという目的で解説を書いていきます。今回のABC196からだんだん遡る感じになりそうです。ブログ書きながら、新たなABCにも参加するのでブログが投稿される日時とナンバリングがぐちゃぐちゃになりそうですが、ご了承ください。灰diff下位の、よく解法ツイートで「はい」とか「やるだけ」みたいなのは端折る可能性があります。

あと、基本的にC++で書いてます。

A - Difference Max

b-cするだけ  

B - Round Down

stringで入力受け取り、頭から見ていって小数点が来たらそれ以下は捨てる

C - Doubled

問題概要

1から整数 N以下で条件を満たすものの個数を数える。 条件：偶数桁かつ文字列で見た時、前半後半が一致している

制約

1 \leq N \lt 10^{12}

解法

1. 本番で通した解法

個数が増えるのは、偶数桁の時だけなので奇数桁の時はそれ以下の偶数桁の条件を満たすものの個数全てである。

例えば、奇数桁の N=100の時、条件を満たすのは11,22,33,...,99の9個、

N=10000の時、1010,1111,1212,...,2020,2121,...,9090,9191,...9898,9999の90個、プラス上記の N=100の時の9個で合計99個

のような感じで奇数桁であれば、桁数/2個、9が並ぶ数になる。

考えなければいけないのは偶数桁の時、上記の9が並ぶ数プラスどれだけあるのかを考える。

例えば、 N = 123456の時

こんな感じで数えます。また、前半部の方が大きい場合は、ちょっとだけ変わって N = 654321の時

こんな感じで数えられます。 ソースコードは以下へ。本番中のコードなので読みづらいかも

atcoder.jp

 これの計算量は Nの桁をdigとすると[tex: O(dig2)]（これ間違ってるかも、指摘下さい）

2. 別解（全探索）

冷静に考えるとこんな複雑なことしなくていいですよね！

半分つまり[tex: N = 106]までなら全探索できるので、[tex: 106]まで一つ一つ N以下の数になるか確かめていけばいいです。本番でさっさとこれができれば…泣

ソースコードはこんな感じ

ll n;
cin >> n;
string s = to_string(n);
int dig = s.size();
ll num1 = n / (ll)pow(10,dig/2);
int ans = 0;
for(int i=1; i<=num1; i++){
    string t = to_string(i);
    t+=to_string(i); 
    if(stoll(t) <= n) ans++; 
}
cout << ans << endl;

 実装がめちゃめちゃ楽でした。計算量は O(\sqrt{N})

反省

考察し終わるまではスピーディでしたが，実装で大ポカをしました。これぐらいの実装はバグらせてもちゃちゃっと直せないといけないと思いました。目指せ緑！！

今回はここまででD, Eは改めて書こうと思います。