ABC 128C - 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
解法
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])