A. Generalized ABC
ASCIIコードを文字にするchrと文字をASCIIコードにするordを使います。
実装(Python)
k = int(input())
ans = ""
for i in range(k): ans += chr(ord("A") + i)
print(ans)
B. Let's Get a Perfect Score
総当たりです。解説通りですが、比較の計算量はbit演算を使うと高速になります。
ある$S_i$と$S_j$を比較する際には$m$個の要素を比較しますが$m \leq 30$なので、int32の範囲で1インストラクションで比較ができ、30倍程度の改善が見込まれます。
サンプルコードでは文字列のreplaceを使ったバイナリ変換をしていますが、ビットシフトなどを用いるともう少し高速に処理できます。
実装(Python)
n, m = map(int, input().split())
allbit = (1 << m) - 1 # 4bitなら 1111を作る
ans = 0
dat = []
for _ in range(n): # oxoxを1010に変換して2進数として読み込む
s = input().replace("o", "1").replace("x", "0")
dat.append(int(s, 2))
for i in range(n):
for j in range(i+1, n):
if dat[i] | dat[j] == allbit: ans += 1
print(ans)
C - String Delimiter
フラグ管理をします。
時間計算量、空間計算量は$O(N)$です。
実装(Python)
n = int(input())
s = input()
kakko = False
ans = []
for x in list(s):
if x == '"':
kakko = not kakko
elif x == ",":
if kakko: ans.append(",")
else: ans.append(".")
continue
ans.append(x)
print("".join(ans))
D - Make Bipartite 2
この問題は次のように言い換えられます。
- 単純無向グラフが与えられます。このグラフの各連結成分が２色で彩色可能かを判定してください。
- 次に、辺の存在しない2点を選び結合（辺の追加）します。この時にその辺を追加しても各連結成分が２色で彩色可能である必要があります。そのような点を選ぶ数を数え上げてください。
まず、与えられた初期状態のグラフに１つでも２色彩色不可能な連結成分がある場合、答えは０です。辺の追加はできても辺の削除ができないためです。
辺の追加が可能な条件を考えます。
- 異なる連結成分に所属する2点に辺を追加する場合は条件を満たします。すでに彩色した２点をつなぐ際に色が違えばそのまま結合すれば彩色された状態は保たれます。色が同じである場合、一方の連結成分の色をすべて反転させて考えれば条件は保たれます。
- 同じ連結成分の２点を考えます。
- 2点間に辺がある場合、条件より線を引くことはできないので不適切です
- 2点の色が同じ場合、その隣接する点は塗り分けなければなりませんがそのような彩色はできないので不適切です
- 2点の色が異なる場合、その辺を追加しても塗り分けられたままなので条件を適します
以上のことから、各点$P_i$について次のことを考えて結果ansを求めていきます。今、$P_i$が所属する連結成分のサイズを$size(P_i)$で示したとします。
- その連結成分外である点は候補になるので$ans$に$n - size(P_i)$を加える
- その連結成分内の点を考えると$ans$に$(連結成分内の同じ色の点の数) - (P_iに隣接する点の数)$を加える
実装を考えます。連結成分という言葉からDSU(UnionFind)を使いたくなるかもしれませんが不要です。
- すべての点を0-1で塗り分けます。全点を探索し、彩色されていない点があれば、まず0としてDFSやBFSをします。この際、開始した点をLeaderとして0-1の数をカウントします。
- 各点について上記の計算をすれば良いです
時間計算量は$O(N)$で空間計算量は$O(N)$です。
実装(C++, DSU利用)
void solve(){
int n, m; cin >> n >> m;
vector<vector<int>> g(n);
dsu uf(n);
REP(i, m){
int u, v; cin >> u >> v; --u; --v;
g.at(u).push_back(v);
g.at(v).push_back(u);
uf.merge(u, v);
}
// 色塗り
deque<int> que;
vector<bool> visited(n, false);
vector<int> color(n, -1);
REP(i, n) {
if(color.at(i) != -1) continue;
que.push_back(i);
color.at(i) = 0;
// paint
while (que.size() > 0) {
auto cur = que.front();
que.pop_front();
for (auto &nxt: g.at(cur)) {
if (visited.at(nxt)) continue;
visited.at(nxt) = true;
color.at(nxt) = 1 - color.at(cur);
que.push_back(nxt);
}
}
}
// validation
REP(i, n){
for(auto &adj: g.at(i)){
// もし、隣接に同じ色がいたら何をしてもダメなので0
if(color.at(i) == color.at(adj)){
cout << 0 << "\n";
return;
}
}
}
REP(i, n) {
assert(color.at(i) != -1);
}
// 各ノードの色を数える
map<int, long long> cnt0;
map<int, long long> cnt1;
REP(i, n){
if(color.at(i) == 0) ++cnt0[uf.leader(i)];
else if(color.at(i) == 1) ++cnt1[uf.leader(i)];
else { assert(false); }
}
ll ans = 0;
REP(i, n){
// まず、グループ以外とはどう繋げてもOK
ans += (n - uf.size(i) ) ;
// 次にグループ内
if(color.at(i) == 0){
ans += cnt1[uf.leader(i)] - g.at(i).size();
} else if (color.at(i) == 1) {
ans += cnt0[uf.leader(i)] - g.at(i).size();
}
}
cout << ans /2 << "\n";
}
E - Choose Two and Eat One
この問題の操作は以下のように言い換えられます。
- N点のグラフGがあり、無向の完全グラフであり、コストが存在する。
- このグラフから好きな辺を選ぶ。この両端の好きな点を選びグラフから消す。グラフのコストを得点に加算する。
- 最後に点が１つになるまでこの作業を繰り返す。得点の最大値を求めよ。
これはグラフの最大全域木を求めることと同値です。
- 操作を考えると辺を$N-1$本選ぶことは明らかです。
- サイクルができてはなりません。サイクルに$k$の点があった際、そのサイクルを構成する辺は$k$です。$k-1$までのサイクルを処理すると点は1点しか残らないため残りの辺を処理することはできません。
- 閉路を生成してはならないため、$N-1$からなるグラフは木であることは自明です。木を構成するコストを最大化すれば良いため、最大全域木を求めればよいです
実装はDSU(UnionFind)を用いたクラスカル法で良いです。降順にソートした順に連結成分でない点間を繋げば良いです。
時間計算量はソートがネックとなり$O(N \log N)$です。空間計算量は$O(N)$です。
実装(Python)
n, m = map(int, input().split())
a = list(map(int, input().split()))
import heapq
cost = []
uf = UnionFindAtCoder(n)
for i in range(n):
for j in range(i+1, n):
cost.append( (- ((pow(a[i], a[j], m) + pow(a[j], a[i], m)) % m), i, j) )
heapq.heapify(cost)
ans = 0
while len(cost) > 0:
c, i, j = heapq.heappop(cost)
if uf.isSameGroup(i, j): continue
uf.Unite(i, j)
ans += c
print(-ans)
F - Union of Two Sets
まず問題を読解します。
- $M$個の$L$, $R$を宣言してください。それぞれは$L$から$R$までの整数の集合です。
- 例えば、$L=1,R=3$は$1,2,3$のことで、$L=5,R=6$は$5,6$のことです。
- この宣言の後、ジャッジは$Q$個の$L,R$を独立に問います。それぞれについて先ほどの$M$個の中から2つの集合(同じでも良い)を選び、その和集合が私の$L$から$R$までの整数の集合と一致するように選んでください。
ここでSparseTableを頭に浮かべます。これは$O(NlogN)$の時間計算量と空間計算量で区間クエリに$O(1)$で答えるデータ構造で冪等半群(idempotent semigroup)の演算を乗せられます。
和集合は結合律が成り立ち、$x^2 = x$が成り立たちます。
SparseTableのクエリは$O(1)$と言われ、事前計算した同じの階層の2つの値を演算することで答えを求めます。いくつか例を示します。
- $L,R = 1,5$のクエリに対しては長さ$2^2=4$の階層にある事前計算した$1,4$と$2,5$を演算して答えます
- $L,R = 2,9$のクエリに対しては長さ$2^2=4$の階層にある事前計算した$2,5$と$5,9$を演算して答えます
実装は多少工夫が必要です。一般にSparseTableの実装は二次元配列で$2^i$の長さの階層と、それぞれのスタートのIndexを持ちます。この問題では最初にすべての区間を宣言し、そのIndexを答えなければなりません。
私は既存のSparseTableライブラリを書き換えて以下のように実装しました。
- $(l1,r1)x(l2,r2) = (l2,r2)x(l1,r1) = (l1, r2)$ ただし、l1 <= l2かつl2 <= (r1+1)とし、である演算xを定義しSparseTableに乗せます
- $N$までの値を含むSparseTableの事前計算をする際、この演算の結果と共にindex番号を持つ変数を用意する
- 事前計算の結果のテーブルを順番に出力する
- クエリに応える際はその範囲のindexを答える
実装(Python)
class sparseTable(object):
func = None
depthTreeList: int = 0
table = []
indextable = []
def load(self, l):
self.n = len(l)
self.depthTreeList = (self.n - 1).bit_length()
self.table.append(l)
cur = 0
indl = []
for i in range(len(l)):
indl.append(cur)
cur += 1
self.indextable.append(indl)
for curLevel in range(1, self.depthTreeList):
l = []
indl = []
for i in range( self.n - (2**curLevel -1) ):
l.append(self.func(self.table[curLevel - 1][i], self.table[curLevel - 1][i + (2**(curLevel - 1)) ] ))
indl.append(cur)
cur += 1
self.table.append(l)
self.indextable.append(indl)
def query(self, l, r): # [l, r)
diff = r - l
if diff <= 0:
raise
if diff == 1:
return(self.indextable[0][l], self.indextable[0][l])
level = (diff - 1).bit_length() - 1
return (self.indextable[level][l], self.indextable[level][r - (2 ** level)])
class sp(sparseTable):
func = lambda self, x,y: ( x[0], y[1] )
n = int(input())
l = []
for i in range(n): l.append( (i, i) )
st = sp()
st.load(l)
ret = []
for li in st.table:
for x in li:
ret.append( x )
print(len(ret), flush=True)
for x in ret:
print(x[0] + 1, x[1] + 1, flush=True)
q = int(input())
for _ in range(q):
a, b = map(int, input().split())
a -= 1
ans = st.query(a, b)
print(ans[0] + 1, ans[1] + 1, flush=True)