ABC-C第12弾

![result.png](https://qiita-image-store.s3.amazonaws.com/0/218584/6ae8617d-b841-022e-34c6-c69db46e01b8.png)




- [バチャ12弾](https://not-522.appspot.com/contest/5785629791092736)
- Sequenceよく分んないけどいずれ書く





# ABC056 「[Go Home](https://beta.atcoder.jp/contests/abc056/tasks/arc070_a)」

## 考察と解法

- なにもしないかジャンプするかを選べるが、毎回ジャンプするのが最適。
- $\frac{1}{2}n(n+1)=10^9$を適当に変形すると$n=\sqrt{10^9}$になるので計算は普通に間に合う（と思う



## [コード](https://beta.atcoder.jp/contests/abc056/submissions/2417012)

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
   ll x;
   cin >> x;
   ll y = 0;
   for (int i = 0;  ; i++) {
      y += i;
      if (y >= x) {
         cout << i << endl;
         return 0;
      }
   }

   return 0;
}
```



## 感想

- やけに簡単だなーって思ったら200点だった



# ABC057 「[Digits in Multiplication](https://beta.atcoder.jp/contests/abc057/tasks/abc057_c)」

## 考察

- なんか問題文が複雑なので整理する
  - $F(A, B)$はA, B桁数が大きい方の桁数を返す
  - $N=AB$となる組み合わせのうち、$F(A ,B)$の最小値はいくつになるか？
- $A, B$の組み合わせを全列挙すると$O(N^2)$になるのでだめ
- $A$を決めたとき、$N=AB$より、$B=\frac{N}{A}$となる（NがAで割り切れる場合に限る）。なので、$O(N)$で$A, B$の組み合わせを列挙できる。ただ、これじゃまだ間に合わないのでもう少し工夫する
- N=6のとき、(2, 3)と(3, 2)を候補に挙げるのは無駄である。なぜならF(2, 3)とF(3, 2)は同じ結果だから。(2, 3)だけを挙げれば十分である。
- ここで、$A\leq B$になるように候補を挙げれば良いことに気がつく。そのためには、$1 \leq A \leq \sqrt{N}$の範囲で探索すれば良いことが分る。$A$を$\sqrt{N}$より大きくすると、$A$が$B$の値を超えてしまう。
- 例えば、$N=36$のときの$A,B$の組み合わせは以下のようになる。これをみると、$A$が$\sqrt{N}$を超えたら$N=AB (A\leq B)$が成り立たなくなることが分る。

<img width="685" alt="comb.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/73f7cf73-8d60-4736-c3b4-59d8e2583c4c.png">


## 解法

- $A(1 \leq A \leq \sqrt{N})$についてのループを回す。そのとき、$B=\frac{N}{A}$で求めることができる（ただし、$N$が$A$で割り切れるときのみ）。
- 後は、$F(A, B)$を実装して返ってくる値の最小値を更新すれば良い



## [コード](https://beta.atcoder.jp/contests/abc057/submissions/2417684)

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll N;

ll digit(ll x) {
   ll ret = 0;
   while (x > 0) {
      ret++;
      x /= 10;
   }
   return ret;
}

ll F(ll A, ll B) {
   return max(digit(A), digit(B));
}

int main() {
   cin >> N;
   ll ans = 1e18;
   for (ll a = 1; a*a <= N; a++) {
      if (N % a == 0) {
         ans = min(ans, F(a, N/a));
      }
   }
   cout << ans << endl;

   return 0;
}
```



## 感想

- **$N=AB(A\leq B)$となるようなペアを挙げるとき、$1 \leq A \leq \sqrt{N}$の範囲で探索すれば良い**ことを知っていたため解けた。かけて$N$になるようなペアを持ってくるには$A$は$\sqrt{N}$以下でないといけないですよねという話。なんかまだモヤモヤする...N=36のときにはAを6になるまで探索すればいいとか気持ち悪くないですか？え？？ってなりません？？
- ちなみに、Multiplicationはかけ算って意味らしい（初めて知った



# ABC058 「[怪文書 / Dubious Document](https://beta.atcoder.jp/contests/abc058/tasks/arc071_a)」

## 考察と解法

- 例えば、全ての文字列において`a`が出てくる最小回数を求める。その回数が答えに`a`が出てくる回数となる。これを`a`～`z`全てについて調べれば良い



## [コード](https://beta.atcoder.jp/contests/abc058/submissions/2417748)

```cpp
#include <bits/stdc++.h>
using namespace std;

int a[30]; // a[i]: char('a'+i)が何個あるかの決定版
int b[30]; // b[i]: char('a'+i)が何個あるかの一時的な配列

int main() {
   fill(a, a+26, 1e5);

   int n;
   cin >> n;
   while (n--) {
      string s;
      cin >> s;
      fill(b, b+26, 0);
      for (char c : s) {
         b[c-'a']++;
      }
      for (int i = 0; i < 26; i++) {
         a[i] = min(a[i], b[i]);
      }
   }

   string ans = "";
   for (int i = 0; i < 26; i++) {
      ans += string(a[i], 'a'+i);
   }
   cout << ans << endl;

   return 0;
}
```

- コンテスト中は[こんなコード](https://beta.atcoder.jp/contests/abc058/submissions/2406949)で通したが、2次元配列はなんかわかりにくいので一次元で書いてみた。



# ABC059 「[Sequence](https://beta.atcoder.jp/contests/abc059/tasks/arc072_a)」

- これよく分らん
- 解説読んだら自明な気がするけど、よくよく考えたらそんなに自明でもない
- 飛ばします。

## 実装

- 僕がコードを書いたら[こんな感じ](https://beta.atcoder.jp/contests/abc059/submissions/2419794)。
- 汚すぎるけどリファクタリングするの大変...



# ABC060 「[Sentou](https://beta.atcoder.jp/contests/abc060/tasks/arc073_a)」

## 考察

- 1回の操作で足される最大値は$T$である。
- 区間がかぶったときは足される値が$T$より小さくなる。
- 結局考えられるのは以下の2パターンとなる。
- 最後の区間は`t[i+1]`を参照できない。必ず$T$が足される。

<img width="371" alt="kukan.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/00af4701-9ab7-daae-a072-1af80d72fdd1.png">


## 解法

- $0\leq i \leq N-1$の範囲で$min(t[i+1]-t[i], T)$を取っていく。
- 最後の区間は$T$を足す



## [コード](https://beta.atcoder.jp/contests/abc060/submissions/2419668)

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll N, T;
ll t[222222];

int main() {
   cin >> N >> T;
   for (int i = 0; i < N; i++) {
      cin >> t[i];
   }
   
   ll ans = 0;
   for (int i = 0; i < N-1; i++) {
      ans += min(t[i+1] - t[i], T);
   }
   ans += T;

   cout << ans << endl;

   return 0;
}
```



## 感想とか

- **1回の操作で足される最大値は何か？という思考ができたらその後の考察が少し楽になったと思う**
- $min(t[i+1]-t[i], T)$について
  - $t[i+1]-t[i]$は、次の区間に突入したらそこで打ち切るイメージ。
  - $T$は次の区間に突入しない時
- つまり、1回の操作で足される最大値が$T$という発想より、現在地点から$T$以内について考える。現在地点+Tが次の区間とかぶったときは、現在地点から延びる線を打ち切って次の区間に託すというイメージ。