【AtCoder】ABC227をPython3で解説（ABCD）

ABC227のA-D問題の解説。

https://atcoder.jp/contests/abc227

## 目次
[A - Last Card](#a---last-card)
[B - KEYENCE building](#b---keyence-building)
[C - ABC conjecture](#c---abc-conjecture)
[D - Project Planning](#d---project-planning)

## A - Last Card

https://atcoder.jp/contests/abc227/tasks/abc227_a

### 解説

`A`番目の人から`N`人に`K`枚のカードを配るとき、最後のカードは誰に配れるかという問題。

回答としては、`A`番目と`K`枚のカードの和から1を引いた値を`N`で割ったあまりを出力すれば良い。このとき、あまりが0になったとき、これはカードを配りきれたということなので、`N`を出力させるようにする。

![IMG_0847.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/d3828c99-db50-05bd-d509-faeab5093391.jpeg)

![IMG_0848.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/365072ea-2fc9-dd4c-1b49-a0a2058cd3bb.jpeg)

### コード
```python
def main():
    n, k, a = map(int, input().split())

    ans = (a + k - 1) % n 
    if ans == 0:
        ans = n

    print(ans)

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

## B - KEYENCE building

https://atcoder.jp/contests/abc227/tasks/abc227_b

### 解説

この問題を簡単に言うと、任意の非負整数(1, 2, ...)$a, b$を用いて、式$4ab + 3a + 3b$で求められる解がある。入力された$S_i$について、この解に当てはまらないものはいくつあるかを求める問題。

解き方については以下の通りである。

![IMG_0849.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/ded221be-d840-bd25-0ad0-e7580d463730.jpeg)


### コード
```python
def main():
    n = int(input())
    slist = list(map(int, input().split()))

    check = set() # 4*i*j + 3*i + 3*jの解の保存場所

    for i in range(1, 1001):
        for j in range(1, 1001):
            test = 4*i*j + 3*i + 3*j
            if test > 1000: # 値が1000を超えたらループを抜ける
                break

            check.add(test) # 値をチェックリストに追加

    cnt = 0

    for s in slist:
        if s not in check: # S_iの中からチェックリストに含まれないものを数える
            cnt += 1

    print(cnt)
    
if __name__ == '__main__':
    main()
```
## C - ABC conjecture

https://atcoder.jp/contests/abc227/tasks/abc227_c

### 解説

正の整数`N`に対し、$A \leq B \leq C$かつ$ABC \leq N$であるような整数の組$(A, B, C)$を求める問題。

全探索してすべてのデータに触れようと思うと、実行時間にあてはまらない。したがって、計算量を工夫する必要がある。

1つ目のループでは、`N`まで探索しているが、`A`の値の3乗、つまり、`A, B, C`がすべて同じ値のとき、これが`N`を超えると条件を満たさないので、これ以上組み合わせを調べる必要がないので、`break`でループを終了させる。

また、2つ目のループでも`N`まで探索しているが、`B, C`が同じ値のとき、計算結果が`N`を超えると、これ以上の数の組み合わせを求める必要はないので、`break`でループ処理を終了する。

答えの出し方だが、`n//a//b`で`C`の値を求めて、$B \leq C$なので、`C`から`B`の値を引いてあげることで、条件に当てはまる整数の組の個数を求めることができる。

![IMG_0850.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/9f72c877-f140-ca4e-f7e8-ec16da0df4e0.jpeg)

### コード
```python
def main():
    n = int(input())
    
    ans = 0
    
    for a in range(1, n+1):
        if a*a*a > n:
            break
        for b in range(a, n+1):
            if a*b*b > n:
                break
            ans += n // a // b - b + 1
            
    print(ans)
    
if __name__ == '__main__':
    main()
```
## D - Project Planning

https://atcoder.jp/contests/abc227/tasks/abc227_d

### 解説

`N`個の部署があり、それぞれの部署には$A_1, A_2, ..., A_i$人いる。
`K`個の部署から1人ずつ選び、`K`人構成のプロジェクトを作りたい。
このときできるプロジェクトの最大数を求める問題。

それぞれの例題を図式化したものは、次のようになる。

![Qiita-10.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/e8847827-2c58-d6e2-f672-3d0dace93b37.jpeg)

![Qiita-11.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/fe12106b-f2a0-8b66-d588-cff26bf60bee.jpeg)

最大数を求めるこの問題は、単調性を持つので、**二分探索**を使用することができる。

![Qiita-12.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/20b4207d-d05f-f5f8-0fed-a9f427a912c4.jpeg)


例2のように、二分探索における中心の値を`2`と推測すると、$A_3, A_4$はそれぞれ2人いればプロジェクトを作成できる。このように$A_i$か$X$のどちらか最小の方をとり、これらの和を求める。この数値が$K \times X$の値になっているか、つまり、人数が条件を超えていないかを確認する。ここでは、$6 \geq 4 = k \times X$となり、条件を満たすので、`ok`側の変数に値を代入するようにする。

これを繰り返していくと、いずれ`X`の値の境界線となる値、`ok`と`ng`がそれぞれ求まる。今回求めたいのは最大値なので、`ok`を出力してあげれば答えとなる。

![Qiita-13.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/966a1dac-fdc0-bc7b-0462-f06d25c17437.jpeg)


また、今回書いた二分探索のコードは、「めぐる式二分探索」というものである。こちらの詳細については、以前、競技プログラミングでの二分探索について記事を作成しているので、よかったら参考にしていただきたい。

https://qiita.com/uniTM/items/2f2a38f225f04154df9a

![Qiita-14.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/67ee46df-5844-ebd5-c18b-ea2403c335e4.jpeg)

### コード1（めぐる式二分探索）
```python
def main():
    def is_ok(pjt):
        total = 0
        for x in xlist:
            total += min(x, pjt)
        return total >= k * pjt

    def meguru_bisect(ng, ok):
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, k = map(int, input().split())
    xlist = list(map(int, input().split()))

    ok = 0
    ng = 10**18 // k

    print(meguru_bisect(ng, ok))


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

### コード2（関数なし）
```python
def main():
    n, k = map(int, input().split())
    
    xlist = list(map(int, input().split()))
    
    ok = 0
    ng = (10**18) // k
    
    while ng - ok > 1:
        md = (ok + ng) // 2
        total = 0
        for x in xlist:
            total += min(x, md)
        if total >= k * md:
            ok = md
        else:
            ng = md
            
    print(ok)
    
if __name__ == '__main__':
    main()
```

## 編集後記

二分探索は学習済みだったので、いくら青問題とはいえ、ときたかった...