Codeforces Round #392 (Div. 2)

codeforces

参加しました

A.o
B.o
C.xo

A. Holiday Of Equality

問題要約

皆が同じだけのお金を持つようにお金を分配する
お金を持ってる人から減らすことはできない

解き方

一番多くお金を持ってる人に合わせるしかないので
a_iの最大値を探してそれをmax_aとすると
(max_a - a_i)の総和が答えになる

問題文の読解に時間がかかった

実際に書いたコード

import sys

n = int(input())
A = [int(a) for a in input().split()]

ans = 0
a_max = max(A)

for a in A:
    ans += (a_max - a)

print(ans)

もうちょっと簡潔に書けたかな

n = int(input())
A = [int(a) for a in input().split()]

a_max = max(A)
ans = sum(a_max - a for a in A)

print(ans)

B. Blown Garland

問題要約

赤青黄緑の電球が並んでて、そのうちのいくつかの電球が切れてる
その並びのどの４つの連続した並びを取っても色がダブっていることはない
その並びのなかでどの色も最低一つは生きている
各色について切れている電球の数を求めよう

解き方

文字列の並びから、切れている電球の色を消去法で確定させていく方法なのかと
思ったけどどうやって書けばいいか分からなくて詰まった
それでよく考えたらあり得る並び方はRGBYRGBYRG...みたいな最初の４つの並びの
繰り返ししかないと分かったので、4! = 24の総当たりで全ての組合せを試して
矛盾しないものがあったら後はそれと元の並びを比較してカウントすればいいという
解法に至った
itertoolsのpermutationsとか初めて使ったけど便利だと思った

実際に書いたコード

import sys
from itertools import cycle
from itertools import permutations

S = input()

cnt = {'R':0, 'B':0, 'Y':0, 'G':0}

rbyg = ('R', 'B', 'Y', 'G')

for col4 in permutations(rbyg):
    cyc = cycle(col4)

    kouho = ''

    for i in range(len(S)):
        kouho += next(cyc)

    for (c1, c2) in zip(S, kouho):
        if c1 != '!' and c1 != c2:
            break
    else:
        for (c1, c2) in zip(S, kouho):
            if c1 == '!':
                cnt[c2] += 1
        
        print(cnt['R'], cnt['B'], cnt['Y'], cnt['G'])
        sys.exit(0)

解説見るとR,B,G,Yのインデックスの4の余りを求めて、それと一致する!のインデックスの位置
をカウントする方法って感じでやってた
こっちのほうが簡潔でいいですね

理想解

S = input()

r_i = S.find('R') % 4
b_i = S.find('B') % 4
y_i = S.find('Y') % 4
g_i = S.find('G') % 4

cnt = {r_i:0, b_i:0, y_i:0, g_i:0}

for (i, s) in enumerate(S):
    if s == '!':
        cnt[i % 4] += 1

print(cnt[r_i], cnt[b_i], cnt[y_i], cnt[g_i])

C. Unfair Poll

問題要約

ｎ行ｍ列の教室があって
１行目、２行目、・・・、n - 1行目、n行目、n - 1行目、・・・、２行目、１行目、２行目・・・
と先生がｋ回生徒をあてていく
一番多く当てられる回数、一番少なく当てられる回数、(x, y)にいるSergei君が当てられる回数を求める

解き方

１行目からｎ行目まで行って、２行目まで帰ってくるってのを一つのサイクルと考えると
何回サイクルが回るかが k // ((2n - 2) * m) で求まる
１サイクルで１行目とｎ行目の人間は＋１、間の人間は＋２回当てられる回数が増える
k % ((2n - 2) * m)回の余りはforループ回して実際に当てていく様子をシミュレートした
n = 1のとき０割りになるのでそこだけ場合分けが必要

考えてみると単純だけどこの解法を思いつくのに結構時間がかかった
実装するのも割と面倒な感じで、単純にシミュレートするところのコーディングでミスがあって
結局提出したのが残り１～２分とかギリギリで結構焦った
合ってるか不安だったけど何とか通っててよかった

O(1)の方法は思いつかなかった
ちょっとめんどくさそうな気がするけど、簡単に求まるのかな？

実際に書いたコード

import sys

n, m, k, x, y = map(int, input().split())

if n == 1:
    max_q = k // m + (k % m != 0)
    min_q = k // m
    serg_q = k // m + (y <= k % m)
    pass
else:
    num_q = [[0] * m for i in range(n)]

    loop = k // ((2 * n - 2) * m)

    for i in range(n):
        for j in range(m):
            if i == 0 or i == n - 1:
                num_q[i][j] = loop
            else:
                num_q[i][j] = 2 * loop

    amari = k % ((2 * n - 2) * m)
    zenhan = min((n - 1) * m, amari)
    kouhan = max(amari - (n - 1) * m, 0)

    for i in range(zenhan):
        num_q[i // m][i % m] += 1

    for i in range(kouhan):
        num_q[(n - 1) - (i // m)][i % m] += 1

    max_q = -1
    min_q = float('inf')

    for i in range(n):
        max_q = max(max_q, max(num_q[i]))
        min_q = min(min_q, min(num_q[i]))

    serg_q = num_q[x - 1][y - 1]

    pass
# print(num_q)

print(max_q, min_q, serg_q)
        sys.exit(0)