目次
第一回日本最強プログラマー学生選手権-予選- A～E問題メモ
A - Takahashi Calendar
問題
- 以下に当てはまる $m$ 月 $d$ 日を「積の日」と呼ぶ
- $d$ が2桁で、どちらの桁の数字も2以上
- $d$ の各桁の数字を掛け合わせると、$m$ に等しい
- 以下の暦で、1年の中に「積の日」が何日あるか求めよ
- 月が1月から $M$ 月までの $M$ ヶ月
- 日が、全月共通で1日から $D$ 日までの $D$ 日
- $1 \le M \le 100$
- $1 \le D \le 99$
解法
ある月の $D$ 日が「積の日」にあたるなら、それが何月かは一意に決まる。
よって、各桁が2以上の2桁の日を全て確かめて、その月があるか（各桁の積が $M$ 以下か）を確かめればよい。
m, d = map(int, input().split())
ans = 0
for d1 in range(2, 10):
for d2 in range(2, 10):
dd = d1 * 10 + d2
if dd > d or d1 * d2 > m:
continue
ans += 1
print(ans)
B - Kleene Inversion
問題
- 長さ $N$ の整数列 $A = A_0, A_1, ..., A_{N−1}$
- $A$ を $K$ 回繰り返した長さ $K \times N$ の整数列 $B$ を作る
- $B$ の転倒数を $\mod{10^9+7}$ で求めよ
- $1 \le N \le 2000$
- $1 \le K \le 10^9$
- $1 \le A_i \le 2000$
解法
転倒数は、「数列を、隣り合う要素をswapすることで昇順にソートする時、必要なswap回数」という意味を持つ。以下の例では8となる。
2 3 2 1 3 1 1 2 2-3 1 3 1 2 2 2 1-3 3 1 3 2 2 1 3 1-3 4 2 2 1 1-3 3 5 2 1-2 1 3 3 6 2 1 1-2 3 3 7 1-2 1 2 3 3 8 1 1-2 2 3 3
ここで重要なのは、$A_i \gt A_{i+1}$ であるなら、どの $i$ から入れ替えても、必要回数は変わらない点である。
そこで、1ループの内部で発生する転倒と、ループをまたいで発生する転倒に分けて算出する。
内部
1ループの内部で発生するものは、Binary Indexed Tree などのデータ構造で求められる。 今回の場合は $N$ が小さいので、全ての $i,j$ の組を確認してもよい。
1ループ分の転倒数を $T_{in}$ とすると、これが $K$ ループそれぞれに発生するので、$K \times T_{in}$ となる。
転倒箇所を入れ替えることで、いわば以下のような状態になる。
A = 2 3 2 1 3 1 K = 4 ↓ 1ループの転倒数 Tin: 8 32回の入れ替えで、以下の状態になる 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3
またぎ
ループをまたいで発生する転倒回数は、「自分より右側のループで、自分より小さな数字の個数」である。
v 1ループ目のこの"3"は、
1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 右側にあるループの個数: 3
~~~~~~~ ~~~~~~~ ~~~~~~~ 1ループ内にある小さな数字の個数: 4
計3x4=12個の転倒が発生
右側にあるループの個数は、
- 1ループ目: $K-1$
- 2ループ目: $K-2$
- …
- Kループ目: 0
なので、0から $K-1$ までの $K$ 個の連番の和 $\frac{K(K-1)}{2}$ として、あらかじめ全ループ分を合計しておく。
1ループに出てくる各数字の個数を数え、数字が小さい方から処理する。今までに出てきた数字の個数を記録する変数 $P$ を用意し、0で初期化する。
- 小さい方から $j$ 番目の数字を $D_j$、個数を $C_j$ とする
- 答えに $C_j \times P \times \frac{K(K-1)}{2}$ を加算する
- $P$ に $C_j$ を加算する
とすると、同じ数字をまとめて計算できる。
from collections import Counter
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
i += i & -i
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
single += bit.sum(a)
bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
p = 0
for a, c in sorted(cnt.items()):
ans = (ans + c * p * coef) % MOD
p += c
print(ans)
C - Cell Inversion
問題
- $2N$ 個のマスが横1列に並び、各マスは白か黒で塗られている（各マスの初期状態の色は与えられる）
- 以下の操作を $N$ 回行う
- まだ選んだことのない、異なる2マスを選ぶ
- 2マスの間（両端含む）の色を反転させる
- つまり、最終的には全てのマスが1回ずつ選ばれることになる
- 最終的に全てのマスを白にできるような操作の手順は何通りあるか、$\mod{10^9+7}$ で求めよ
- 選ぶマスの組み合わせが同じでも、操作の順番が異なるものは、別に数える
- $1 \le N \le 10^5$
解法
DP。だが、ある状態から遷移できる状態が限られるので、考える状態数は実質1通り。
$2N$ 個のマスを、先頭から順番に見る。各マスに対して考え得る操作は、以下の2つである。
- 反転させる区間を新しく「開く」
- 既に開いた区間に対して「閉じる」
$DP[i][k]=i$ 文字目まで見て、開いている区間が $k$ 個ある時の状態数 とする。
$k$ の値およびそのマスを開くか閉じるかで、最終的にそのマスが何回反転されるかがわかるため、最終的な色も判定できる。 「最終的にそのマスが白になる」ことを保証しながら遷移を考える。結果的には以下のようになる。
i 0 1 2 3 4 5 6 7 8
B W B B W W W B
k 0 1 12
1 1 6 12
2 1 3 6
3 1
初期状態の $i$ 番目のマスの色を $S_i$ とする。
- $DP[i-1][k=偶数]$、$S_i=$黒の場合
- $i$ 番目のマスをひらくと、奇数回反転され、最終的に白になる
- $i$ 番目のマスを閉じると、偶数回反転され、最終的に黒になる
- よって、開くしかない
- $DP[i][k+1]=DP[i-1][k]$
- $DP[i-1][k=奇数]$、$S_i=$黒の場合
- $i$ 番目のマスをひらくと、偶数回反転され、最終的に黒になる
- $i$ 番目のマスを閉じると、奇数回反転され、最終的に白になる
- よって、閉じるしかない
- ペアにする開いたマスは、$k$ 通りある
- $DP[i][k-1]=k \times DP[i-1][k]$
$S_i=$白の場合も似たような遷移となる。遷移の自由度が無いので、$k$ の取りうる値は各 $i$ で1通りとなる。
途中で $k$ が負になってはならず、最終的には $k=0$ とならないといけない。これに違反したら0通り。
最後に、$DP[2N][0]$ に、操作の手順入れ替え分の $N!$ をかけた値が、答えとなる。
n = int(input())
s = input()
MOD = 10 ** 9 + 7
ans = 1
for i in range(2, n + 1):
ans = ans * i % MOD
pending = 0
for i, c in enumerate(s):
if (i % 2 == 0 and c == 'B') or (i % 2 == 1 and c == 'W'):
pending += 1
continue
ans = ans * pending % MOD
pending -= 1
if pending != 0:
ans = 0
print(ans)
D - Classified
問題
- $N$ 頂点の完全グラフがある
- 各辺に、以下の条件を満たすように、正整数の「レベル」を設定する
- 任意の頂点 $i$ から出発して、同じレベルの辺のみを奇数本、経由して $i$ に戻るような経路が無い
- レベルの最大値が最小となるような例を1点構築せよ
- $2 \le N \le 500$
解法
「偶数本の辺」と聞いたら「二部グラフ」と答える。（本当か？）
今回の場合、頂点をAグループとBグループに2分割してしまえば、Aの1点とBの1点を結ぶ辺は、全て同じレベルに設定してよい。 同じ頂点に戻ってくるには偶数本の辺を通るしか無いことは明らかである。
1 -- 5 (※省略しているが、実際は1-7や1-8などの間にも辺がある)
×
2 -- 6
×
3 -- 7
×
4 -- 8
さて、こうした場合に残る辺を考える。これは先ほどの二部グラフにおける同一グループ同士を結ぶ辺であり、しかもそれぞれで完全グラフとなっている。
1 -- 2 5 -- 6 | × | | × | 3 -- 4 7 -- 8
すると、$N$ の小さい元の問題に帰着できるので、再帰的に解ける。
頂点を2分割する場合、単純に2等分（奇数の場合はどちらかが1つ多い）でよい。頂点数に対して必要なレベルは広義単調増加なので、全体のレベルを低く抑えるには、分割後のグループの大きい方を最小化した方がよい。 ただ、「この解法で最小化するなら2等分がいい」ことは言えるが、そもそもこの解法で最小化できるかの証明は、いまいちできていない。
def fill(ans, l, r, level):
if r - l <= 1:
return
m = (l + r) // 2
for i in range(l, m):
for j in range(m, r):
ans[i][j] = level
fill(ans, l, m, level + 1)
fill(ans, m, r, level + 1)
n = int(input())
ans = [[0] * n for _ in range(n)]
fill(ans, 0, n, 1)
for i, row in enumerate(ans[:-1]):
print(*row[i + 1:])
解説pdfやYouTubeでは、Bitを使った解法が、最小値の証明付きで紹介されていた。
頂点に $0～N-1$ の番号を付けて、その2進数表記から、2頂点間の辺に設定するべきレベルが求まる。
19 10011
26 11010
xor --------
1001
この時、xorで1が立っているビットの桁(この場合1,4のいずれか)を、19と26の間にはる辺のレベルとしてよい。何故か。
「レベル」を「辺を辿る時に、頂点番号の下から[レベル]ビット目に注目する」と解釈する。
そのビットが0である頂点と1である頂点の間にのみ辺を貼るようにすれば、これは二部グラフになる。
0 -- 1
×
0 -- 1
＼
1
2つの頂点番号のXORで1が立っている桁が、両者が異なっている桁であるため、その中から1つ選んでレベルに設定すればよい。 どれを選んでもよいが、Pythonではn.bit_length()で最上位の桁を取れるため、記述が簡潔になる。
以上の理由から、頂点番号は必ずしも0からの連番である必要は無い。 しかし、仮に全く同じ頂点番号の2点が含まれてしまうと、その2点間に設定できるレベルが無くなってしまうため、頂点番号は全て異なっている必要がある。 よって、$N-1$ の2進数表記の桁数分のレベルは、必ず必要になる。
ソースコードはめちゃんこ短くなる。ゴルファー歓喜。
n = int(input())
for i in range(n):
print(*((i ^ j).bit_length() for j in range(i + 1, n)))
E - Card Collector
問題
- $H \times W$ のマス目の上に、$N$ 枚のカードが置かれている
- $i$ 番目のカードは座標 $(R_i,C_i)$ にあり、正整数 $A_i$ が書かれている
- 同じマスに複数枚のカードが置かれていることもある
- 以下の操作を行う
- まず、各行から1枚ずつカードを取る（取らなくてもよい）
- 次に、各列から1枚ずつカードを取る（取らなくてもよい）
- 取ったカードに書かれた整数の合計の最大値を求めよ
- $1 \le H,W \le 10^5$
- $1 \le N \le 10^5$
解法
カードに書かれた値の大きい方から貪欲。ただし取ってよいかの判定がやや難しい。
一番数字の大きいカードを考えると、これは必ず取られる。 取られなかった場合と比較して、そのマスが該当する行と列のいずれかで、最大のカードを取るようにした方がよくなる。
↓8 ↓2
┌──┬──┐ 最大の9が取られない場合、
→5│ 5 8│ 7 9│ ↓2 か →5 を9に変更しても他の行・列に影響は無く、
├──┼──┤ 必ず合計は大きくなる
→4│ 4│ 2│
└──┴──┘
同様に、次に大きい8,7も、必ず取られる。
↓5 ↓9
┌──┬──┐ 8,7が取られない場合、
→8│ 5 8│ 7 9│ 行と列のいずれかで8,7に変更できる余地が残っている。
├──┼──┤
→4│ 4│ 2│ 左の例では、7の行・列は既に大きい数字が入ってしまっているが、
└──┴──┘ 以下のように8の取り方を組み替えることで、取れる
↓8 ↓9
┌──┬──┐
→7│ 5 8│ 7 9│
├──┼──┤
→4│ 4│ 2│
└──┴──┘
しかし、5は、もう5が所属する行・列のいずれでも、それより大きい数字で取られることが決まっており、組み替える余地も無い。 5を取るならそれより大きいカードを1枚諦めざるを得ないため、取る意味が無い。
この「組み替える余地も無い」というのは、どうやって判定すればよいか。
行と列に記号を割り振る。
C D
┌──┬──┐
A│ 5 8│ 7 9│
├──┼──┤
B│ 4│ 2│
└──┴──┘
この時、9は「AかD」、8は「AかC」、7は「AかD」で取る。この行/列が繋がっている範囲内では、各数字を取る行/列は互いに融通できる。 （行/列が繋がっているとは、「AかD」と「AかC」があった時に、共通のAを介して「A-C-D」が繋がっているということを表す）
しかし、行・列とも1つずつしか取れないので、繋がっている行/列数より多いカードは取れない。
5は「AかC」で取れるが、この時、繋がっている「A-C-D」の3つは既に9,8,7で埋まっており、取れない。
次に大きい4は「BかC」で取れるが、これはつながりが「A-B-C-D」に拡張され、もう1枠空くことになるため、取れる。
手順をまとめると
- 行と列に通し番号を振る
- 融通しあえる行/列のつながりを管理するUnion-Find木などを用意する
- 同時に、各グループ内で取ることが決まったカード数も管理できるようにしておく
- 値の大きいカードから、以下の手順で取れるか調べる
- $R_i$ 行と $C_i$ 列をグループ化
- グループ内で、まだ「頂点数＞取ることが決まったカード数」なら、カードを取れる
- 取ったカードの合計値が、最大値
import sys
sys.setrecursionlimit(10 ** 5)
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
self.taken = [0] * n
def _root(self, x):
if self.table[x] < 0:
return x
else:
self.table[x] = self._root(self.table[x])
return self.table[x]
def union(self, x, y):
r1 = self._root(x)
r2 = self._root(y)
if r1 == r2:
new_root = r1
else:
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
self.table[r1] += d2
self.taken[r1] += self.taken[r2]
new_root = r1
else:
self.table[r1] = r2
self.table[r2] += d1
self.taken[r2] += self.taken[r1]
new_root = r2
cells = -self.table[new_root]
taken = self.taken[new_root]
if cells > taken:
self.taken[new_root] += 1
return True
return False
n, h, w = map(int, input().split())
hw = h + w
cards = []
for line in sys.stdin:
r, c, a = map(int, line.split())
cards.append((a, r - 1, h + c - 1))
cards.sort(reverse=True)
uft = UnionFind(hw)
ans = 0
for a, r, c in cards:
if uft.union(r, c):
ans += a
print(ans)
