目次
Mujin Programming Challenge 2018
Mujin Programming Challenge 2018
ロボットをとてもかしこくうごかすしくみをつくる会社主催のプログラミングコンテストでした。
A - コンテスト名
問題
- 文字列の先頭5文字が'MUJIN'であるか判定せよ
- ただし文字列は5文字に満たない場合もある
解法
Pythonなら's[:5]'で、5文字未満でも取れるだけ取ってきてくれるので場合分けの必要が無く楽。
print('Yes' if input()[:5] == 'MUJIN' else 'No')
B - セキュリティ
問題
- 数字を、$N$ から始めて、文字列 $S$ に従って増減させる
- $S$ は先頭から読んでいって、
'+'なら1増やし、'-'なら1減らす - 初期状態を含め、どこかで
'0'になるか判定せよ
解法
そのままシミュレーションすればよい。
def solve(a,s):
if a==0:
return True
for c in s:
if c=='+':
a+=1
else:
a-=1
if a==0:
return True
return False
a=int(input())
s=input()
print('Yes' if solve(a,s) else 'No')
C - 右折
問題
- 平地'.'と障害物'#'で表される $H \times W$ のグリッドがある
- ロボットを、好きなマスに、上下左右好きな方向に置く
- ロボットは平地のマスを、1マス以上進み、右折し、さらに1マス以上進み停止した
- 置いた場所と停止した場所の組み合わせは何通りあるか
解法
数え上げる時、似たパターンをどうやってまとめるかを考える。
出発点を基準に考えると、4方向×右折までに進む距離のパターン数×右折後に進む距離のパターン数 を考えることになりそうだが、右折までに進む距離によって右折後に進める距離のパターン数が変わってくる。それは大変なので、もうちょっと上手い方法がありそう。
ここで、①から出発した時と、②から出発した時と、同じ場所で右折するなら「右折後に進める距離のパターン数」は同じことに気付く。これを事前計算しておくと1回1回求めなくてよい。
① ②
→→→→┐ 右折後に進める距離のパターン数
↓ ＝右折後に連続する平地のマス数
↓
ならばということで右折点を基準に考えてみると、同じことが「右折までに進める距離のパターン数」でも言える。
→→→→┐ ③で止まっても④で止まっても、
↓③ 同じ場所で右折してきたなら、
↓ 右折前に進んだ距離のパターン数
↓④ ＝右折前に連続する平地のマス数は同じ
よって、1方向について（右折までに進んだ距離のパターン）×（右折後に進んだ距離のパターン）で効率よくまとめられそう。
また、4方向についても、
①⑧
↓↑
②←┘└←⑦
③→┐┌→⑥
↓↑
④⑤
①の方向から来て右折までに進める距離のパターン数（=①の方向に連続する平地数）を $p_1$ で表すと、1つの右折点に付き4方向網羅したパターン数は
$$p_1p_2+p_3p_4+p_5p_6+p_7p_8$$
となるが、たとえば $p_1=p_8$ なので、同じものをまとめると $(p_1+p_5)(p_3+p_7)$ で計算できる。
- $(p_1+p_5)$: 縦方向に連続する平地数-1であり、縦に連続する平地同士はみんな同じ値となる
- $(p_3+p_7)$: 横方向に連続する平地数-1であり、横に連続する平地同士はみんな同じ値となる
なので、これらを別々に計算しておいて、同じ場所の数字を掛け合わせると、そこを右折点にした時のパターン数が計算でき、全て足し合わせたものが答えとなる。
→row ↓column 同じマスを掛け合わせる ...# 2220 1210 2420 .... 3333 1210 -> 3630 -> 20 全て足す #.## 0000 0200 0000
結構計算量的にしんどくて、Pythonだとよほど高速化を頑張らないと間に合わない（少なくとも通せている人はいなかった）。PyPyなら通った。
n, m = map(int, input().split())
field = []
for i in range(n):
field.append([int(c == '.') for c in input()])
field_row_acc = [[0] * m for _ in range(n)]
for i, row in enumerate(field):
l = 0
a = 0
curr_row = field_row_acc[i]
for j, c in enumerate(row):
if c == 0:
if l < j:
curr_row[l:j] = [a - 1] * (j - l)
l = j + 1
a = 0
continue
a += 1
if l < m:
curr_row[l:m] = [a - 1] * (m - l)
field_t = list(zip(*field))
field_col_acc = [[0] * n for _ in range(m)]
for i, row in enumerate(field_t):
l = 0
a = 0
curr_row = field_col_acc[i]
for j, c in enumerate(row):
if c == 0:
if l < j:
curr_row[l:j] = [a - 1] * (j - l)
l = j + 1
a = 0
continue
a += 1
if l < n:
curr_row[l:n] = [a - 1] * (n - l)
field_col_acc = list(zip(*field_col_acc))
ans = 0
for row1, row2 in zip(field_row_acc, field_col_acc):
for c1, c2 in zip(row1, row2):
ans += c1 * c2
print(ans)
D - うほょじご
問題
- $x,y$ に、ちょっと変わった互除法を繰り返し適用する
- まず、$x,y$ の小さい方を、10進表記でひっくり返す。123→321, 100→1
- その後、$x,y$ の大きい方から小さい方を引く
- $x,y$ のいずれかが0なら終了する
- すると、$x,y$ がループして永遠に操作が終わらない組が出てくる
- $M,N$ が与えられた時、$1\le x \le M, 1\le y \le N$ の範囲で、永遠に終わらない組はいくつあるか答えよ
- $1 \le M,N \le 999$
例
(x,y)=(12,38) (21, 38) 小さい方をひっくり返す (21, 17) 大きい方から小さい方を引く (21, 71) 小さい方をひっくり返す (21, 50) 大きい方から小さい方を引く (12, 50) 小さい方をひっくり返す (12, 38) 大きい方から小さい方を引く ...ループ
解法
試しに $N,M=100$ の範囲で探してみるが、いまいち法則性がわからなかった。
制約が $1000 \times 1000$ で $10^6$ くらいなので、状態を全て持っておくくらいのことはできる。
とりあえず、ある組 $(x_1,y_1)$ の遷移中に現れる他の組 $(x_2,y_2)$ は、終了するかループするかの結果が同じになる。
解説を見ると、これは、自明な終了パターンから操作を逆向きに適用して、たどり着けない組がループする組、という方法で解けると。
グラフはいつも唐突に出てきて僕たちを惑わせる。
実装
まず $1000\times 1000$ の配列を'1'で埋め尽くす。
自明な終了パターンである $(0, 1),(0,2),...(0,999)$ またはその逆の組から、操作を逆向きに適用して探索し、たどり着けた組を'0'にする。
探索が終わったら2次元累積和をとると、配列の $[N][M]$ の値が答えである。
遷移に注意が必要となる。基本的に「どちらからどちらを引くか」「どちらをひっくり返すか」で4通りの遷移が考えられるが、ひっくり返す前の数字はもう一方より小さくないといけない。しかしそれは実際にひっくり返してみるまでわからないので、試してみることが必要となる。
123, 456
↙ ↘ どちらかにどちらかを足す
579, 456 123, 579
↙ ↘ ↙ ↘ どちらかをひっくり返す
975,465 579,654 321,579 123,975
x x o x ひっくり返す前の方が小さいか
また、遷移の上で桁数が増えることは無い。よって、途中で4桁以上になったら、999以下の数字からの遷移ではあり得ないので探索を止めてよい。
また、数字をひっくり返した結果、末尾に'0'が付くことはあり得ない。10の倍数の数字はひっくり返してはいけない。
また、2桁以下の数字'AB'は、'BA'の他に、'BA0'をひっくり返した結果としてもあり得るので、そちらも試さないといけない。
from itertools import accumulate
def transition(x, y, q, checked):
p = x + y
if p >= 1000:
return
if p % 10 != 0:
rp = int(str(p)[::-1])
while rp < 1000:
if rp <= x and not checked[x][rp]:
q.add((x, rp))
q.add((rp, x))
if rp <= y and not checked[rp][y]:
q.add((rp, y))
q.add((y, rp))
rp *= 10
if x % 10 != 0:
rx = int(str(x)[::-1])
while rx < 1000:
if rx <= p and not checked[rx][p]:
q.add((rx, p))
q.add((p, rx))
rx *= 10
if y % 10 != 0:
ry = int(str(y)[::-1])
while ry < 1000:
if p >= ry and not checked[p][ry]:
q.add((p, ry))
q.add((ry, p))
ry *= 10
def solve(n, m):
d = [[1] * 1000 for _ in range(1000)]
checked = [[False] * 1000 for _ in range(1000)]
d[0][0] = 0
checked[0][0] = True
q = {(i, 0) for i in range(1, 1000)}
while q:
x, y = q.pop()
if checked[x][y]:
continue
checked[x][y] = checked[y][x] = True
d[x][y] = d[y][x] = 0
transition(x, y, q, checked)
d = [list(accumulate(e)) for e in d]
d = [list(accumulate(e)) for e in zip(*d)]
return d[n][m]
n, m = map(int, input().split())
print(solve(n, m))
E - 迷路
問題
- $N \times M$ のグリッド
- 障害物が'#'、平地が'.'で表され、'S'と'G'が1つずつある
- 'S'から'G'まで平地をロボットが移動する
- ロボットは上下左右に隣接するマスへの移動に1秒かかる
- 進める方向が下記の通り制約されている中で、最も早く着ける時間を求めよ
- 移動制約
- 進める方向は、長さ $K$ の'UDLR'のいずれかからなる文字列 $d$ で規定される
- 出発を $t=0$ として、時刻 $t$～$t+1$ の間に進める方向は、文字列 $d$ の $t\mod{K}$ 文字目(0-indexed)の示す1方向に限定される
- 'U'=上、'D'=下、'L'=左、'R'=右
- ロボットは、各時刻において移動せずその場に留まることもできる
例
N=2 M=3 d = UDRRL S.. .#G
| t | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 進める方向 | U | D | R | R | L | U | D | … |
| 実際の移動 | 待 | 待 | R | R | 待 | 待 | D | 到着! |
解法
こういうグリッド内の移動は、各マスを頂点とし、上下左右マスへの移動を辺と見做したグラフ上の経路探索問題として解くのがよくある解法。
今回は、時間で移動できる方向が制約されているのが特徴的。とはいえ、移動できるようになるまで待つこともできる。
まず、各マスへは早く着くほどよい。後から着いた方が結果的に'G'に着くのが早くなる、ということは無い。上に移動したいがなかなか移動できなくて待っている間に後着に追いつかれたとしても、「抜かされる」ことはない。
この条件であれば、Dijkstra法の考え方が使える。優先キューを使えば、最初にノードを訪れたコストが、そのノードへの最短であると保証される。
今居るマスから4方向に直接遷移する辺のコストを考える。回り回って結果上のマスに到着する移動は考えず、あくまでグラフ上に張る辺として、直接の移動のみを考える。
その場合、例えば上への移動なら、「次に上に動けるようになるまで待機して、動けるようになったら動く」のが素直に最も早く着ける。「各マスへは早く着けるほどよい」のだから、上に動けるけど敢えて見逃して次の機会で行った方が最終的には……とかは無い。（$d$ の中にその方向が出てこない場合は移動できないが）
よって、隣接マスへの移動コストは「待つ時間+移動時間(=1秒)」となる。
すると、ノードへの到着時刻によって、次のマスへの移動コストが変動することになる。このようなネットワークを Time-Dependentと呼ぶ。
Time-Dependentなネットワークにおいて、以下のような辺を、FIFO制約を満たすという。
- 時刻 $t_1$ に通過開始したらコスト $c_{t1}$ かかって $t_1+c_{t1}$ に次の頂点に着く
- それより後の時刻 $t_2$ に通過開始しても、$t_1+c_{t1} \le t_2+c_{t2}$ となり、$t_1$ の出発より早く着けることはない
- 以上が、任意の $t_1, t_2$ に成り立つ
全ての辺がFIFO制約を満たすなら、Dijkstraアルゴリズムが使える（上の条件をより明確に言い換えただけだが）。逆に言うと、Time-Dependentなら、この条件を満たすか確認しないとDijkstra法は使えない。（そもそもNP困難らしい）
移動コストの算出方法だが、$K$ の制約が $10^5$ とでかいので、1回ずつ「時刻 $t$ に着いたので、次に $d$ 中に出てくる'U'は何秒後か……」などと調べていては間に合わない。 事前計算で、各時刻に着いた時の、4方向それぞれの移動コストを求めておくとよい。
import sys
from heapq import heappop, heappush
def make_move(s):
ss = s + s
move = [[-1] * k for _ in range(4)]
u, d, l, r = [float('-inf')] * 4
for i, c in list(enumerate(ss))[::-1]:
if c == 'U':
u = 1
d += 1
l += 1
r += 1
elif c == 'D':
u += 1
d = 1
l += 1
r += 1
elif c == 'L':
u += 1
d += 1
l = 1
r += 1
else:
u += 1
d += 1
l += 1
r = 1
if i < k:
move[0][i] = u
move[1][i] = d
move[2][i] = l
move[3][i] = r
return move
def search(s, g, move, field):
q = [(0, s)]
visited = [[False] * m for _ in range(n)]
movedir = list(zip(move, [-1, 1, 0, 0], [0, 0, -1, 1]))
while q:
cost, cell = heappop(q)
if cell == g:
return cost
i, j = cell
if visited[i][j]:
continue
visited[i][j] = True
ck = cost % k
for mov, di, dj in movedir:
ti, tj = i + di, j + dj
if field[ti][tj] == '#':
continue
mc = mov[ck]
if mc == float('-inf'):
continue
if visited[ti][tj]:
continue
nc = (ti, tj)
heappush(q, (cost + mc, nc))
return -1
n, m, k = map(int, input().split())
d = input()
field = ['#' * (m + 2)]
s, g = None, None
for i, row in enumerate(sys.stdin.readlines()):
row = '#' + row + '#'
field.append(row)
if s is None:
f = row.find('S')
if f > -1:
s = (i + 1, f)
if g is None:
f = row.find('G')
if f > -1:
g = (i + 1, f)
field.append('#' * (m + 2))
move = make_move(d)
print(search(s, g, move, field))
F - チーム分け
問題
- $N$ 人をチームに分ける
- 1チームの人数は問わないし各チームで異なっていてもよい
- $i$ 番目の人は、$a_i$ 人より大きいチームには所属したくない
- 全ての人の要望を叶えつつ、チームを分ける方法は何通りか、$\mod{998244353}$ で答えよ
- 数え上げるにあたり、チームの並び順は問わない
例
N=4 a: 3 2 3 4
(1,3,4),(2) (1,2),(3,4) (1,3),(2,4) (1,4),(2,3) (1,2),(3),(4) (1,3),(2),(4) (1,4),(2),(3) (1),(2,3),(4) (1),(2,4),(3) (1),(2),(3,4) (1),(2),(3),(4)
以上の11通り
解法
$k$ 人のチームを作るなら、$k$ 以上の値を宣言してる人から選ぶことになる。それらの人は、$k-1$ 人以下のチームにも必ず所属できる。
よって、作るチームを人数の大きい方から決めていって、どのチームにもまだ所属していない人数で区別する動的計画法が考えられる。
$dp[k][r]=$ $k$ 人のチームまで考察済みで、$r$ 人がまだ残っている場合のパターン数
遷移を考える。$dp[k+1][r]=p$ が計算済みで、$k$ 人のチームを作る場合を、「配るDP」で考える。
- 配るDP: dp[k+1][ri]から遷移できる次の状態（各dp[k][rj]）に対して、状態数を“配る”ように加算していく
- 貰うDP: dp[k][rj]を求める際に、その計算に必要となる前の状態（各dp[k+1][ri]）から状態数を“貰う”
どっちを基準にして考えるかの違いであって、どちらでもやりやすい方でよい。
まず、$k$ 人のチームに所属でき、かつ、まだどのチームにも所属していない人数は $r+(a_i=k である人数)$ となる。これを$r_n$ とする。$k$ 人のチームのメンバーはこの中から選ぶことになる。
$k$ 人のチームを作らないなら、そのまま $r_n$ 人を持ち越して $dp[k][r_n]$ に $p$ を加算する。
$k$ 人のチームを $i$ 個作るなら、（$i=1,2,...,$作れるだけ）
- $r_n$ 人からチーム1個作る選び方: $c_1={}_{r_n}C_{k}$
- $r_n-k$ 人からチーム1個作る選び方(計2個): $c_2=c_1 \times {}_{r_{n-k}}C_{k}$
- $r_n-2k$ 人からチーム1個作る選び方(計3個): $c_3=c_2 \times {}_{r_{n-2k}}C_{k}$
- …
- $r_n-(i-1)k$ 人からチーム1個作る選び方(計$i$個): $c_i=c_{i-1} \times {}_{r_{n-(i-1)k}}C_{k}$
が係数となり、$dp[k][r_n-ik]$ に $\displaystyle p \times \frac{c_i}{i!}$ を加算していく。
$i!$ で割っているのは、同じ人数のチームの並び順を考慮しないため。上記の考え方だと、$c_i$ は並び順まで区別した通り数となっている。
以上を、$dp[k+1][r] \gt 0$ である各 $r$ についておこなうと、$dp[k]$ の状態が確定する。
$k=1$ まで求めたら、$dp[1][0]$ が答えとなる。
実際には、$k=2$ まで求めたら、残りを1人ずつのグループに分ける方法は各1通りしか無いため、$dp[2][r]$ を合計した値が答えとなる。
from collections import Counter, defaultdict
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
n = int(input())
d = Counter(map(int, input().split()))
MOD = 998244353
facts, invs = prepare(n, MOD)
grp_size = max(d)
dp = {0: 1}
while grp_size > 1:
newer = d[grp_size]
ndp = defaultdict(lambda: 0)
for remain, patterns in dp.items():
rn = remain + newer
ndp[rn] += patterns
ndp[rn] %= MOD
co = 1
grp_cnt = 1
while grp_cnt * grp_size <= rn:
new_remain = rn - grp_cnt * grp_size
co *= facts[new_remain + grp_size] * invs[grp_size] * invs[new_remain]
co %= MOD
ndp[new_remain] += patterns * co * invs[grp_cnt]
ndp[new_remain] %= MOD
grp_cnt += 1
dp = ndp
grp_size -= 1
print(sum(dp.values()) % MOD)
