ABC137参戦記(A問題~C問題)

先日行われたABC137に参加したのでコンテスト中のあれこれをメモしておこうかと思います。使用言語はpython3、結果はABC3完で1961位(順位表情報)でした。コンテストへのリンクはこちら→https://atcoder.jp/contests/abc137

#A - +-x
$A + B, A - B, A \times B$を全て求めて最大値を求めれば良さそうです。提出コードはこちら。

```python:ABC137_A.py
A, B = map(int, input().split())
print(max(A+B,A-B,A*B))
```

#B - One Clue
なにやら数直線上にたくさん石が並んでるようですが、$K,X$の制約を見てみると黒石がありそうな範囲は数直線の極々真ん中のあたりのようです。端が黒石になるような場合を考える必要はなさそうです。$X$が一番右にある黒石である場合と一番左にある黒石である場合を考えると図のようになります。

<img width="1097" alt="ABC137_B解説.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/478399/8684ae6f-4eeb-75b4-0e8a-e4cc1ccbdc4d.png">

提出コードはこうなりました。

```python:ABC137_B.py
K, X = map(int, input().split())
ans = [str(i) for i in range(X-K+1, X+K)]
print(" ".join(ans))
```

#C - Green Bin
任意の二組の文字列に対して10文字全てが一致するような組が何組あるのか愚直に求めようとするととても計算が間に合いそうにありません。そこで、各文字列をソートしておき、さらにそのソートされた文字列をソートしてやることで計算量が減らせるのではないかと思いました。このようにして作ったリストSに関してS[i]とS[i+j]が同じなら入れ替えると同じ文字列になる$j+1$個の文字列がある、となります。これを満たす最大の$j$をtmpと置いて$tmp+1$個の中から二つ選ぶ組合せの総数を足し合わせていくことで答えが求められます。提出コードは以下になります。

```python:ABC137_C.py
from math import factorial
def com(n,r):
    if n<r:
        return 0
    return int(factorial(n) // factorial(r) // factorial(n-r))

N = int(input())
S = [[0 for j in range(10)] for i in range(N)]
for i in range(N):
    s = str(input())
    for j in range(10):
        S[i][j] = s[j]
    S[i].sort()
S.sort()
ans = 0
i = 0
j = 1
while i < N:
    tmp = 0
    while i + j < N and S[i] == S[i + j]:
        tmp += 1
        j += 1
    if tmp != 0:
        ans += com(tmp+1, 2)
    i += j
    j = 1
print(ans)
```
最初組合せではなく順列かと思って実装してしまいWAを一個もらいました。

組合せの計算を行う関数は以前ググって調べてスニペットに登録していました。便利です。こちらの記事が組合せに関して参考になると思います。
[【python】順列・組み合わせを計算する方法](https://www.haya-programming.com/entry/2018/04/14/185828)

#D - Summer Vacation
この問題は解くことができませんでした...が、備忘録としてコンテスト中にやっていたことを書いておきます。

最初考えたのは報酬が高く、貰えるまでの日数が長い順にソートして、M日後までに報酬が得られるようなものを全て選ぶ、と言うような方法を考え、次のようなコードを提出しました。

```python:ABC137_D.py
N, M = map(int, input().split())
l = [0 for i in range(N)]
for i in range(N):
    A,B = map(int, input().split())
    l[i] = [-B, -A]
l.sort()
ans = 0
today = 0
for i in range(N):
    if today - l[i][1] <= M:
        ans -= l[i][0]
        today += 1
print(ans)
```

結果はWAでした。例えば、
3 3
2 5
1 4
3 3
のようなケースでは３件目を今日受ける、2件目を1日後受ける、1件目を2日後受ける、のようにしたとき、3日後報酬の最大値12を得られますが、このコードでは今日1件目を受け1日後2件目を受け、3件目は受けられません。

次に考えたのはDPを使う方法です。とりあえず報酬を貰えるまでの日数が長く、高い順にソートしておいて$1, 2, ... , n, ... N$件目を受けるか、受けないかでテーブルを埋めていきます。わかりづらいですが下図のようなイメージです。

<img width="748" alt="ABC137_D解説.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/478399/03a2f60c-5615-9885-476a-d939952adfb4.png">

提出コードはこちら

```python:ABC137_D.py
N, M = map(int, input().split())
dp = [[0 for i in range(M+1)] for j in range(N+1)]
l = [0 for i in range(N)]
for i in range(N):
    A,B = map(int, input().split())
    l[i] = [-A, -B]
l.sort()
for n in range(1, N+1):
    for m in range(n):
        if -l[n-1][0]  + m <= M:
            dp[n][m] = max(dp[n][m], dp[n-1][m-1] - l[n-1][1])
        dp[n][m-1] = max(dp[n][m-1], dp[n-1][m-1])
print(max(dp[N]))
```

二重ループのせいでしょうか、PyPyで提出してもTLEとなってしまい、ダメでした...仮に時間制限をクリアできたとしてACされるのでしょうか...検証が必要そうです(分かる方いらっしゃいましたらコメントでご教授してくださると喜びます...)。

[公式の解説](https://img.atcoder.jp/abc137/editorial.pdf)では優先度付きキューを用いているようですが正直まだ優先度付きキューを使った実装の経験がなく、全然理解できていないです...要精進ですね...

#反省
今回はC問題まで通すことができました。時間配分は大体A-2分半、B-5分、C-25分という感じでした。Cをもう少し早く解きたいのとDを確実に解けるようにするのが今後の課題かなと思いました。