Atcoder Beginner Contests 195 に参加しました！！

皆さんこんにちは！
今回は昨日行われた パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） の感想を載せて行きたいと思います！

目次

A - Health M Death / Difficulty: 5 / 灰

atcoder.jp

A問題の難易度に関してはいつも通りといった感じでしたね。
迷った部分としては、A, Bは問題文あまり読んでいないので
M % H なのか H % M なのかでちょっと考えました。
でも、入力例に H は M の倍数であるのでといった感じのニュアンスが読み取れたのですぐくAC出来ました。

m,h = map(int,input().split())
if h % m == 0:
    print("Yes")
else:
    print("No")

B - Many Oranges / Difficulty: 483 / 茶

atcoder.jp

さて、今回のメインディッシュはこちらの問題でしょうか。
なんとB問題に茶色Diffが来ました！！
調べて見た所B問題が茶色以上なのは ABC107以来 / 2年半ぶり程 の出来事でした！！
どうせいつも通りBまではすんなり行くと思っててCでややこしいのが来るのかなと考えていたので、Bで考える問題が来て驚きました。

解法については、まずどのような場合において "UNSATISFIABLE" となってしまうのかを考えます。

ここで、入力例3を見て見ましょう。

みかんの個数を n とすると、

n = 1のとき、買うことのできる範囲は 300 以上 333 以下です。
n = 2のとき、買うことのできる範囲は 600 以上 666 以下です。
n = 3のとき、買うことのできる範囲は 900 以上 999 以下です。
...
...
n = k - 1のとき、買うことのできる範囲は 300 * (k - 1) 以上 333 * (k - 1) 以下です。
n = kのとき、買うことのできる範囲は 300 * k 以上 333 * k 以下です。

つまり、ここの範囲内に W(kg) が入っていなければ、答えは "UNSATISFIABLE" となります。
ここまでこれば、後一歩です。次に考えるべきポイントは買うことのできる最小値、最大値はいくらであるかということです。
すると先程の上記の図を見てください。
一般に k 個買ったときの最小値は 300 * k なのでそれよりも少ない数で買うことは出来ません。
なので、300 * k <= 100 * A となったタイミングが最小値の答えとなり、300 * k >= B となったタイミングが最大値の答えとなります。

a, b, w = map(int,input().split())
w *= 1000 # gに変換する
cnt = 0
# 以下、maが最小値、miが最大値を表しています。逆になっててすみません...
ma = mi = -1
for i in range(10 ** 7):
    x = a * (i + 1)
    y = b * (i + 1)
    if x <= w <= y and ma == -1:
        ma = i + 1
    if ma != -1 and x > w and mi == -1:
        mi = i

if ma == -1 or mi == -1:
    print("UNSATISFIABLE")
else:
    print(ma, mi)

C - Comma / Difficulty: 265 / 灰

atcoder.jp

次はC問題です。
この問題は結論から言えば、 ”筋肉しか勝たん” です。

コンマの必要な数について場合分けをして見ましょう。

1 <= n <= 999 のとき、必要なコンマの数は 0 個
1,000 <= n <= 999,999 のとき、必要なコンマの数は 1 個
1,000,000 <= n <= 999,999,999 のとき、必要なコンマの数は 2 個
1,000,000,000 <= n <= 999,999,999,999 のとき、必要なコンマの数は 3 個
1,000,000,000,000 <= n <= 999,999,999,999,999 のとき、必要なコンマの数は 4 個
n = 1,000,000,000,000,000 のとき、必要なコンマの数は 5 個

という考察結果が得られるのであとは 0 の数を間違えないように気をつけて判別すれば終わりです。

n = int(input())
if 1 <= n <= 999:
    print(0)
elif 1000 <= n <= 10 ** 6 - 1:
    print(n - 1000 + 1)
elif 10 ** 6 <= n <= 10 ** 9 - 1:
    print(999000 + (n - 10 ** 6 + 1) * 2)
elif 10 ** 9 <= n <= 10 ** 12 - 1:
    print(999999 - 1000 + 1 + (999999999 - 1000000 + 1) * 2 + (n - 1000000000 + 1) * 3)
elif 10 ** 12 <= n <= 10 ** 15 - 1:
    print(999999 - 1000 + 1 + (999999999 - 1000000 + 1) * 2 + (999999999999 - 1000000000 + 1) * 3 + (n - 10 ** 12 + 1) * 4)
else:
    print(999999 - 1000 + 1 + (999999999 - 1000000 + 1) * 2 + (999999999999 - 1000000000 + 1) * 3 + (999999999999999 - 10 ** 12 + 1) * 4 + 5)

D - Shipping Center / Difficulty: 945 / 緑

atcoder.jp

続いてD問題です。
Cまで解き終わった時点でまだ1時間ほどあったので解きたかったですが、解けませんでした。
終わった後に解くことができたのでコードだけ貼っておきます。

方針としては、貪欲法で解くことができます。荷物を入れられる箱のうち、重さ制限の小さいものからできる限り大きなものを入れていくといった方針でACすることができます。方針は簡単ですが、実装がやや複雑な気がします。

import sys
input = sys.stdin.readline
n, m, q = map(int,input().split()) # 荷物、はこ、クエリ
w, v = [0] * n, [0] * n # 大きさ、価値

for i in range(n):
    w[i], v[i] = map(int,input().split())

x = list(map(int,input().split()))

for i in range(q):
    box = [[True, 0] for _ in range(m)] # 荷物が入るかの有無・入る量
    l, r = map(int,input().split())
    # 箱に入れられるかの判定
    for j in range(l, r + 1):
        box[j - 1][0] = False
    # 荷物の入れられる最大値の判定
    for j in range(m):
        box[j][1] = x[j]
    box.sort(key = lambda x: x[1])

    nimotu = [[0, 0, True] for _ in range(n)] # 荷物の大きさ、価値、詰めたかどうかの有無
    for j in range(n):
        nimotu[j][0], nimotu[j][1] = w[j], v[j]
    # 価値の大きい順にソート
    nimotu.sort(key = lambda x: x[1], reverse = True)
    ans = 0
    for j in range(m):
        if box[j][0] == False: continue # 使えない箱だったらスルー
        for k in range(n): # 入れれる箱の場合どの荷物を詰めるかを見ていく
            if nimotu[k][2] == True and box[j][1] >= nimotu[k][0]:
                nimotu[k][2] = False
                ans += nimotu[k][1]
                break
    print(ans)

E - Lucky 7 Battle / Difficulty: 1609 / 青

atcoder.jp

全く問題すら見ていません。ここまでいけるようになりたいです。

F - Coprime Present / Difficulty: 2068 / 黄

atcoder.jp

こちらに関しても問題すら見ていません。
なにやら既出の問題だったそうですね。精進すると既出の問題が増えそうなので継続して今後も精進して行きたいです...

コンテスト結果

今回のコンテスト結果は以下のような結果となりました。

ABC195のコンテスト結果

Dも解けたかもしれなかったので残念です。次回こそは４完します！！！

それにしても緑パフォ取りまくってるのに茶コーダーというのはなかなか面白いですね（）

永年茶コーダー

最後に

ほんとに緑まで後ちょっとです。本日のARCには参加できませんが、とにかく早く緑に行きたいです。
よければ応援よろしくお願いします！