Codeforces Round #684 (Div. 2) ABC1

import sys
import collections
input = sys.stdin.readline
deque = collections.deque
 
for _ in range(int(input())):
    n, c0, c1, h = map(int, input().split())
    s = input().rstrip()
    zCnt, oCnt = s.count('0'), s.count('1')
    print(min(c0*zCnt + c1*oCnt, c0*zCnt + c0*oCnt + h*oCnt, c1*oCnt + c1*zCnt + h*zCnt))

 

A - Buy the String

 

문자열 중 일부만 바꾸는 것으론 절대 최대 이익을 볼 수 없다.

 

따라서 0을 모두 1로 바꾸거나, 1을 모두 0으로 바꾸거나, 그대로 구매하는 세 가지 경우 중 최소가 답이다.

 

 

import sys
import collections
input = sys.stdin.readline
deque = collections.deque
 
for _ in range(int(input())):
    n, k = map(int, input().split())
    nu = k*((n-1)//2)
    s = [*map(int, input().split())][nu:]
    r = 0
    for i in range(0, len(s), len(s)//k):
        r += s[i]
    print(r)

 

B - Sum of Medians

 

결국 n k에 따라 사용하지 않는 수의 갯수가 결정된다.

 

남은 수열에서 |남은 수열| / k 의 간격으로 수를 골라 합하면 된다.

 

 

#include <bits/stdc++.h>
using namespace std;

queue<string> que;
int R, C;
bool board[100][100];

void magic(int rr, int cc, bool a, bool b, bool c, bool d) {
	string t = "";
	if (a) {
		t.append(to_string(rr + 1) + " " + to_string(cc + 1) + " ");
		board[rr][cc] = !board[rr][cc];
	}
	if (b) {
		t.append(to_string(rr + 1) + " " + to_string(cc + 2) + " ");
		board[rr][cc + 1] = !board[rr][cc + 1];
	}
	if (c) {
		t.append(to_string(rr + 2) + " " + to_string(cc + 1) + " ");
		board[rr + 1][cc] = !board[rr + 1][cc];
	}
	if (d) {
		t.append(to_string(rr + 2) + " " + to_string(cc + 2) + " ");
		board[rr + 1][cc + 1] = !board[rr + 1][cc + 1];
	}
	t.append("\n");
	que.push(t);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int TEST; cin >> TEST; while (TEST--) {
		cin >> R >> C;
		for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
			char temp; cin >> temp;
			board[i][j] = (temp == '1');
		}

		for (int r = 0; r < R - 1; ++r) for (int c = 0; c < C; c += 2) {
			bool lc = board[r][c], rc = board[r][c + 1];
			if (lc && !rc) magic(r, c, 1, 0, 1, 1);
			if (!lc && rc) magic(r, c, 0, 1, 1, 1);
			if (lc && rc) magic(r, c, 1, 1, 0, 1);
			if (c + 2 == C - 1) c -= 1;
		}

		for (int c = 0; c < C; c += 2) {
			bool lc = board[R - 1][c], rc = board[R - 1][c + 1];
			if (lc && rc) {
				magic(R - 2, c, 1, 1, 1, 0);
				magic(R - 2, c, 1, 1, 0, 1);
			}
			if (lc && !rc) {
				magic(R - 2, c, 0, 1, 1, 1);
				magic(R - 2, c, 1, 0, 1, 1);
				magic(R - 2, c, 1, 1, 1, 0);
			}
			if (!lc && rc) {
				magic(R - 2, c, 1, 0, 1, 1);
				magic(R - 2, c, 0, 1, 1, 1);
				magic(R - 2, c, 1, 1, 0, 1);
			}
			if (c + 2 == C - 1) c -= 1;
		}

		cout << que.size() << "\n";
		while (!que.empty()) {
			cout << que.front(); que.pop();
		}
	}
}

 

C1 - Binary Table (Easy Version)

 

제한이 3*n*m이라 아무렇게나 풀어도 된다.

 

2 * 2 칸 안에서는 항상 칸의 개수 이하의 행동을 요함을 직접 그려서 증명할 수 있다.

 

 

C2는 n, m이 홀수일 때에 대한 처리가 필요해 보이는데 잘 모르겠다.