ABC275参戦記(A-F)

AtCoder Beginner Contest 275の参戦記です。
個人的な精進の記録として書きます。
初の6完だったので嬉しくて書きました。

https://atcoder.jp/contests/abc275

# A - Find Takahashi
https://atcoder.jp/contests/abc275/tasks/abc275_a

**考察**
Hの最大値のindexを取ればOK


**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
def main():
    N = int(input())
    H = list(map(int, input().split()))
    idx = H.index(max(H))
    print(idx + 1)
```

</div></details>

# B - ABC-DEF
https://atcoder.jp/contests/abc275/tasks/abc275_b

**考察**
C++だったら毎回modで割らないといけないけど、pythonだったらそのままでよさげ

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
def main():
    A, B, C, D, E, F = map(int,input().split())
    ans = A * B * C % mod2
    ans -= D * E * F % mod2
    ans %= mod2
    print(ans)
```

</div></details>

# C - Counting Squares
https://atcoder.jp/contests/abc275/tasks/abc275_c

**考察**
斜めの正方形めんどくさくね？
原点周りの回転を求めるrotate関数あるからそれ使って、2点全探索したあと反時計回りに残りの2点決めたらいいか。
同じ正方形は4回数えるから最後に4で割ろう。

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
def rotate(p, theta):
    x, y = p
    ret = [0, 0]
    ret[0] = x * math.cos(theta) - y * math.sin(theta)
    ret[1] = x * math.sin(theta) + y * math.cos(theta)
    ret[0] = round(ret[0])
    ret[1] = round(ret[1])
    return ret


def main():
    S = [input() for _ in range(9)]
    ans = 0

    for i in range(9):
        for j in range(9):
            if S[i][j] != "#":
                continue
            for k in range(9):
                for l in range(9):
                    if S[k][l] != "#":
                        continue
                    if i == k and j == l:
                        continue
                    m, n = rotate((k - i, l - j), math.radians(-90))
                    m += i
                    n += j
                    if m < 0 or 9 <= m or n < 0 or 9 <= n:
                        continue
                    o, p = rotate((i - k, j - l), math.radians(90))
                    o += k
                    p += l
                    if o < 0 or 9 <= o or p < 0 or 9 <= p:
                        continue
                    if S[m][n] == S[o][p] == "#":
                        ans += 1
    print(ans // 4)
```

</div></details>

# D - Yet Another Recursive Function
https://atcoder.jp/contests/abc275/tasks/abc275_d

**考察**
・・・メモ化再帰？

**コード**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
def main():
    memo = {}
    memo[0] = 1

    def f(x):
        if x in memo:
            return memo[x]
        ret = f(x // 2) + f(x // 3)
        memo[x] = ret
        return ret

    N = int(input())
    print(f(N))
```

</div></details>

# E - Sugoroku 4
https://atcoder.jp/contests/abc275/tasks/abc275_e

**考察**
DPだな。
```dp[i][j]```:i回ルーレットを回したときのjにいる確率
として計算すれば行けそう。確率はMで割る代わりにMの逆元かければOK。
Nについたときにそれ以降進める必要はないから、jは0～N-1で回して最後に全部足そう。

**コード**

<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
#!/usr/bin/env python3
dpos4 = ((1, 0), (0, 1), (-1, 0), (0, -1))
dpos8 = ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1))
mod1 = 10**9 + 7
mod2 = 998244353
from math import inf


def main():
    N, M, K = map(int, input().split())

    # i回回したときにjにいる確率
    dp = [[0] * (N + 1) for _ in range(K + 1)]
    dp[0][0] = 1

    mod_inv = pow(M, mod2 - 2, mod2)
    for i in range(K):
        for j in range(N):
            for k in range(1, M + 1):
                if j + k <= N:
                    dp[i + 1][j + k] += dp[i][j] * mod_inv % mod2
                    dp[i + 1][j + k] %= mod2
                else:
                    dp[i + 1][N - (j + k - N)] += dp[i][j] * mod_inv % mod2
                    dp[i + 1][N - (j + k - N)] %= mod2
    ans = 0
    for i in range(K + 1):
        ans += dp[i][N]
        ans %= mod2
    print(ans)

if __name__ == "__main__":
    main()
```

</div></details>

# F - Erase Subarrays
https://atcoder.jp/contests/abc275/tasks/abc275_f

**考察**
Aの要素を使ってできる数値は
```dp[i][j]```:i番目までを使ってjができるかどうか。中身はbool
でできるからこれ使ってできないかな。
・・・boolじゃなくて操作回数を入れればいいんじゃない？
操作回数が増えるのってi-1番目の要素を使っててi番目の要素を使わないときにしか増えないような気がする
ということで
```dp[i][j][k]```:i番目まで使ってjができるとき（k=0:i番目を使わない k=1:i番目を使う）の操作回数

**初期化**
```python
dp[0][0][1] = 0
```

計算量は```3000*3000*2*4```くらいなんだからPypyで出せば通るやろ。

**コード**

<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```python
#!/usr/bin/env python3
dpos4 = ((1, 0), (0, 1), (-1, 0), (0, -1))
dpos8 = ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1))
mod1 = 10**9 + 7
mod2 = 998244353
from math import inf


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    # i番目まででjができたときの操作回数
    dp = [[[inf] * 2 for _ in range(M + 1)] for _ in range(N + 1)]
    dp[0][0][1] = 0
    
    ans = [inf] * (M + 1)
    for i in range(N):
        a = A[i]
        for j in range(M + 1):
            if dp[i][j][0] != inf:
                dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][0])
                if j + a <= M:
                    dp[i + 1][j + a][1] = min(dp[i + 1][j + a][1], dp[i][j][0])

            if dp[i][j][1] != inf:
                dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][1] + 1)
                if j + a <= M:
                    dp[i + 1][j + a][1] = min(dp[i + 1][j + a][1], dp[i][j][1])
    for i in range(1, M + 1):
        ans = min(dp[-1][i])
        if ans == inf:
            ans = -1
        print(ans)


if __name__ == "__main__":
    main()
```

</div></details>

**結果**
TLE
いけると思ったけど甘かった。
枝刈りとかちゃんとすれば通るんだろうけどわからんからC++で書き直すか・・・

**コード(C++)**
<details><summary>ソースコードを表示（折りたたみ）</summary><div>

```C++
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// using namespace atcoder;
using ll = long long;
const ll MOD1 = 1000000007LL;
const ll MOD2 = 998244353LL;
using namespace std;
const vector<pair<int, int>> dpos4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// const vector<pair<int, int>> dpos8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
template <typename T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;  // aをbで更新
        return true;
    }
    return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;  // aをbで更新
        return true;
    }
    return false;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(M + 1, vector<ll>(2, 1e18)));
    dp[0][0][0] = 1;
    dp[0][0][1] = 0;

    for(int i = 0; i < N; i++){
        int a = A[i];
        for(int j = 0; j <= M; j++){
            chmin(dp[i + 1][j][0], dp[i][j][0]);
            chmin(dp[i + 1][j][0], dp[i][j][1] + 1);

            if(j + a <= M){
                chmin(dp[i + 1][j + a][1], dp[i][j][0]);
                chmin(dp[i + 1][j + a][1], dp[i][j][1]);
            }
        }
    }
    for(int i = 1; i <= M; i++){
        ll ans = min(dp[N][i][0], dp[N][i][1]);
        if(ans >= 100000) ans = -1;
        cout << ans << '\n';
    }
	return 0;
}
```

</div></details>

**結果**
無事AC

# コンテスト結果

https://atcoder.jp/users/lazylazy/history/share/abc275

# 感想

Cの実装めんどくさいからDよりDif高そう。
EのDPは典型的なDPで逆元知ってるかどうかが問題な気がする。
Fの考察できちんとDPかけたのがだいぶ嬉しい。
そして初の6完。
枕を高くして眠れそうです。