AtCoder ABC173の振り返り - 電電のブログ

はいどうも電電です．

今回もAtCoderの振り返りとしてまとめます．

とりあえず，水色になるまでは，もうちょっとかいておきたいですね．(ネタはあるけどちょっと面倒）

今回の全体を通しての感想としては，D問題までは割といい感じに解けたのですが，E問題の実装部分でバグを踏んで時間切れでした．これを解けないと水色には行けなそうですね．チャチャットいきましょう．

A - Payment
B - Judge Status Summary
C - H and V
D - Chat in a Circle
E - Multiplication 4

A - Payment

お店で N円の商品を買います。 1000 円札のみを使って支払いを行う時、お釣りはいくらになりますか？ただし、必要最小限の枚数の 1000 円札で支払いを行うものとします。

A問題としてはちょっとややこしい問題な気もします．入力の値を1000で割ったあまりを求めると，入力の端数がわかります．この端数のお釣りをかんがえるので，1000からひきます．ただし，1000ちょうどの場合があるので再び1000で割ったあまりを出力します．

N = int(input())
print((1000 - N % 1000) % 1000)

B - Judge Status Summary

高橋君は、プログラミングコンテスト AXC002 に参加しており、問題 A にコードを提出しました。この時の，ジャッジ結果が AC, WA, TLE, RE であったものの個数をそれぞれ求めてください。

これは数え上げを行ってそれを表示する感じですね．単純にfor分で回してもいいですが，０個の場合も返さないといけないことに注意してください．僕はpythonのcollections.Counterの機能を最初使おうかと思ったんですが，0個の場合が面倒だったので普通に辞書を使って数えました．

N = int(input())
S = []
for i in range(N):
    S.append(str(input()))

cnt = {
    "AC":0,
    "WA":0,
    "TLE":0,
    "RE":0
}
for s in S:
    cnt[s] += 1

for key in cnt.keys():
    print("{} x {}".format(key, cnt[key]))

C - H and V

H行W列に並ぶマス目が与えられて，これらのマス目にはそれぞれ，白，黒が割り当ててあり，それらの中で指定した行と列を垢で塗り潰すことができます．この結果残ったますの中で黒いますがK個あるような塗り方が何通りあるか答えよ．

という問題でした．実はこれ結構面倒で制約条件がH,W共に6以下なので，総当たりでいけると気付けるか，そしてそれを実装する力があるかという問題でした．

実装としては，縦，横それぞれにbit全探索を行っていきます．

import numpy as np

H, W, K = list(map(int, input().split()))
c = []
for h in range(H):
    l = []
    for s in input():
        if s == ".":
            l.append(0)
        else:
            l.append(1)
    c.append(l)

ans = 0
for bit_h in range(2 ** H): # bit_hが2進数で隠すか隠さないかを示す
    for bit_w in range(2 ** W):
        k = 0
        nn = np.asarray(c)
        # mask 部分
        for h in range(H):
            """
            (bit_h & 2 ** h)の部分で，マスクがかかっている部分を調べる
            >> hによって，参照したい行が0 or 1なのかを調べる．0なら色がないので，したの作業がいらない
            """
            if (bit_h & 2 ** h) >> h == 0:
                continue
            nn[h] = np.zeros((1, W))
        for w in range(W):
            if (bit_w & 2 ** w) >> w == 0:
                continue
            nn[:, w] = np.zeros((1, H))
        # cnt部分
        if K == np.sum(nn):
            ans += 1
print(ans)

D - Chat in a Circle

あなたはオンラインゲーム「ATChat」のチュートリアルを終え、その場に居合わせたプレイヤーN人で早速とある場所を訪ねることにしました。訪ねる際、N 人は好きな順番で 1 人ずつ到着します。あなたたちは迷子にならないために、既に到着した人たちで環状に並び、新たに到着した人は好きな位置に割り込んで加わるというルールを決めました。最初に到着した人以外の各人は、割り込んだ位置から到着した時点で「時計回りで最も近い人」と「反時計回りで最も近い人」のフレンドリーさのうち小さい方に等しい心地よさを感じます。最初に到着した人の心地よさは 0です。 N人が到着する順番や割り込む位置を適切に決めたとき、N人の心地よさの合計の最大値はいくらになるでしょう？

さてこの問題ですが，色々と実験を行うと，一番居心地の総量が多いパターンは，フレンドリーの値がおおきな人を先に配置しておいて，できるだけフレンドリーな人のところにいくのが良いというのがわかります．となると，フレンドリーさでsortを行ってから高い順に到着すればいいわけです．さらにどう配置するかという問題ですが，せいぜい右と左にしか新しい人は入れない（入ったとしても高い順に到着しているのでフレンドリーが低い人基準になってしまう）ので，高い人のフレンドリー力はせいぜい2回までしか発揮できないという構造になっています．また答えるべきなのは，居心地の良さの合計であって，陣形ではないので，単純に上位から数えていけばいいということになります．(ただし一人目だけは一回しか効力を発揮しません)

N = int(input())
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)

ans = 0
ans += A[0]
tmp = 1
for i in range(1, N - 1):
    ans += A[tmp]
    if i % 2 == 0:
        tmp += 1
print(ans)

E - Multiplication 4

N個の整数 A_i が与えられます。

このなかからちょうど K個の要素を選ぶとき、選んだ要素の積としてありえる最大値を求めてください。そして答えを(10 ** 9 + 7)で割ったあまりを答えてください

これは，積を大きくしろっていう問題なので，与えられる数字が正のみならとても簡単なのですが，負も与えられます．(-) * (-) = +なので，打ち消せればいいのですが，それはわかりません．

条件が結構あるので，整理していくと

まず正の数が作れるかどうかcheckして，正の数が作れるなら，-を2つペアにしたものと，+を二つペアにしたものを集めてきて大きさ順に入れる．作れないなら負の中で最大値を出す．

N,K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 正負に関係なくsort
A_abs = sorted(A, key = lambda x:abs(x))
A_p = [] # plusを入れる
A_n = [] # -を入れる
for i in range(N):
    if A[i] < 0:
        A_n.append(A[i])
    else:
        A_p.append(A[i])

A_n.sort()
A_p.sort(reverse = True)

ok = True
if len(A_p) > 0:
    # 正の数が存在している
    if N == K:
        # 選択肢がない時
        ok = (len(A_n) % 2 == 0)
        # 負の数が偶数個
    else:
        ok = True
else:
    ok = (K % 2 == 0)

ans = 1
if ok == False:
    # 解が正にならない場合は絶対値でソートしたものの中で小さいものからかけていく
    for i in range(K):
        ans *= A_abs[i]
        ans = ans % mod
else:
    if K % 2 == 1:
        # 奇数個選ぶ
        ans *= A_p[0]
        ans = ans % mod
        A_p = A_p[1:]
    position = 0
    pairs = []
    cnt_p = len(A_p)
    cnt_n = len(A_n)
    while cnt_p - position > 1:
        pairs.append(A_p[position] * A_p[position + 1])
        position += 2
    position = 0
    while cnt_n - position > 1:
        pairs.append(A_n[position] * A_n[position + 1])
        position += 2

    pairs.sort(reverse=True)
    for i in range(K // 2):
        ans *= pairs[i]
        ans = ans % mod

print(ans)