AtCoder Beginner Contest 198 まとめ

こんにちは。白羽(shiroha_F14)です。

今回はABC198の参戦記録を書きます。
前回がABC196なので実に1回分サボってしまいました(白目)

#総合結果
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1078419/14ef832a-74dd-a7a8-af82-ffbb50f6337f.png)

A - B(2WA) - C(1WA) - D(1WA) で初の4完を達成しました。

#この日までの精進
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1078419/905215fe-c96d-b405-bb21-64dc952151cd.png)
(Accepted -4とRated Point Sum -1000して考えてください)
緑diff 18AC および水diff 1ACです。
出来るだけdiff800↑のC,D問題に挑み、時間が無くてもStreakは繋ぎました。


#振り返り
B問題で大事故を起こしていますが、C問題は許容範囲、ABC本番中では初D問題ACでかなりの進歩だと思いました。

特にD問題は水diff(1224)で、恐ろしいことにこれを除くとこれまで水diffは1問しか解いてません。
本番で出せる実力の限界がdiff1000くらいまで来ているのは確実だと思いました。

逆に、E問題のDFSが解けなかったのは痛いです。こっちの方がdiffが低い(1161)のでBFS実装を試していた間の時間がもったいなかったという所です。

以下、解いた順に解法など。

##A問題 - 0:31 0WA
横一列に並んだ任意の物体を考え、並びの中に仕切りを入れて左右ともに1つ以上物体がある仕切りの入れ方を考えます。
すなわち入力から1を引いて出力します。

$O(1)$

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

int main(){
  int n; cin >> n;
  cout << n - 1 << endl;
}
```

##C問題 - 8:26 1WA
中途半端な位置にある点がゴールの場合も入力例2,3のように座標軸から見て同じ角度に動き続ける必要はないので、
大抵の場合において、最終地点までのユークリッド距離を$r$で割った結果を切り上げることで正答になります。

ただし入力をintで行うとゴールまでのユークリッド距離が最大で$10^{10}$なので、正しい計算になりません。
また、最終地点までのユークリッド距離が$r$より小さい時の正答は2です(一敗)。

$O(1)$

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

using ld = long double;

int main(){
  ld r, x, y; cin >> r >> x >> y;
  ld euc_dist = sqrt(pow(x, 2) + pow(y, 2));
  // euc_dist < rならば2になる
  if(euc_dist < r){
    cout << 2 << endl;
  }else{
    cout << ceil(euc_dist / r) << endl;
  }
}
```

##B問題 - 68:07 2WA
☆グ★ダ☆グ★ダ☆
###本番での解法
入力の後ろから0をカウントして同じ回数0を頭に加算してみましたが、一個だけWA。
それでチキってCに逃げ、Cが終わった後Dのコーディングをやろうとして若干上手くいかなかったのでBに戻りました。
結果としては1個ずつ追加して反転しました。最初から間に合わないはずがないんだからこのくらい愚直で良かったのに……

$O(1)$

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

int main(){
  string n; cin >> n;
  //後ろから0の連続数を確認する
  for(int i = 0; i < 10; i++){
    string ns = n;
    reverse(n.begin(), n.end());
    if(n == ns){
      cout << "Yes" << endl;
      return 0;
    }
    reverse(n.begin(), n.end());
    n = "0" + n;
  }
  cout << "No" << endl;
}
```

###最適解(pyなど反転が容易な言語を除く)
最初に大元の文字列と反転した文字をそれぞれ別の変数に用意します。(言語によってはシャローコピーに注意？)
それら二つが一致しているかを確認し、一致していなければ大元の方は先頭に、反転した方は末端に0を追加して、一致確認、を繰り返します。入力の制約より、高々10回で打ち切ってよいです。

$O(1)$

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

int main(){
  string n; cin >> n;
  string rn = n;
  reverse(rn.begin(), rn.end());
  for(int i = 0; i < 10; i++){
    if(n == rn){
      cout << "Yes" << endl;
      return 0;
    }
    n = "0" + n;
    rn += "0";
  }
  cout << "No" << endl;
}
```

##D問題 - 70:43 1WA
想定解通りだと思います。
いったん、頭から順にアルファベット1文字につき0から順に数字を1つずつ割り当てます(ここで割り当てる数字は計算用の数字ではありません)。
割り当てが11種類以上になったらその時点で```UNSOLVABLE```。
それ以外の場合は0～9の数字に対する順列全列挙をしていきます。先ほどのアルファベットに対応する数字を添字に、各順列から取り出せる値を使って計算を実際にしてみます。制約が5secなのでC++だとギリギリながらこの解法で通りました。
Javaなんかは有志ライブラリかDFSで解くしかなさそうです。

[注意点]
桁数は10ですが、順列からの数値生成中にintの範囲を超えかねませんので多倍長整数を使いましょう。

最悪計算量$10!$です。

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

using ll = long long;

int main(){
  vector<string> s(3);
  cin >> s[0] >> s[1] >> s[2];

  //数値化
  vector<vector<int>> posmp(3, vector<int>(0));
  map<string, int> usedStr; int nxt = 0;
  const string lst = "abcdefghijklmnopqrstuvwxyz";
  for(int i = 0; i < 26; i++) usedStr[lst.substr(i, 1)] = -1;
  for(int h = 0; h < 3; h++){
    for(int i = 0; i < s[h].length(); i++){
      if(usedStr[s[h].substr(i, 1)] == -1){
        usedStr[s[h].substr(i, 1)] = nxt;
        posmp[h].push_back(nxt);
        nxt++;
      }else{
        posmp[h].push_back(usedStr[s[h].substr(i, 1)]);
      }
    }
  }
  if(nxt > 10){
    cout << "UNSOLVABLE" << endl;
    return 0;
  }
  
  vector<int> perm(10);
  for(int i = 0; i < 10; i++) perm[i] = i;
  do{
    //式の生成
    vector<ll> res = {0, 0};
    for(int h = 0; h < 2; h++){
      for(int i = 0; i < s[h].length(); i++){
        res[h] += perm[posmp[h][i]] * pow(10, s[h].length() - 1 - i);
      }
    }
    ll t = 0;
    for(int i = 0; i < s[2].length(); i++){
      t += perm[posmp[2][i]] * pow(10, s[2].length() - 1 - i);
    }
    bool flg = true;
    for(int lch = 0; lch < 2; lch++){
      if(floor(log10(res[lch])) + 1 != s[lch].length()) flg = false;
    }
    if(floor(log10(t)) + 1 != s[2].length()) flg = false;
    if(res[0] + res[1] == t && res[0] > 0 && res[1] > 0 && flg){
      cout << res[0] << endl;
      cout << res[1] << endl;
      cout << t << endl;
      return 0;
    }
  }while(next_permutation(perm.begin(), perm.end()));
  cout << "UNSOLVABLE" << endl;
}
```

##E問題 4WA
ここからは本番中にはACできませんでした。
一応、可能性は見えていました。
まずは入力を無向グラフで受け取ります。
そして頂点1からの全経路を列挙しようとしてBFSで解こうとしたのですが、制約が大きめなのでTLEを起こしました。
ダイクストラなんかで処理を高速化するわけでもなさそうで悩んでいたところで時間切れになりました。
解説を見たらDFSとあって面食らいましたが、とりあえず実装できそうではあったのでUpSolve中。

[本番中一番良かったSub]
https://atcoder.jp/contests/abc198/submissions/21683712

##F問題 手つかず
**なにこれ。**
解説も3つくらい解法あるしまずもって橙diffだしなんじゃこりゃ。~~これ解けるようになる頃にはARCとかAGC出るようになってるでしょうなぁ~~

#考察
前述のとおり水diffのACはこの回まで1個だったので若干の成長はあると思いますが、実装問題だから解けたというのがあるので数理系でも安定して4完できるというのが当面の目標になります。