ABC 128C - Switches

問題概要

C - Switches

解法(解説AC)

bit全探索を行う。
この問題系は虚無でbit全探索も判定も書けるようにしたい。

提出コード

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
sw = []
count = 0
d = defaultdict(int)

for i in range(m):
    p = readl()
    sw.append(p[1:])
p = readl()
count = 0
for i in range(2 ** n):
    den = defaultdict(int)
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in sw[k]:
                    den[k] += 1
    flg = True
    for j in range(m):
        if den[j] % 2 != p[j]:
            flg = False
    if flg:
        count += 1
print(count)

Educational Codeforces R#65 (Div. 2) - C. News Distribution

問題概要

グループに所属する数を数えよ
Problem - C - Codeforces

解法

サイズ付きUnionFindを用いる。
が、(10^5) * 5はPythonだと相当きつい。
PyPy3を用いたが、Input関数を止めてsys.stdin.readlineで高速化しない無理だった。。。

提出コード

# coding: UTF-8
import sys

def find(x):
    if node[x] < 0:
        return x
    else:
        node[x] = find(node[x])
        return node[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    ret = False
    if x != y:
        ret = True
        if rank[x] > rank[y]:
            node[x] += node[y]
            node[y] = x
        else:
            node[y] += node[x]
            node[x] = y
            if rank[x] == rank[y]:
                rank[y] += 1
    return ret

def is_same(x, y):
    return find(x) == find(y)

def size(x):
    return -node[find(x)]

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
node = [-1 for i in range(n + 1)]
rank = [0 for _ in range(n + 1)]
query = [readt() for _ in range(m)]
for a in query:
    if a[0] >= 2:
        for j in a[2:]:
            unite(a[1], j)
for i in range(1, n + 1):
    print(size(i), end=" ")

Codeforces Round #559 (Div. 2) - B. Expansion coefficient of the array

問題概要

Problem - B - Codeforces

数列aが渡される。
1≤i,j≤nとしたとき、 k*|i−j|≤min(ai,aj)を満たすkを答えよ

解法

k = ai / max(i, n- i)を全て試せばよい。

例えば、Nを9としたとき
|i-j|の最大値は数列aiから
0 1 2 3 4 5 6 7 8 (要素)と並べたとき
8 7 6 5 4 5 6 7 8 (各要素の|i-j|の最大)
となる。
aiは、その都度、|i-j|の最大値で割るため
aiが最小だろうがなかろうが全て試すため気にしなくてよい。

#include<bits/stdc++.h>
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<30
#define v(T) vector<T>
#define vv(T) v(v(T))
 
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef long long ll;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int i, j, k;
int main()
{
	int n;
	k = INF;
	cin >> n;
	rep(i,n) {
		int v;
		cin >> v;
		k = min(k, v / max(i, (n - i - 1)));
	}
	cout << k << endl;
	return 0;
}

AGC 033 A - Darker and Darker

問題概要

A - Darker and Darker
H*W列内に".", "#"が存在する。
存在する#を起点に十字で.を#に置き換える。
上記を繰り返したときに、何回目で全てのマスが埋まるか答えよ。

解法

"."→"#"に置き換えたところをqueueに入れ、幅優先探索で置き換えていけば良い。

提出コード

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define INF 1e9

int mp[1001][1001];
bool used[1001][1001];
int hw_count;
int h, w;

int main()
{
	int first_count = 0;
	cin >> h >> w;
	queue<pair<int,int>> q;
	rep(i, h) {
		string s;
		cin >> s;
		rep(j, w) {
			if (s[j] == '#') {
				mp[i][j] = 1;
				first_count++;
				q.push(make_pair(i,j));
			} else {
				mp[i][j] = 0;
			}
		}
	}
	int count = first_count;
	int ans_count = 0;
	hw_count = h * w;
	if (first_count == hw_count) {
		cout << 0 << endl;
		exit(0);
	}
	while(1) {
		if (count == hw_count || q.empty()) {
			break;
		}
		ans_count++;
		queue<pair<int,int>> q2;
		while(!q.empty()) {
			pair<int,int> qq = q.front();
			int qi = qq.first;
			int qj = qq.second;
			q.pop();
			if (mp[qi][qj] == 1) {
				if (used[qi][qj] == true) {
					continue;
				}
				used[qi][qj] = true;
				if (qi + 1 < h) {
					if (mp[qi + 1][qj] == 0) {
						count++;
						mp[qi + 1][qj] = 1;
						q2.push(make_pair(qi + 1,qj));
					}
				}
				if (qj + 1 < w) {
					if (mp[qi][qj + 1] == 0) {
						count++;
						mp[qi][qj + 1] = 1;
						q2.push(make_pair(qi,qj + 1));
					}
				}
				if (qi - 1 >= 0) {
					if (mp[qi - 1][qj] == 0) {
						count++;
						mp[qi - 1][qj] = 1;
						q2.push(make_pair(qi - 1, qj));
					}
				}
				if (qj - 1 >= 0) {
					if (mp[qi][qj - 1] == 0) {
						count++;
						mp[qi][qj - 1] = 1;
						q2.push(make_pair(qi, qj - 1));
					}
				}	
			}
		}
		q = q2;
	}
	cout << ans_count << endl;
	return 0;
}

ABC 035C - オセロ

問題概要

C - オセロ
N個の文字列(初期値0i0i+1...0i+N)に対して、範囲を指定すると対象の要素が1⇔0と反転する。
範囲指定をQ回行った時、Nの文字列を答えよ。

解法

範囲指定の積み重ねの結果で表裏が決まるため、Imos法で解ける。

提出コード

n, q = map(int, input().split())
a = [0 for i in range(n + 2)]
for i in range(q):
    x, y = map(int, input().split())
    a[x] += 1
    a[y + 1] -= 1
for i in range(n + 1):
    if i == 0:
        continue
    a[i] = a[i - 1] + a[i]

s = ''
for i in range(1, n + 1):
    if a[i] % 2 == 0:
        s += '0'
    else:
        s += '1'
print(s)

ABC 113 D - Number of Amidakuji

問題概要

D - Number of Amidakuji
あみだくじ。
0本目からスタートし、W本の長さH + 1までにを任意の線を引いた時
K本目にたどり着くパターンは何パターンあるか答えよ。

解法(解説AC)

現在の位置状態での線の引き方を全列挙し、DP(メモ化再帰)を用いて答える。

ソースコード上のメモとして、
x → 現在の位置
y → 現在の進み具合
for分のi → 現在の位置にいる時の線の配置状態(1が隣接へつながっているとき)
for分のj → NGパターンの列挙(隣へ繋がっているかつ、次の隣へも線が引かれている状態)

提出コード

h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))

def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]

    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

ABC 111 C - /\/\/\/

問題概要

C - /\/\/\/
数列Aに対して、偶数列を任意の値a, 奇数列を任意の値bの2種類のみに置き換える時
最小で何か所置き換えれば条件を満たせるか答えよ。
※ただし、値a, 値bは異なる値とする

解法

偶数列、奇数列から、それぞれ1番目に多い値(a1,b1)と2番目に多い値(a2,b2)を求め
a1とb1が異なるときは、nからa1とb1を引く。
a1とb1が同一である場合、a1とb1で多い方を採用し、
採用されなかった方はa2、またはb2を用いる。
a1とb1が同一かつ、同じ数である場合、
a2とb2を比較し、多い方を採用しnから引けばよい。

提出コード

n = int(input())
a = list(map(int, input().split()))
even = defaultdict(int)
odd = defaultdict(int)
for i in range(n):
    if i % 2 == 0:
        even[a[i]] += 1
    else:
        odd[a[i]] += 1
x = sorted(even.items(), reverse=True, key=lambda t:t[1])
y = sorted(odd.items(), reverse=True, key=lambda t:t[1])
even_index = 0
odd_index = 0
if x[0][0] == y[0][0]:
    if x[0][1] > y[0][1]:
        even_index = 0
        odd_index = 1
    elif x[0][1] < y[0][1]:
        odd_index = 0
        even_index = 1
    else:
        if len(x) > 1:
            print(n - x[0][1] - max(x[1][1], y[1][1]))
        else:
            print(n // 2)
        exit()
else:
    even_index = 0
    odd_index = 0
print(n - x[even_index][1] - y[odd_index][1])