AtCoder参加したったー（ABC193編）

こんにちは！バイオインフォマティクス系オタク修士学生のroadricefieldです！AtCoder ABC193参加しました！  

# [A問題](https://atcoder.jp/contests/abc193/tasks/abc193_a)  

何円安くなっているかを引き算で計算してそれが定価の何％に当たるか計算して出力すればいいですね．「割合」は小学5年生の算数で習います．  

（私の解答）

```python
A, B = map(int, input().split())
print(((A-B)/A)*100)
```  

# [B問題](https://atcoder.jp/contests/abc193/tasks/abc193_b)  

まず問題設定より，*A<sub>i</sub>*が*X<sub>i</sub>*以上である店*i*では，高橋くんがその店にたどり着いたときにはスヌケマシンは売り切れてしまっています．このことに気をつけてすべての店についてスヌケマシンを買えるのか，買えるのであれば価格はいくらなのかを調べて最安値を出力すればいいです．  

（私の解答）  

```python

N = int(input())

ans = 10000000000

for _ in range(N):
  A, P, X = map(int, input().split())
  if A >= X: continue
  if P < ans: ans = P

if ans != 10000000000: print(ans)
else: print(-1)
```  

私の解答ではどこの店でもスヌケマシンが買えない場合は`ans`が最後に`10000000000`のままとなっていますのでそのようなときは`-1`を出力するように書いています．  

# [C問題](https://atcoder.jp/contests/abc193/tasks/abc193_c)  

変数`ans`を*N*として，*a<sup>b</sup>*と表すことのできる数を列挙していって*N*よりも小さいかどうかを判定していき，小さいならば順次`ans`から1を引いていって，*a<sup>b</sup>*が*N*よりも大きくなってしまったところで処理を終了してその時の`ans`を出力するという方針で解きました．  

問題は「*a<sup>b</sup>*と表すことのできる数を列挙」をどのように実現するかです．*a*, *b*それぞれ2からスタートして1ずつ増やしながら列挙していけばよいでしょう．しかし，そのままやると途中で重複が起きてしまいます．たとえば*a* = 2, *b* = 4 のとき*a<sup>b</sup>* = 16ですが*a* = 4, *b* = 2のときも*a<sup>b</sup>* = 16です．これに気をつけなければなりません．と，いうわけで一度出現した数を記録しておいて一度現れた数は飛ばしながら処理をすすめることにしましょう．*a*に代入する数がすでに出現している場合は*b*がどんな数でも*a<sup>b</sup>*はすでに出現していることを利用するなどして以下のように書きました．  

（私の解答）  

```python

N = int(input())

ans = N
done = set()

for i in range(2,10**5+5):
  if i**2 > N: break
  if i in done: continue
  j = 2
  while 1:
    if i**j > N: break
    else:
      done.add(i**j)
      ans -= 1
      j += 1

print(ans)

```  

*a<sup>b</sup>*で表せる数がさほど多くないので普通に間に合います．  

# [D問題](https://atcoder.jp/contests/abc193/tasks/abc193_d)  

これは高校の数学Aの確率ですね完全に．高橋くんと青木くんの裏向きのカードの組み合わせとしてあり得るすべての場合の数，(9*K*-8)(9*K*-9)で高橋くんが勝つ組み合わせの数を割ればいいです．ここで数字が同じ2枚のカードは異なるものとして扱わなければなりませんね．  

まず最初に1~9のカードがそれぞれ何枚が表向きに場に出ていないカードとして残っているかを計算しておいて，それに気をつけながら高橋くん，青木くんの裏側のカードの数字のすべての組み合わせ（9 × 9 = 81通り）についてそれぞれ検討していきます．気をつけることとしては例えば高橋くんと青木くんの裏向きになっているカードの数が同じである場合を検討するとき，そもそもその数字のカードが表向きでないものとして2枚以上残っていなければそのような場合は存在しないことになります．高橋くんが勝つ数字の組み合わせとなる場合の数を計算していってその総和を(9*K*-8)(9*K*-9)で割ったものが答えになりますね．  

（私の解答）  

```python  

K = int(input())
S = input()
S = list(map(int, list(S[:4])))
T = input()
T = list(map(int, list(T[:4])))
ST = S + T

left_card = [K]*9

for i in range(1,10): left_card[i-1] -= ST.count(i)

bumbo = (9*K - 8)*(9*K - 9)
bunshi = 0

for i in range(1,10):
  if left_card[i-1] == 0: continue
  for j in range(1,10):
    if left_card[j-1] == 0: continue
    S.append(i)
    T.append(j)
    Takahashi = 0
    Aoki = 0
    for k in range(1,10):
      Takahashi += k*(10**S.count(k))
      Aoki += k*(10**T.count(k))
    if Takahashi > Aoki:
      if i == j and left_card[i-1] == 1:
        pass
      elif i == j and left_card[i-1] != 1:
        bunshi += left_card[i-1]*(left_card[i-1]-1)
      else:
        bunshi += left_card[i-1]*left_card[j-1]
    S = S[:4]
    T = T[:4]

print(bunshi/bumbo)
```  

今回はアルゴリズムの力というか思い通りの処理を実装する力が問われるような問題でしたね（D問題までは）．て，いうかAtCoderってすごく難しくてやっとD問題まで安定して解けるようになってきた～と思ったら次に待ち受けるのはDよりはるかに難しいE問題ですからね！？時間足りひん！！Eを解けるようになるにはA~Dを解き切る時間を超大幅に短縮する鍛錬を積むか，解けるはずのC,D問題を後回しにしてEに果敢に立ち向かうかしかないですね......