目次
パナソニックプログラミングコンテスト2020 C,D,E,F問題メモ
Panasonic Programming Contest 2020
見事にB,C,Dで1WAずつ戴きました。注意力が足りない。
C - Sqrt Inequality
問題
- 整数 $a,b,c$ が与えられる
- $\sqrt{a} + \sqrt{b} \lt \sqrt{c}$ か判定せよ
- $1 \le a,b,c \le 10^9$
解法
演算誤差に注意しましょうという問題。
pythonでは小数値はdouble型であり、だいたい有効数字15桁くらい（10進数）を保持できる。
しかし、今回の場合、それでは足りない。
あまり平方根に求められる有効数字がどれくらいになるか、感覚に無かったが、 解説に紹介されているような $(249999999, 250000000, 999999998)$ を試すと、有効数字17桁まで一致し、18桁目も19桁目を四捨五入すれば一致する。 そのため、有効数字19～20桁は欲しい。
from math import sqrt a = 249999999 b = 250000000 c = 999999998 print(sqrt(a)) print(sqrt(b)) print(sqrt(a) + sqrt(b)) print(sqrt(c)) # 15811.38826921912 # 15811.388300841896 # 31622.776570061018 ┐ # 31622.776570061018 ┴本来異なるのに一致してしまう
より精度を上げた値 √a 15811.38826921912002668789774 √b 15811.38830084189665999446772 √a + √b 31622.77657006101668668236546 √c 31622.77657006101670249375381
想定解は、2乗して移行して平方根を無くし、整数だけで判定できるよう式変形する。
ただpythonではDecimalモジュールがあり、これを使うと28桁の精度で演算してくれるし、必要ならより上げることもできる。
まぁ、便利なものはとりあえず使って、WAなら精度を上げればいいよね（応用が利かなくなっていざという時に困る発想）
ただ今回は問題が非常にシンプルなのでいいが、Decimal型で演算を重ねると当然、速度は遅くなるので注意。
import decimal
a, b, c = map(decimal.Decimal, input().split())
print('Yes' if a.sqrt() + b.sqrt() < c.sqrt() else 'No')
D - String Equivalence
問題
- ある同じ長さの2つの文字列 $s,t$ が「同型」とは、以下を指す
- 任意の $i,j$ について、$s_i=s_j$ なら $t_i=t_j$
- 任意の $i,j$ について、$s_i \neq s_j$ なら $t_i \neq t_j$
- 同型の文字列の中で、辞書順最小である文字列を「標準型」と呼ぶ
- 長さ $N$ の標準型の文字列を、辞書順で全て列挙せよ
- $1 \le N \le 10$
解法
深さ優先探索。樹形図を書くと作るべき文字列を列挙しやすい。
標準形は、同型の中で辞書順最小なので、頭から見て新規に出てくる文字に対して必ずa,b,c…の順に割り振っていくのがいい。
頭から決めていって、たとえば $N=5$ で aba?? まで決まっていたとする。
次に来られる文字は「既に出た内のどれか」か「まだ出てきてない文字」であり、まだ出てきていない文字は上記の通り、cとするのがよい。
- abaa?
- abab?
- abac?
出力も辞書順に行う必要があるが、上記の中では abaa? が必ず他より先に来るので、その探索木を優先的に探っていけばよい。
a -- a -- a -- a ...
| | `-- b ...
| `-- b -- a ...
| |-- b ...
| `-- c ...
`-- b -- a -- a ...
| |-- b ...
| `-- c ...
|-- b -- a ...
| |-- b ...
| `-- c ...
`-- c -- a ...
|-- b ...
|-- c ...
`-- d ...
探索は、再帰関数で書くのが楽。
再帰関数の引数として、実際に文字列をとって1文字ずつ伸ばしていくと、再帰を呼ぶたびに新しいオブジェクトが作られ、メモリを食う（今回はそれでも間に合うが）。
文字列を配列で表現し、1階層下のDFSを呼ぶ直前にappend、関数に参照で渡し、終わったらpopすると、配列を使い回せて、若干メモリの節約になる。
s = 'abcdefghij'
sg = s.__getitem__
def dfs(ans):
if len(ans) == n:
print(''.join(map(sg, ans)))
return
for i in range(max(ans) + 2):
ans.append(i)
dfs(ans)
ans.pop()
n = int(input())
dfs([0])
E - Three Substrings
問題
- ある英小文字からなる文字列 $S$ がある
- $S$ に対して以下の操作を行って文字列を生成する
- 1文字以上の連続する文字列を切り出して、さらにいくつかを
'?'で置き換える
- 3回、$S$ から操作により（独立に）生成した文字列 $A,B,C$ が与えられる
- 元の文字列 $S$ の文字列長としてあり得る最小値を求めよ
- $1 \le |A|,|B|,|C| \le 2000$
例
これで7文字 こうすると6文字 A ??c? ??c? ??c? B ac?a ac?a ac?a C ?b?a ?b?a ?b?a S accab?a ?acbaa
最小値なので、6文字が答え
解法
?を含むのが片方だけなら正規表現とか使えるんだけど、両方に含むので自力で比較するしかない。
ワイルドカードを含む文字列検索アルゴリズムにはBitap法などがあるが、この問題では愚直比較でも解ける。
以下の方法により、とりあえず答えは出せる。
- $A$ の位置を固定
- $A$ に対する $B$ の相対的な位置を全探索 $O(N)$
- その位置で$A$ と $B$ が一致するか判定 $O(N)$
- OKなら $A$ に対する $C$ の相対的な位置を全探索 $O(N)$
- その位置で $A \& B$ と$C$ が一致するか判定 $O(N)$
$A \& B$ は「$A$ と $B$ を今の仮位置で重ね合わせた結果、一方が '?' で一方が英小文字なら、英小文字に確定させた文字列」とする。 $N$ は $|A|,|B|,|C|$ の長さだが、具体的にどれの長さというわけではない、まぁ3つを適当に合わせた概念とする。
これでは $O(N^3)$ かかる。 長さが全て上限の2000で、さらに'?'が多くて一致しやすいケースなどを考えれば無理。
ここで、「$A \& B$ と$C$ が一致する」という判定は、「$A$ と $C$ が一致する、かつ $B$ と $C$ が一致する」に分割できる。
そして、分割してしまえば、これらは $O(N^2)$ で事前計算でき、ループ中では $O(1)$ で取得可能であるので、全体を $O(N^2)$ に減らせる。
- $(A,B),(A,C),(B,C)$ それぞれの組み合わせについて、以下を計算する
- 一方のもう一方に対する相対位置を-8000～8000とした時それぞれの、一致する・しない $O(N^2)$
- $A$ に対する $B$ の相対的な位置を全探索 $O(N)$
- その位置で$A$ と $B$ が一致するか判定 $O(1)$
- OKなら $A$ に対する $C$ の相対的な位置を全探索 $O(N)$
- その位置で $A \& B$ と$C$ が一致するか判定 $O(1)$
事前計算範囲が-8000～8000となる理由については、以下に示す。文字列の位置は、先頭文字の位置で表すとする。
■B, C が A に対して取り得る相対位置は、各文字長が最大の2000の場合、-4000～4000
最小値を取る場合
i -4000 -2000 0 2000
|----A----|
|----B----|
|----C----|
最大値を取る場合
i 0 2000 4000
|----A----|
|----B----|
|----C----|
■この範囲でB,Cそれぞれの相対位置を探索する場合、
B-C間の相対位置として取り得るのは-8000～8000
i -4000 -2000 0 2000 4000
|----A----|
|----B----|
|----C----|
実際には相対位置-2000～2000を超えた範囲は（そもそも重なってないので）判定は全てTrueとしてよい。
もちろん、この探索はかなり無駄があり、 $A$ と $B$ の位置に隙間が空いていたら $C$ はその隙間を埋める範囲だけ探索すればいい、など 細かく条件分けして効率化することは可能。
ただ、文字列探索はindexの範囲を正しく実装するのにかなりの注意力を必要とするため、 多少の無駄によって一律のアルゴリズムで実装が可能になるのであれば、 特に実装スピードを要求される競プロにおいては、とりあえずそちらで実装して、 どうしてもTLEが取れなければ枝刈りをする、という方針の方がよいのかも知れない。
def match(s, t, ls, lt, i):
return all(s[i + j] == '?' or t[j] == '?' or s[i + j] == t[j] for j in range(min(ls - i, lt)))
a = input()
b = input()
c = input()
la, lb, lc = len(a), len(b), len(c)
ab = [match(a, b, la, lb, i) for i in range(0, la)] + [True] * 8000
ac = [match(a, c, la, lc, i) for i in range(0, la)] + [True] * 8000
bc = [match(b, c, lb, lc, i) for i in range(0, lb)] + [True] * 8000
ba = [match(b, a, lb, la, i) for i in range(1, lb)] + [True] * 8000
ca = [match(c, a, lc, la, i) for i in range(1, lc)] + [True] * 8000
cb = [match(c, b, lc, lb, i) for i in range(1, lc)] + [True] * 8000
ab.extend(reversed(ba))
ac.extend(reversed(ca))
bc.extend(reversed(cb))
ans = la + lb + lc
for db in range(-lb - lc, la + lc + 1):
ab_ok = ab[db]
if not ab_ok:
continue
for dc in range(-lb - lc, la + lb + 1):
ac_ok = ac[dc]
bc_ok = bc[dc - db]
if ac_ok and bc_ok:
ans = min(ans, max(la, db + lb, dc + lc) - min(0, db, dc))
print(ans)
F - Fractal Shortest Path
問題
- シェルピンスキーのカーペット の要領でレベル30まで繰り返した盤面を考える
- 最小単位を1辺としたマス目で考えると、$3^{30} \times 3^{30}$ マスの盤面となる
- 以下の $Q$ 個のクエリに答えよ
- 1クエリは $a,b,c,d$ の4つの数字で与えられる
- $i$ 行 $j$ 列目を $(i,j)$ とするとき、$(a,b)$ から $(c,d)$ までの、白いマスだけを縦横に移動したときの最短距離を求めよ
- $1 \le Q \le 10000$
- 指定される箇所は必ず白マス
解法
レベル3くらいまで頑張って書いて眺めると、わりと縦も横もスカスカで、ほとんど最短距離で行けることが分かる。
ただ、■をいくつか挟んで対岸にある場合は、その■は迂回の必要がある。 迂回が必要な最も大きい■を考える。
p q
■■■ ... ■■■
s ■■■ ... ■■■ t
■■■ ... ■■■
■は同じ大きさのものが同じ高さに並ぶことはあり得るが、数マスだけ上下にズレたりとかはない。 迂回するとき、上側を迂回するとして $s→p→q→t$ と通ればよい。
ここで、$p,q$ の属する行は、この範囲においては必ず全て白マスである。（黒マスがあったとしたら、それはより大きな■であり、迂回の必要がある最も大きい■に矛盾） 従って、$p→q$ は最短で行ける。
$s→p$ は最短で行けるか？
まず、$p$ の属する縦列もこの範囲では白マスである（1つの■の塊の周囲は必ず白マス）。よって、$s$ から上と右に移動を繰り返して、$p$ と同じ行または列に来れたら、後は最短距離で行ける。
その道中まではどうかというと、「上にも右にも進めない」状態にならない限り、どちらかには進める。そしてどちらかに進み続ければいつかは $p$ と同じ行または列に行ける。
上にも右にも進めない状態とは、以下のような感じで $s-p$ 間をナナメに遮る黒マスがあるということになるが、作り方からしてそれはあり得ない。 （任意の $k$ に対し、Lv.$k$ 盤面は最外周1マスを白マスで覆われている。従って、Lv.$k+1$ 盤面を作る際に、2つの Lv.$k$ 盤面の合体により新たな■の隣接が発生することはない。あるとしたら Lv.$k$ 盤面の中に既に含まれている場合だが、これを再帰的に適用した場合、Lv.1盤面に含まれていないといけないことになるが、Lv.1盤面に■の斜めの隣接はない。）
よって $s→p$ は最短で行ける。$q→t$ も同様。
p
■■
■
s ■
よって、最も大きい■を縦か横のいずれか一方に迂回する必要性だけ考えれば残りは最短で行ける。
迂回すべき■のサイズ・迂回距離を求める
迂回する方向を縦に決め打ちし、横は最短距離とする（縦横反転して2通り試して大きい方を答えとする）。
Lv.$k$ 盤面の1辺の長さ（$=3^k$）を $L(k)$ と表す。
$k$ が大きい方から、Lv.$k$ 盤面の中央の■を迂回する必要があるか？を判定する。
$a,c$ を $L(k-1)$ で割ると、商によって、始点終点がそれぞれ 「L(k-1)行をまとめて“1行”とした場合どの“行”にいるか」が分かる。
0 □□□ 1 □■□ 2 □□□ （□はLv.k-1盤面）
商が異なる場合は、迂回の必要は無く最短距離で行ける。
商が等しく、それを3で割った余りが0 or 2なら、Lv.$k$ 盤面では迂回の必要は無い。より小さいLvで試す。
商が等しく、mod 3が1の場合、迂回の必要の可能性があるので、判定を進める。
$b,d$ を $L(k-1)$ で割った商を考えると、今度はどの“列”にいるかが分かる。
↓↓ ↓↓ どの列にいるか？ ...□□□□□□□... ...■□□■□□■... ←この行に共にいることは確定済 ...□□□□□□□...
- 商の差が1以下なら、同じまたは隣接する□に位置しているので、Lv.$k$ 盤面では迂回の必要は無い。
- 商の差が2以上なら、迂回の必要があることが確定する。
迂回距離（最短移動における縦移動の距離）は、$a,c$ を $L(k-1)$ で割った余りを $m_a,m_c$ として、以下の小さい方を取る。
- 上に迂回する場合は $(m_a+1) + (m_c+1)$
- 下に迂回する場合は $(L(k-1) - m_a) + (L(k-1) - m_c)$
import sys
def solve(a, b, c, d):
for i in range(30, 0, -1):
# ここに到達している時点で、Lv.i 盤面の同じ横ならびに位置することは保証されている
d3i = d3[i - 1]
da, ma = divmod(a, d3i)
dc, mc = divmod(c, d3i)
if da != dc:
return abs(a - c) + abs(b - d)
if da != 1:
a, c = ma, mc
continue
db, mb = divmod(b, d3i)
dd, md = divmod(d, d3i)
if (abs(db - dd) < 2):
a, c = ma, mc
continue
return min(ma + mc + 2, 2 * d3i - (ma + mc)) + abs(b - d)
return abs(a - c) + abs(b - d)
d3 = [pow(3, i) for i in range(31)] + [0]
q = int(input())
buf = []
for line in sys.stdin:
a, b, c, d = map(int, line.split())
a -= 1
b -= 1
c -= 1
d -= 1
ans = max(solve(a, b, c, d), solve(b, a, d, c))
buf.append(ans)
print('\n'.join(map(str, buf)))
