参加日記: AtCoder ABC 251 AからE

https://atcoder.jp/contests/abc251/tasks

# A - Six Characters

## 解法1
入力の文字数が少ないので、Pythonであれば、str()*nでその文字列が$n$回繰り返した文字列が生成され、str()[:6]で先頭から6文字を切り出せることを考え以下のように解けます。
```Python
s = input()
print((s*6)[:6])
```

## 解法2:
別の言い方にしてみると、$S$を1文字目から順に表示していき、最後の文字を出力したら、また最初の文字に戻ればよいです。0-indexedで考え、文字数でmodを取るとこれを実現できます。このため、以下のように解くこともできます。

```Python
s = input()
for i in range(6):
    print(s[i % len(s)], end="")
print()
```

https://atcoder.jp/contests/abc251/submissions/31749052


# B - At Most 3 (Judge ver.)

重りの数が$300$と小さいので、$1,2,3$個取ったときの重さの和を全探索すればよいです。結果はset()などに入れておけば、重さの種類を簡単に求められます。
Pythonであれば、itertools.combinations(dat, k)で、$dat$の配列から要素を$k$個選ぶことを全列挙できます。これを活用して実装します。

<details><summary>実装(Python)</summary><div>

```Python
from itertools import combinations
n, w = map(int, input().split())
dat = list(map(int, input().split()))
ans = set() # 結果の種類数
for cnt in (1,2,3): # 1,2,3個選んだ時
    for selected in combinations(dat, cnt): # datの値をcnt個選ぶ全ての組み合わせ
        # ここで、selectedには(3,6,10)や(1,2)や(4)のようにcnt個の重さの値が入っている
        if sum(selected) <= w: # なので、その和がw以下なら
            ans.add(sum(selected)) # その和を重さの種類としてsetに淹れる
print(len(ans)) # で、種類数を表示してやれば良い
```
</div></details>

https://atcoder.jp/contests/abc251/submissions/31749250

# C - Poem Online Judge 
- sが既に出てきた文字列なら無視します
- tが大きい順に取り出したいです
- tが同値なら、index番号が小さいものを取り出したいです

ということをしたいです。今、もしも、sに重複がないのであれば、`(-t, index)`が入った配列を昇順にソートして一番最初の要素のindexが答えであることは2,3個目のしたいことから自明です。`-t`としているのは、tが大きいものを最初に持ってきたいためです。

sが重複しないようにこのようなデータの配列を作るのには、sが出現したかをset()などで管理して読み込めばよいです。

<details><summary>実装(Python)</summary><div>

```Python
n = int(input())
dat = list()
known = set() # sを管理するリスト
for i in range(n):
    s, t = input().split()
    if s in known: continue # sが既に出現したならスキップ
    known.add(s) # sを処理したと記録
    dat.append( (-int(t), i+1) ) # (-t, index)を作る
dat.sort() # ソートして
print(dat[0][1]) # 頭のindexを出力
```
</div></details>

https://atcoder.jp/contests/abc251/submissions/31749500

# 【割愛】D - At Most 3 (Contestant ver.)
解説の通りです。100進数...

https://atcoder.jp/contests/abc251/editorial/3958


# E - Takahashi and Animals
この問題は巡回が発生するのが厄介です。つまり、動物Nに餌をやると動物1にも餌が与えられます。

この問題は、巡回がなければとてもシンプルな問題です。$dp[i]$を`少なくとも`動物$i$まで餌をやり切っているときの最小コスト。と考えます。すると以下のように考えられます。もし、`●`までコストが決まっているとしましょう。
<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/8a2e42e2-bbd0-5350-b7e3-e8f2b97a3400.jpeg width=50%>
- パターン1: $i-2$までが決まっていて、$i-1$に餌をやる(と$i$まで餌が届く)
- パターン2: $i-1$までが決まっていて、$i-1$に餌をやる(と$i$まで餌が届く)
- パターン3: $i-1$までが決まっていて、$i$に餌をやる(と$i+1$まで餌が届くが、$i$までとしてもいい)

これをDPで解いていけば、$dp[n]$が答えです。

さて、巡回が存在するときはこのままではWAになります。というのも、巡回がない状態では動物1に餌をやるには動物1に餌をやるしかないですが、巡回がある状態では動物Nに餌をやっても動物1に餌をやれるからです。

解説の通り、この問題は動物1に餌をあげる状態が、`動物1に餌をやったとき`と`動物Nに餌をやったとき`の２つからスタートすればよいです。どのようにその２つをシミュレートするかというと、入力をローテートしてやり、この状態にしてやれば、同じコードで流用できます。

<details><summary>実装(Python)</summary><div>

```Python
n = int(input())
indat = list(map(int, input().split()))
def func(dat):
    # この関数は「巡回がないとして」動物1 (dat[0])に餌をやったときの動物Nまで餌をやるのに最小のコストを計算する
    ans = [1<<61] * n
    ans[0] = dat[0] # 動物1に餌をやった
    ans[1] = dat[0] # 動物1に餌をやった(ので、動物2まで届く)
    for i in range(2, n): # その先をシミュレート
        ans[i] = min(ans[i], ans[i - 2] + dat[i - 1])  # Pat1
        ans[i] = min(ans[i], ans[i - 1] + dat[i - 1])  # Pat2
        ans[i] = min(ans[i], ans[i - 1] + dat[i])      # Pat3
    return ans[n-1] # 最後まで餌をやるのにかかるコスト
ans1 = func(indat) # 初期状態のコスト
import collections
indat = collections.deque(indat)
indat.rotate(1) # 初期状態を一個ローテート [1,2,3] -> [2,3,1]にする
ans2 = func(list(indat)) # またDP計算。これは実質、動物Nに餌を挙げることで動物1に餌をあげたパターン
print(min(ans1, ans2)) # その最小が答
```
</div></details>

https://atcoder.jp/contests/abc251/submissions/31751104