読者です 読者をやめる 読者になる 読者になる

Codeforces Round #392 (Div. 2)

参加しました

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

問題要約

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

解き方

文字列の並びから、切れている電球の色を消去法で確定させていく方法なのかと
思ったけどどうやって書けばいいか分からなくて詰まった
それでよく考えたらあり得る並び方はRGBYRGBYRG...みたいな最初の4つの並びの
繰り返ししかないと分かったので、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行m列の教室があって
1行目、2行目、・・・、n - 1行目、n行目、n - 1行目、・・・、2行目、1行目、2行目・・・
と先生がk回生徒をあてていく
一番多く当てられる回数、一番少なく当てられる回数、(x, y)にいるSergei君が当てられる回数を求める

解き方

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

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

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)