tooh’s diary

半角全角、常体敬体が入り乱れるカオス

3/27 AtCoder(-2進法)

こんばんは。しばらく更新しなかったのはチュウニズムの方ばかりコミットしていたためです。とーです。(AtCoderのstreak自体は地味に続いています)

AtCoder


ABC105C

与えられた数字を-2進数で表す問題 2進数とかではなくて負の数で与えられているのが何ともやり辛いところ


考え方は、例えば普通の2進数がどのようになっているかを参考にすると見えてくる

9(10進法)を2進数で表すことを考える これは1001になるが、まず右から一桁目は0もしくは1を表せることを考えれば、ここのビットが立っていれば(つまり1であれば)奇数、立っていなければ(0であれば)偶数を表すことは明らか なぜならそれよりも後ろ(二桁目以降)は2で割ったあまりに対して何の影響も及ぼさないから

というわけで、ここは1を立てておく
ここで1を消費したため、残りの桁では8を表せばよいと分かる

さて、二桁目より後ろを考えるとき、ここから後ろは2**1,2**2......と、必ず二の倍数を表すので、これを二で割って2**0(つまり1)、2**1......としたものを、8を二で割った数、つまり4を表すにはどうすればよいかを考えるのは同じことである

4は2で割り切れるので、一桁目(9を表すときには右から二桁目にある数字)は0でよい

そして、全く同じ要領で、4(から0を除いた数字、実質4)を2で割った数字2を、また二進法で表すことを考える
2は2で割り切れるので、一桁目(9を表すときには右から三桁目にある数字)は0でよい

また2を2で割ると、今度は1が出てきて、これは2で割り切れないので、二進法で表したときの一桁目(9を表すときには右から4桁目にある数字)は1にする

そして、1を消費したので、1から1を引いて0になった ここで終了する
その結果として、9の二進法表示として1001が得られた




今説明したやり方は、-2進法表記でも全く同様に使うことができる。つまり
①:Nが-2(2でもよい)で割り切れるなら、0を並べて-2で割る
②:Nが-2で割り切れないなら、1を並べて、ここで1を消費したのでNから1を除いて、除いた結果0でないなら-2で割る
③:②の結果が0になったならそこで終了する

という感じ(基本的にこのやり方は任意のn進法で使える)
注意として、2進法の時もそうだけど、下の桁から決定していっているので、ビットは前に前にとくっつけていくことを忘れないようにする





ABC110C

文字列を操作するやつ(きらい)

文字列SとTで、文字が一対一対応になっていればYes、そうでなければNoを出せばよい
例えばazzelとappleならば、
a:a
z:p
l:e
e:l
となっているので良いが、
chokudaiとredcoderでは、
c:r
h:e
o:d
k:c
u:o
d:d
a:e
i:r
と、cとiのどちらに対してもrが対応してしまうので(o,dも同様)、例えばc→rと変更したら、rhokudaiとなるが、その後でiをrに変更しようと思うとrとiの間で相互の変換が起こるので、ihokudarになってしまう
これが起こらず、かつちゃんと入れ替えができるのは文字が上と下で一対一に対応してることが必要条件になる これをコードに起こせばよい

3/22 AtCoder(ceilを使う時の注意、DP、N!を素因数分解)

ARC004C

二点間の距離がn個与えられて、点1と点nの距離の最小値はなんぼという問題

点が並んでる順番で距離が与えられているので、折り返すのは最長辺の両端でないといけない(逆にそこじゃないところで折ると長さが伸びてしまう)
求める値は、辺の長さの総和をS、最長辺の長さをmとして、max(0,2*m-S)になる


ARC062C

k = max(-(-A//L[i][0]),-(-B//L[i][1]))

k = max(math.ceil(A/L[i][0]),math.ceil(B/L[i][1]))

は同一のモノではないらしい(上の方が合ってる)
切り上げの時に安易にceil使うと間違えるかもしれない 原因不明 なにこれ


EDPC E 

価値iを達成するのに必要な最小の重量をdp[i]とするタイプのDP
こういうのは、まず全部float('inf')で埋めてから、dp[0]を0に更新して、リストのケツの方(つまりdp[10**5])から値を更新していく 
dp[0]の方から更新していくと、例えば

weight value
3 30
4 50
5 60

という入力を受け取ったときに、dp[50]=4で更新→dp[100]を8で更新(重量4の品物を2回使っていることになるのでこの時点ですでにあり得ない)→......と無限に続いていってしまうので注意

ABC114D

約数を75個持つ数として、例えばp**4とq**14の積を考えたとき、このようにp,qを選んでくるときは
①pには、指数が4以上14未満の数を選び、qには指数が14以上のモノを選ぶ
②p,qいずれも指数が14以上のモノを選ぶ
の二パターンがあり、後者はnC2ではなくnP2(順番も考慮すれば、どちらを4つ、どちらを14つ使うかも考えたことになる)であることに注意して数え上げる

あと、階乗の素因数の個数を求めるコード

N = int(input())
def primes(n):
  ass = []
  is_prime = [True] * (n + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
      continue
    for j in range(i * 2, n + 1, i):
       is_prime[j] = False
  for i in range(len(is_prime)):
    if is_prime[i]:
      ass.append(i)
  return ass
L = primes(N)
factorial_factor = []
for i in range(len(L)):
  k = L[i]
  cnt = 0
  cur = 1
  while N//k > 0:
    cnt += N//k
    cur += 1
    k = L[i]**(cur)
  factorial_factor.append([L[i],cnt])

3/21 AtCoder(最長共通部分列、期待値の線形性)

こんばんは。寝ても寝ても眠いとーです。

ARC092C

N個の座標が与えられて、xy座標の大きいものと小さいものをペアにしていきましょうという問題

想定解が頭良すぎた 自分で最初考えていてのは、xの小さい順にソートしてそれをxの小さい方から覆っていくようにとっていけばよいって方針だったけど、xの小さい順にソート→それで覆えるものでy座標が大きいものをとっていった方が省エネになる

なんか別の解き方もあるみたいなので、それはまたの機会に


EDPC F


最長共通部分列(LCS:Longest Common Subsequence)の問題

例えば、
abcd と becd の最長の共通部分列は bcd となる

長さが欲しいならば、dpを使って、(s,tは文字列)

s = input()
t = input()
dp = []
for i in range(len(s)+1): #s+1行、t+1列のリストを作る
  L = [0]*(len(t)+1)
  dp.append(L)
for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]: #sのi文字目とtのj文字目が一致していたら
      dp[i+1][j+1] = dp[i][j]+1 #リストのi+1行j+1列を、i行j列+1に変更
    else:
      dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]) #dp[i+1][j+1]はdp[i+1][j],dp[i][j+1]の長い方に変更

とすればよい

今回は部分列の長さではなく部分列自体を出力してほしいと言っているが、これをdpで愚直に文字列を形成していくやり方でやるとしんどい

ので、文字列を逆順に追っていき、作った文字列の前に文字を追加することを考える

文字を追加するタイミングは、dp[i+1][j+1]の数字が1減ったときである
これは、現在見ているs,tの文字をn,m番目として、
dp[n][m] == dp[n-1][m]であれば、sを一文字前にずらしても文字列(の長さ)は変わらない→LCS自体に変化はない
dp[n][m] == dp[n][m-1]であれば、tを(略
それ以外→dp[n][m] == dp[n-1][m-1]+1で、ここでLCSは増える(このタイミングで文字列を増やせばよい)
ということからわかる

juppy.hatenablog.com

↑こちらの記事を参考にさせていただきました ありがとうございました


SoundHound Inc. Programming Contest 2018 C

1~nまでの数字を重複を許してm個並べたとき、隣接する数字の絶対値がdになる部分の数の期待値を出す問題

シミュレーションで期待値が出せない以上何かしらの計算で出せるようになっているはず

隣り合う数字の差が0になるペアは(1,1)~(n,n)のn通りで、確率は1/n
差がdになるペアは(1,d+1)~(n-d,n)の(n-d)通りと、これをひっくり返した奴の計2*(n-d)通りなので、確率は2*(n-d)/(n**2)


よって、隣り合う数字の差がdになる確率が分かったため、期待値の線形性(この場合で言えば、期待値は(隣り合う数の差がdになる確率)*(m-1箇所)で求められる)からすぐに答えが分かる

同じような問題で、

[例]
確率1/2で0か1を表示する電光掲示板を8つ並べる。'111'と表示される箇所の数の期待値は?(1111は2つとしてカウントされる)

という問題は、'111'と連続する確率が1/8で、3つ並ぶところは6箇所あるので、6*1/8=3/4と求められる 簡単だね

3/19 AtCoder(PyPy3)

こんにちは。気分が悪くて半日お布団の中にいたとーです。

AtCoder

ARC013A

以前解けなかったきりしばらく放置していた問題

荷物の長さの順列を持ってきて、与えられた容器の辺をその順列の第一、二、三要素で割り切って、掛け合わせたものが容器に入る荷物の数なので、それの最大値を求めるだけ


ABC110D

これも以前解けなかった問題

素因数分解して、指数の部分を分割すればよいっていう賢いやり方が書いてあった すごい

さて実装の段で、nCkをかけていって、最後に10**9+7で割る操作が入ったのだが、

import math
n = int(input())
k = int(input())
a = (math.factorial(n))%(10**9+7)
b = (math.factorial(k)%(10**9+7))
c = (math.factorial(n-k)%(10**9+7))
print((a*pow(b*c,10**9+5,10**9+7))%(10**9+7))

この逆元を使うやり方だとTLEし、

n,k = map(int,input().split())
cur = 1
for i in range(k+1,n+1):
  cur *= i
for j in range(1,n-k+1):
  cur = cur//j
print(cur%(10**9+7))

こっちの普通に掛け算をする方では通った なんで

多分n,kがそんなに大きくないときは、後者の計算量もそれほどではないのでこっちの方が速い(nCk自体の計算はkに依存するので)のではないかとか思ったけど、n=10**5,k = 100とかでも前者の方が速かった(し、後者に至っては間に合わない)ので何とも言えない

まあこういうケースもあるということを覚えておく



EDPC D,I

どっちもTLEだったけどPyPyにしたら通った  マジ?

PyPyを使うデメリットは分かってないけど、速いんだったらこっちの方がよくないですか

3/18 AtCoder(漸化式dp)

こんばんは。特に何もすることなく春休みが終わっていくことに嘆くとーです。

今日から解くに至った問題は記録しないことにします。めんどいので。

AGC031B

juppy.hatenablog.com

いつもお世話になっているじゅっぴーダイアリーを読んで、自分なりに考えたことをまとめる
類似の問題で取り上げられていた

Sの連続した部分列のうち、同じ文字が含まれない取り出し方は?

という問題の解き方は
①基本的に前の方から後ろに向けて、文字列を伸ばしていく
②今持っている文字列の中に、次に見る文字が含まれていなければ、(今持っている文字列の長さ+1)だけ足す
(例)
abcという文字列で、今見ている文字列がab、次に見る文字がcであれば、cはabの中に含まれていないので、cを付加することによりカウントされる文字列はc,bc,abcの3つ
③今持っている文字列の中に、次に見る文字が含まれていたら、文字列中のその文字が含まれなくなるまで文字列を短縮し、それから次の文字を入れ、(今持っている文字列の長さ+1)だけ足す
(例)
abcaという文字列で、今見ている文字列がabc、次に見る文字がaであれば、aはすでに文字列に含まれているので、aを落としてbcに縮め、それから再びaをくっつける。新たにカウントされる文字列はa,ca,bcaの3つ

を繰り返していくという感じ

この動きを管理する漸化式を立てるとき、
「これまでに見た文字列の中で、既出の文字がどのインデックスで出てきたか」を格納するリストが必要で、これと「一番最後に見た文字」を照らし合わせる

さらに、「今持っている文字列の一番最後のインデックスがどこにあるか」という情報も必要になる
これは、次に見る文字に対して新たに何個の文字列ができるかということを考えたとき、
①次の文字が、今見ている文字列の最後(インデックス的に言えば0に近い方)のインデックスよりも前のインデックスで一度以上出現していた→文字列に付加しても文字列が縮まることはない
②①ではない→その文字の所まで文字列を縮める必要がある

ということがあるからだ

だから、答えのコードに説明をつけると、

n = int(input()) #文字数
s = list(input())
mod = 10**9+7
def f(x):
    return ord(x) - 97
used = [-1]*26 #ここに文字ごとにその文字が使われた直近のインデックスが入る
tank = -1 #文字列の末尾を示す
res = 0
for i in range(n):
    res += (i - max(used[f(s[i])],tank))%mod #新たに増える文字列がいくつあるか
    tank = max(tank,used[f(s[i])]) #文字列の末尾を更新する(同じまま推移することもある)
    used[f(s[i])] = i #今見た文字の直近のインデックスを更新
print(res)


となる


これを今回のAGCのB問題に応用すると、

①隣り合っている同色の石は(隣り合っていること自体)無意味なので一つにまとめてよい
②i番目の石までの並べ方はdp[i] = dp[i-1]+dp[used[i]]とできる i-1番目までの色の並べ方に「i番目の石と同じ色の石で、最もi番目に近い石までの並べ方」を足せばよい理由は、その「最もi番目に近い石までの並べ方」をj番目とすると、「i~j番目の石をすべてその色で塗る」という行為で増える色の分=増やすべき要素数(逆に、これまでに登場しない色であれば、その間を塗ることで増える場合の数はない)となるからである

ということを使っていけばよい(②で考える分、類似問題のように「現在見ている文字列の、先頭に近い(ケツの)文字の情報」を保持しておく必要はない)

python3によるコード

N = int(input())
K = []
for i in range(N):
  K.append(int(input()))
L = [K[0]]
for j in range(1,N):
  if K[j] != L[len(L)-1]:  #ダブり解消
    L.append(K[j])
dp = [0]*len(L)
dp[0] = 1  #最初は1通りからスタート
used = [-1]*(max(L)+1)  #used[i] == iとする(1インデックスぽい)
used[L[0]] = 0  #リストの最初の数字を見た
for i in range(1,len(L)):
  if used[L[i]] == -1:
    dp[i] = dp[i-1]
  else:
    dp[i] = (dp[i-1]+dp[used[L[i]]])%(10**9+7)
  used[L[i]] = i
print(dp[len(L)-1])


ABC113D

あみだくじの問題
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは何通り作れますかという趣旨の問題


まず、この問題を解くうえで一番重要なのは、「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ

高さh、棒jに至る経路の総数をdp[h][j]とすれば、高さh-1からこの位置に至ることができるのは、棒j-1,j,j+1のいずれかしかない

さらに、そこに至る経路数というのは結局「ほかの棒にどんな風に架け橋(横棒)がかかっているか」の場合の数なので、それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある

例えば、dp[h-1][j]を見てみる これは、同じ棒から下ってくることを意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」ということである
つまり、この高さにおける横棒の架かり方というのは「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の二パターンしかないということになる

ある高さにおける横棒のかかり方も漸化式で求められる 高さhにおける(横一列にかけ橋が並んでいる状況を考える)、n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)
と書くことができる

これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである

だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、j-1本の棒の間にかかる橋の場合の数f(j-1)と、W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる これと同様に、残り二本に対してもいくつかければよいかを考えて、dp[h][j]]に対する漸化式を立てればよい

以下はpython3による解答

H,W,K = map(int,input().split())
dp = []
for i in range(H+1): #高さ0の分を余分に持っておく
  L = [0]*W
  dp.append(L)
fb = [1,1] #フィボナッチ(f(n)=f(n-1)+f(n-2))
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 #左端の棒の高さ0は初期位置なので1に
if W != 1: #棒が一本以上あるときは
  for i in range(1,H+1):
    for j in range(W): #棒が左端、右端、それ以外で場合分け
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7)) #高さH(一番下)、K-1番目の棒を調べる


EDPC H

迷路の経路の総数(右、下移動のみ)を求めるときにDPが使える

3/17 AtCoder(素因数分解)

こんばんは。昨日のAGCのショックでしばらく立ち直れなかったとーです。

AtCoder

解くに至った問題

AGC:031A
ARC:097C
Tenka1 Programmer Contest:C
CADDi 2018:C
codeFlyer:B


AGC031A

解き方はすぐ思いついたのですが、まず10**9+7で割ったあまりを問われていることに気づかず3回WA、さらに、もし26文字すべてが文字列の中に使われていたとすると、それらを選ぶ/選ばないの組合せが2**26通りあるので、これではO(10**8)くらいになって間に合わない

という感じで本番中にACできませんでした(実質解き方を思いついてない) 

2**26通りの組み合わせはいいんですけど、これって結局「何を何個使うか」の組合せでしかない
例えば、「120の約数は何個ありますか?」という問いかけに対して、馬鹿正直に120==(2**3)*(3**1)*(5**1)だから、2だけで構成されるのが何個、2と3で構成されるのが何個......みたいに数え上げる必要はない
2が使えるのは0,1,2,3個だから4通り、3が使えるのは0,1の2通り、5が使えるのは0,1の2通りだから約数は4*2*2=16個、と数えるのが普通だし、明らかに速い
というわけで、今回もこちらを使うべきである ただ、「一つも選ばない」という選択は出来ないので、その場合(1通り)を除くようにすれば、すぐに答えは求まる

bit全探索しか思いつかなかった 脳が凝り固まっている
制限時間内に解ける仕様になっているのだから、それを見つけるように努力する



天下一C

うまいことすれば3500**2のループで解けますって言われたから、普通に書いたらTLEした
通ったコードはこれ

N = int(input())
for n in range(1,3501):
  for w in range(n,3501):
    if (4*n*w-w*N-n*N) > 0:
      h = n*w*N/(4*n*w-w*N-n*N)
      if h == int(h) and h > 0:
        print(int(h),n,w)
        exit()

4行目で != 0としていたらダメだった 分母が負の値の時も律儀に計算することになるためである
だから>0とする必要がある


CADDi2018C

nを素因数分解するコード

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

計算量はO(n**0.5)

3/16 AtCoder(最長部分増加列)

こんばんは。生活リズムが完全に崩壊したとーです。

AtCoder

解くに至った問題

ABC:006D/035D
AGC:009A/013A/018A/021A

ABC006D

解説AC
LIS(Longest Increasing Subsequence)の問題

カードを挿入することで位置を変化させる必要がない部分は「前から見ていって増加している」ような部分である
カードを挿入する回数を最小にしたいので、その「増加する」列(飛び飛びでもよい)で、最も長いところを求めればよい(その長さを数字の個数から引けば終わり)

[例]
1,3,5,2,4,6
のLISは1,2,4,6


さて、その部分列の求め方を説明する といってもあんまり難しくない

1からNまでのN個の数字で構成された部分列を考える
まず、N個の∞をもったリストdpを用意する
ここでは、簡単に1,3,5,2,4,6という数列で説明を進める

dp = [float('inf')]*6

さて、dpの値を更新することを考える
dp[i]には(iは0インデックス)、部分列の長さがi+1になるような列で、その列の最後の数字で最も小さい数字が入る

例えば、上の例で言えば、

dp = [1,2,4,6,inf,inf]

となる

数列を前から見ていき、今見ている数列の要素がdpのどこに入るかを二分探索で調べる
こうすることで、例えば1,3,5まで見た時点ではdp = [1,3,5,inf,inf,inf]となっていたのが、次に2を見たら3の前に入ることが分かるので、その値を更新してdp = [1,2,5,inf,inf,inf]
→4を見たら5の前に入ることが分かるので、dp = [1,2,4,inf,inf,inf]
→6を見たら4の後ろに入るので、dp = [1,2,4,6,inf,inf]

となるようにアルゴリズムを組めばよい

以下はpython3による答えのコード

import bisect
N = int(input())
L = []
for i in range(N):
    L.append(int(input()))
dp = [float('inf')]*N
for i in range(N):
    k = bisect.bisect_left(dp,L[i])
    dp[k] = L[i]
endnum = bisect.bisect_left(dp,N+1)  #N+1は必ず、リストdpの「無限でない最小の要素」になる
print(N-endnum)


ABC035D

島を訪れるのは一つだけでよい(二つ以上滞在するのは時間食うし、それだったらポイントが多くなる方により長く滞在すればよい)ということを念頭に置き、島1から各頂点への最短経路をダイクストラで求める

今回注意すべきなのは「往復するコストが同じではない」ということ
なので、辺を格納するときは片道に限るということを念頭に置いておき、行きと帰りでダイクストラを二回やってそこまでの往復にかかる時間を計算し、各島の滞在時間を求め、ポイントが最大になるような島を選べばよい



AGC031

失敗 0完 2つTLEが取れなかった 反省します

3/15 AtCoder(巨大な数をある数で割ったときの余りを求める、順列)

こんにちは。肉を食べると確実に腹をこわすとーです。

AtCoder

解くに至った問題(7問)

ABC:012D/021D/030D/046D/047D/052D/073D

ABC030D

例えば、1234567890という数字の列が10**5回続くような巨大な数字(つまり10**6桁)を10**9+7で割ったあまりを突然求めたくなったらどうすればよいだろうか

素直にmodをとると馬鹿みたいに時間がかかるので、工夫をする必要がある

簡単な例として、1234を4で割ったあまりを考えてみる

桁が大きい方の数字から見ていけば、
1を4で割ったあまりは1

1*10+2=12を4で割ったあまりは、(1を4で割ったあまり*10)を4で割ったあまりと、2を4で割ったあまりの和(つまり、1*10+2=12≡0)

12*10+3=123を4で割ったあまりは、(12を4で割ったあまり*10)を4で割ったあまりと、3を4で割ったあまりの和(つまり、0*10+3=3≡3)

123*10+4=1234を4で割ったあまりは、(123を4で割ったあまり*10)を4で割ったあまりと、4を4で割ったあまりの和(つまり、3*10+0=30≡2)

となって、2と求まる
つまり、上から一桁ずつ見ていけば、桁数分のループを行うことで余りが正しく求まるということが分かる

これをコードにする(kは与えられた巨大な数を「文字列」として受けとる。こうして上から一桁ずつ見ていける)

k = input()
mod = 10**9+7
ans = 0
for n in map(int,k):
  ans = (10*ans+n)%mod
print(ans)


ABC073D

順列の求め方

例えばL=[1,2,3]の順列を求めたいと思ったら、

import itertools
K = list(itertools.permutations(L))

とすれば、

K = [(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)]

となる(K[1][2] == 2など指定もできる)

3/14 AtCoder

こんばんは。シャニマスにドはまりして一日つぶしたとーです。

解くに至った問題(2問)

AGC:006A
CODE FESTIVAL 2016 qual A:B


CODE FESTIVAL 2016 qual A B

同じものをまとめてくれるset()はリスト内の要素が変数やタプルの時のみ使えることに注意
例えば

L = [[1,2],[1,2],[3,4],[3,4]]

をまとめてほしいと思ってもまとめてくれないので、中身をタプルにする必要がある

3/13 AtCoder

こんばんは。花粉症でくしゃみと鼻水と目のかゆみの三重苦に悩まされているとーです。

AtCoder

解くに至った問題(8問)

ABC:070D/078D/089D
AGC:006B/008A,B/014B
キーエンスプロコン2019:C


今日は考察ゲーの問題ばかりで解説ACに逃げがちでした......

ABC070D
頂点、辺の数がそれぞれ10**5個ずつ与えられても、一個の頂点から各頂点に向かう最短経路を求める際にダイクストラ法を使えばなんとか間に合うという知見を得た(ln(10**5)が大体10くらいなので10**6のオーダーになる)

一か月のまとめ

こんばんわ。とーです。
二月からAtCoderに本腰入れて取り組み始め、一か月が経ちました。(とほぼ同時に50記事になったのでこの記事を書きました)
継続は力なりというのでしょうか、レートの伸びが目に見えて嬉しい限りです。

さて、この一か月(2/10~3/10)で、ABCのB,C問題を中心に198問解きました
f:id:saguh:20190312025823p:plain

そしてレートの推移がこちらになります
f:id:saguh:20190312025844p:plain


実は、この一年間で過去に競プロを始めようと思ったことが二回ほどあったのですが
一回目:四月初め。pythonの初心者向けの本を買ってやろうとするも、別にそれは競プロ用でもなんでもなく、標準入力を受け取るところでinf年時間を溶かし3日で断念
二回目:九月初め。夏の成績も出て八月はブルーになっていた気持ちも落ち着いてさて始めようかと思ったら、案外夏休みが短くて二週間しかできず、Aを埋めてBを1/3くらい解くので精一杯
みたいな状況でした

この一か月で、B問題で入力や単純な操作のメソッドを学び、C問題でアルゴリズムの典型例を学習してきました

A,B問題を全部解けば、基本的な操作は理解できると思うので割愛します

C問題,D問題を通して学んだアルゴリズムや操作、教育的な問題をまとめたいと思います



☆☆☆が「C解けるなら知ってて当然」、☆☆が「Cの中堅レベルで使える」、☆が「Dで威力を発揮する」くらいの大雑把な感じの分類です



アルゴリズム


☆☆☆累積和(いもす法)

二週間くらい前は扱いに一苦労でしたが、今は結構扱えるようになってきて使い勝手が良いです
累積和の強みとして、一回作ってしまえば部分区間の和(や積)をO(1)で求められるというところです
計算が間に合わねえ!って問題も累積和で解決するタイプが(特にCだと)多いです

いもす法はその派生です これは累積和より早くリストが作れます
「被覆区間を求める」タイプの問題で力を発揮します 

C - ハイスコア
C - 総和
C - Together
D - Candy Distribution
A - Zero-Sum Ranges


☆☆☆最小公倍数、最大公約数(ユークリッドの互除法

ユークリッドの互除法で最大公約数を求めるアルゴリズム

def gcd(x,y):    #x >= y
  while y != 0:
    k = x
    x = y
    y = k%y
  return  x

※最小公倍数を求めるときは、最小公倍数を求めたい数の組をa,bとし、最小公倍数をL、最大公約数をGとすれば、a*b == L*Gという関係が成り立つため、L = a*b/Gで求まる

C - Monsters Battle Royale


☆☆☆素数素因数分解、エラトステネスの篩、階乗の約数)

n以下の素数を列挙するアルゴリズム

def primes(n):
  ass = []
  is_prime = [True] * (n + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
      continue    
    for j in range(i * 2, n + 1, i):
       is_prime[j] = False
  for i in range(len(is_prime)):
    if is_prime[i]:
      ass.append(i)
 return ass

C - Factors of Factorial

☆☆☆全探索(10進法をn進法に直す)

効率的なやり方が思いつかない場合、全探索で求めてしまった方が安全な場合が多いです
計算量(全部で何通りあるかでよい)を確認し、10**6までだったら余裕で間に合うので、どんどんパソコン君に全探索を丸投げしましょう

10進法をn進法に直すアルゴリズム(NはN桁まで0埋めします)

def Base_10_to_n(X,n):
  if (int(X/n)):
    return Base_10_to_n(int(X/n),n)+str(X%n)
  return str(X%n)
for X in range(n**N):
  STR = Base_10_to_n(X,n).zfill(N)

D - Patisserie ABC
C - All Green
C - 755
C - Synthetic Kadomatsu
D - Simple Knapsack


☆☆☆漸化式によるDP

C - 柱柱柱柱柱
C - Strange Bank


☆☆二分探索

D - Lazy Faith
C - Snuke Festival


☆☆ワーシャルフロイド法、ダイクストラ
ワーシャルフロイド法

from scipy.sparse.csgraph import floyd_warshall  #呪文を唱える
n,m = map(int,input().split())   #nは頂点の数、mは辺の数
d = [[float("inf")]*n for i in range(n)]   #ここに辺の重さを格納
L = []
for i in range(n):
    d[i][i] = 0   #同じ頂点間は重さ0
for i in range(m):
    a,b,l = map(int,input().split())   #a,bは頂点(1インデックス)、lは重さ
    if a == 1:  #今回は始点が頂点1の辺は繋がない
        L.append([a,b,l])
    else:
        d[a-1][b-1] = l   #距離を格納(双方向)
        d[b-1][a-1] = l
d = floyd_warshall(d)   #最短距離を求める

ダイクストラ

import heapq
def dijkstra_heap(s):    #始点sから各頂点への最短距離
    d = [float("inf")] * n    #ここに始点sから各点への最短距離を格納
    used = [True] * n    #Trueは「最短距離が未確定」を意味する
    d[s] = 0    #始点sは当然距離0
    used[s] = False    #d[s]=0と確定したのでFalseに
    edgelist = []    #全部調べつくしたとき、このリストは空になる
    for e in edge[s]:   #edgelistに[重み,行き先]を入れる
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離(重み)のものを探す
        if not used[minedge[1]]:    #取り出した[重み,行き先]の「行き先」が、最短距離確定済み頂点なら
            continue     #引き返す(距離が無駄に増える)だけなので使わない
        v = minedge[1]    #行き先
        d[v] = minedge[0]    #距離(重み)
        used[v] = False    #「今」見た頂点はFalseにする
        for e in edge[v]:    #行き先から出る道[重み,行き先]の要素eに対して
            if used[e[1]]:    #行き先が「最短距離未確定」ならば
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])   #edgelistにソートしてぶち込む
    return d    #調べつくしたら、最短経路の入ったリストdを返す

n,w = map(int,input().split())   #nは頂点の数、wは辺の数を表す
edge = [[] for i in range(n)]    #edge[i]は、iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())    #x,yは頂点の番号、zは重み(距離)
    edge[x].append([z,y])
    edge[y].append([z,x]) 
print(dijkstra_heap(0))    #番号0の頂点からの最短経路を求める

C - 友達の友達
C - 正直者の高橋くん
C - Blue Bird
B - リモコン


☆☆Union Find(シンプル・サイズ付き)

シンプルなUnion Find

N,Q = map(int,input().split())   #N個の頂点(0インデックス)、Q個のクエリ
L = []
for i in range(Q):
    L.append(list(map(int,input().split())))
par = []
rank = []
for i in range(N):
    par.append(i)
    rank.append(0)
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
def same(x,y,par):
    return find(x,par) == find(y,par)

サイズ付きUnion Find

N,M = map(int,input().split())
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
L.reverse()
par = []
rank = [0]*N
size = [1]*N
for i in range(N):
  par.append(i)
def find(x,par):
  if x == par[x]:      
    return x
  else:
    return find(par[x],par)
def unite(x,y,par,rank,size):
  x = find(x,par)
  y = find(y,par)          
  if x != y:
    if rank[x] < rank[y]: 
      par[x] = y
      size[y] += size[x]
    else:
      par[y] = x
      size[x] += size[y]
      if rank[x] == rank[y]:
        rank[x] += 1
def same(x,y,par):
  return find(x,par) == find(y,par)

B: Union Find - AtCoder Typical Contest 001 | AtCoder
D - Decayed Bridges


☆しゃくとり法

C - 列

幅優先探索

C - 幅優先探索


深さ優先探索

C - One-stroke Path
D - Fennec VS. Snuke


☆逆元
nCk = n!/(k!*(n-k)!)を10**9+7で割ったあまりを制限時間内に求めるアルゴリズム

import math
n = int(input())
k = int(input())
a = (math.factorial(n))%(10**9+7)
b = (math.factorial(k)%(10**9+7))
c = (math.factorial(n-k)%(10**9+7))
print((a*pow(b*c,10**9+5,10**9+7))%(10**9+7))

C - 経路





操作編

☆☆☆スタック、キュー

from collections import deque
L = deque([1,2,3,4])
a = L.popleft()
a == 1
L.append(5)
L == deque([2,3,4,5])

☆☆リストのn番目でソート

L = sorted(L, key = lambda x:x[n])   #n番目(0インデックス)でソート

☆☆リストのコピー

L = [1,2,3,4,5]
M = copy.deepcopy(L)
M == [1,2,3,4,5]

☆小数点以下の四捨五入

fは四捨五入したい数digitは小数第何位で四捨五入したいかを表す

f,digit = map(float,input().split())
def my_round(f, digit):
    p = 10**digit
    return (f*p*2+1)//2/p

3/10 AtCoder(全列挙、ワーシャルフロイドを高速化する、幅優先探索で迷路を解く)

こんにちは。昨日緑に上がれなくて悔し涙で枕を濡らしたとーです。

AtCoder

解くに至った問題(5問)

ABC:007C/022C/028D/033C/114C


ABC114C
数字の中に3,5,7が一回以上出てくるような数字で、与えられた数よりも小さいものは何個あるのよ、という問題

数字を文字列みたいに扱って、3,5,7が一回以上出てくるようなものをサーチしてから、それをまた数に直して比較する、という二回の手続きを踏むので結構面倒

まず初めにとった戦略は、「既存の数の先頭や末尾に3,5,7をつけていって候補を増やしていく」というもの

しかしL = [357,375,537,573,735,753]というリストで作って増やしていった結果、どうにも答えと合わない

原因を探ったところ、こういう増やし方では、例えば3557のような数字が作れないというのが問題になっていた

次に、とりあえず3,5,7から作り始めて、先頭や末尾に3,5,7をどんどん追加していき、後でそれが条件を満たす(つまり、3,5,7が一回以上出てくる数字かどうか)を判断する方針をとった

しかし、これだと5秒近くかかってしまい結局TLEしてしまった

最終的な答えのコードはこうなった

N = int(input())
ans = 0
if N <= 356:
  print(0)
else:
  L = ['3','5','7']
  for i in range(len(str(N))-1):
    for j in range(len(L)):
      L.append(L[j]+'3')     #ここの操作は末尾につけるだけでよい
      L.append(L[j]+'5')
      L.append(L[j]+'7')
    K = list(set(L))
    ans = 0
  for i in range(len(K)):
    if K[i].count('3') > 0:
      if K[i].count('5') > 0:
        if K[i].count('7') > 0:
          if int(K[i]) <= N:
            ans += 1
  print(ans)

先頭につけるところを省略したら40倍近く速くなった。これは、既存の数の先頭に3,5,7をつける操作でできた数字は、末尾に3,5,7をつける操作でできる数字を含んだものだからである(結局setでダブりを解消することにはなるが、毎回6個の数字を作り出していたら、省略する手間は3個の時とは比べ物にならないくらい大きい)

この方針が通用したのは10**9以下にある七五三数があんまり多くない(その候補となりうる、3,5,7のみで構成された数字もあまり多くない)ためであった 場合の数を答えるような問題では、最終的な答えの数が小さいときは候補を全列挙してから、あとで解となりうるかを吟味する戦略がとれる




ABC022C

出発点と終着点が同じループの最短経路を求めましょうねという問題

解答は
①スタートに隣接する頂点は少なくとも二つある
②①のような条件を満たす頂点を二つ選んでくる
③②で選んだ頂点間の最短経路をワーシャルフロイドで求める(①のような頂点は辺から外せば、閉路が開路になるためこれが使える)
④②を全通り試す

という手続きを踏んでいた(自明な解法)

ただ、N <= 300なので間に合うか?という懸念があった(結局前回紹介したやり方だと間に合わず)

調べてみて、from scipy.sparse.csgraph import floyd_warshall という謎の呪文を唱えれば高速化できることが分かった

from scipy.sparse.csgraph import floyd_warshall  #呪文を唱える
n,m = map(int,input().split())   #nは頂点の数、mは辺の数
d = [[float("inf")]*n for i in range(n)]   #ここに辺の重さを格納
L = []
for i in range(n):
    d[i][i] = 0   #同じ頂点間は重さ0
for i in range(m):
    a,b,l = map(int,input().split())   #a,bは頂点(1インデックス)、lは重さ
    if a == 1:  #今回は始点が頂点1の辺は繋がない
        L.append([a,b,l])
    else:
        d[a-1][b-1] = l   #距離を格納(双方向)
        d[b-1][a-1] = l
d = floyd_warshall(d)   #最短距離を求める(追記を参照)

さて、

d = floyd_warshall(d)

の所だが、

d = floyd_warshall(d,directed = False)

とすると、上の方ではdirectedがTrue(デフォルト)になっているが、これは頂点iから頂点jに一方通行で向かう際の最短経路を計算してくれる一方で、下のdirected = Falseの方ではiからj、jからiの両方の最短経路を考慮してくれるという違いがある 今回の問題では、始点と終点を入れ替えることによる経路長の変化はないため、どちらを使っても問題はない

これを使うとなんとNが300の時でも余裕で間に合ってしまう  scipy恐るべし

docs.scipy.org
atcoder.jp



ABC007C

やる前から「うっわめんどくさそ~」ってなってやらなかった迷路の問題

というか、ほかの人のpython3の回答を見ても得られるものがなかったので、自己流でやるのがためらわれたというのもある

そろそろC埋めも佳境に差し掛かり、逃げてられないということで解きました


さて、解説に入る前に、僕はこの問題ACする前に2WA食らいました

原因ですが、問題文に書いてある解き方を見たとき、「あれこれダイクストラで使ったheapq使えんじゃね?」と思って使ったのが間違っていたためです

heapq.heappop(L)
heapq.heappush(L,a)

は、それぞれ意味が
「リストの最初をpop」
「リストにソートしてaを入れる」
ということなので、今回のように先入れ先出し(リストの先頭から使っていき、新しい要素はリストのケツに突っ込む)が求められるような状況では、後者の操作が勝手にソートを行うものなので、リストの順番がぐちゃぐちゃになり、都合が悪い(ありていに言えば使えない)ということになります
(ただ、この性質はダイクストラ法では使えるので、そちらはheapqを使ってあげる必要があります)

さて、pythonFIFO先入れ先出し)を実装する方法を説明します 今日はWi-fiの調子が悪く、パソコンの期限も悪かったためここで時間を食ったし、何より調べたサイトがどれもカス欲しい情報が載っていなかったしやけに小難しいのばかりで最悪な思いをしたので、簡潔、明瞭に書きたいと思います

まず

from collections import deque

という呪文を唱えます
こうすることで、リストのスタック、キューの操作が速くなります

リストは、普段例えば

L = [1,2,3,4]
M = [[1,2],[3,4],[5,6]]

のように書いているかもしれませんが
ここでは、

L = deque([1,2,3,4])
M = deque([[1,2],[3,4],[5,6]])

と書きます
リストの先頭から要素を取り出したいときは、popleft()を使います
例えば、上の状況では、

a = L.popleft()
b = M.popleft()

とすれば、

a == 1
b == [1,2]
L == deque([2,3,4])
M == deque([[3,4],[5,6]])

となります

また、末尾に要素を追加したい場合は、普通のリストと同じようにappendが使えます

L == deque([2,3,4])
M == deque([[3,4],[5,6]])
L.append(5)
M.append([7,8])

とすれば、

L == deque([2,3,4.5])
M == deque([[3,4],[5,6],[7,8]])

となります

www.smartbowwow.com
こちらのサイトを参考にさせていただきました ありがとうございました (やっぱり競プロのサイトに焦点を当てて調べると欲しい情報が手に入る)
☆pop()がなぜ遅いかもここに書いてあります 本当に勉強になる(popってO(n)なんですね)


以下はpython3による答えのコードです リストで座標を扱う時は、必ず(y,x)となる(リストの行が先に来る)ことを念頭に置きます

from collections import deque
R,C = map(int,input().split())
sy,sx = map(int,input().split())  #スタートの座標
gy,gx = map(int,input().split())  #ゴールの座標
L = []
for i in range(R):
  L.append(list(input()))   #迷路の情報を受け取る
dy_dx = [[1,0],[-1,0],[0,1],[0,-1]]   #移動
que = deque([[sy-1,sx-1]])   #queには次に見るべき座標が入る。括弧が二重になっていることに留意
L[sy-1][sx-1] = 0  #スタートの座標(迷路上)の情報を0に
while len(que) > 0:  #queが空でないときは
  cur = que.popleft()   #queの一番左を見る
  for i in range(4):  #現在見ているマスの上下左右をチェック
    if 0 <= cur[0]+dy_dx[i][0] <= R-1 and 0 <= cur[1]+dy_dx[i][1] <= C-1:  #移動した後も迷路内にあるかの確認
      if L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] == '.':  #まだ見ていない通路であれば
        L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] = L[cur[0]][cur[1]]+1  #現在見ているマスの手数+1を入れる
        que.append([cur[0]+dy_dx[i][0],cur[1]+dy_dx[i][1]])   #queの末尾に今チェックした座標を入れる
print(L[gy-1][gx-1])  #queが空になったら、ゴールの座標に書かれた数字(手数)を出力


python3でこの問題を解く人が参考にしてくれると嬉しい

3/9 AtCoder

こんにちは。えっちな音声を聞いてたら今日はバカ早く起きました。とーです。

AtCoder

解くに至った問題(9問)

ABC:013C/035C/057D/084C/099C/121A,B,C,D


ABC099C

以前は苦労して解けなかったけどいま見たらパッと「DPやん」って思いつくようになったのは成長なんでしょうか。しかし2回バグらせてたのでダメですね。
以下はpython3による答え

N = int(input())
dp = [0]*100001     #ここに手数をいれます
L = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
for i in range(100001):
    for j in range(len(L)):
        if 1 <= i+L[j] <= 100000:
            if dp[i+L[j]] == 0:     #リストの値が未更新なら
                dp[i+L[j]] = dp[i]+1     #参照したところから一手で飛べるとしておく
            else:     #リストの値が更新済みなら
                dp[i+L[j]] = min(dp[i]+1,dp[i+L[j]])       #更新済みの値と新たに参照したところから一手で飛んでくるののどちらがより手数が少ないかを判定
print(dp[N])

ABC121

全完しました
ヒィウィゴァ!ビ-ヒ-ロ-アイワナビ-ヒ-ロ-ホホンヒホヒホハハヘヘホw
       ∩
       \\
       /  )
⊂\_/ ̄ ̄ ̄  /
 \_/ ՞ةڼ◔(
   )    /⌒\
  /  ___/⌒\⊃
 (  /
  \\
   ∪
嬉しさのあまりBe a Hero!を踊るとー

3/8 AtCoder(ワーシャルフロイド法、ダイクストラ法、逆元)

こんにちは。心機一転して今日は8時に起きたとーです。

AtCoder

解くに至った問題(9問)

ABC:016C/021C/029C/034C
ARC:001A/015A/059C
AGC:005A/011A


ARC001A

以前解いたことがあったらしいけどとりあえずワーシャルフロイド法の勉強ということで

ワーシャルフロイド法は、ある2頂点を最短コストで行くにはどうすればよいかというのを、頂点の数をnとしてO(n**3)で計算してくれるアルゴリズム だからpython3で競プロやるときはn <= 100くらいが実用的かしらん

リストdを用意する このリストdには、n個の要素を持ったリストがn個あり、d[i][j]は、頂点iから頂点jに行くのにかかる最短コストを表す

リストの更新方法だが、単純な3重ループであり、d[i][j]を求めるのであれば、現在入っている最短コストの候補d[i][j]と、頂点kを介していく経路のコストd[i][k]+d[k][j]を比較し、コストの小さい方を採用していくというのを繰り返していく

一般的なコードは以下の通りになる

def warshall_floyd(d):     #d[i][j]は、iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,w = map(int,input().split())     #nは頂点の数、wは辺の数
d = [[float("inf") for i in range(n)] for i in range(n)]    #d[i][j]は辺ijのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())    #x,yは頂点、zは辺のコスト
    d[x][y] = z      #双方向のコストを更新
    d[y][x] = z
for i in range(n):
    d[i][i] = 0      #自身のところに行くコストは0
print(warshall_floyd(d))

この問題では、dの各要素を温度に見立て、±1,±5,±10の温度に対しコスト1の辺を伸ばしていく


以下はpython3による解答

s,e = map(int,input().split())
def warshall_floyd(d):    #d[i][j]はiからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n = 41     #頂点(温度)の数は0~40の41個
d = [[float("inf") for i in range(n)] for i in range(n)]   #d[i][j]は辺ijのコスト(存在しないときはinf)
CL = [1,5,10,-1,-5,-10]     #リモコンで調節できる温度
for i in range(n):
    for j in range(6):
        if 0 <= i+CL[j] <= 40:     #0度以上40度以下であれば
            d[i][i+CL[j]] = 1     #コストを更新
            d[i+CL[j]][i] = 1
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは0
warshall_floyd(d)
print(d[s][e])

ちなみにABC016Cもワーシャルフロイド法を使う問題です こっちもやっておくとよいかも

じゅっぴーダイアリーを参考にさせていただきました ありがとうございます
juppy.hatenablog.com



ABC021C

ワーシャルフロイド法だと計算が間に合うかな?と心配になったので、ダイクストラ法の勉強をする

ダイクストラ法は、ワーシャルフロイド法同様に「ある地点から別の地点への最短経路を求める」ことを可能にしてくれるが、ワーシャルフロイド法と比較して、
①計算が速い(辺の数をE、頂点の数をVとしてO(ElogV))
②距離(移動の重み)が負の数だと使えない
③結構複雑
という特徴を持っている

仕組みとしては、ワーシャルフロイド法のように全部の頂点同士をマッチングさせるのではなく、必要な部分だけを扱っていくようになっていて、
①始点を見る
②始点を訪問済みにする、以下、訪問済みにした頂点はもう訪れない(もう一度訪問済みの頂点に戻るのは、距離(重み)が非負である以上は無駄なので)
③始点と隣り合う頂点を、最短経路で訪れたとしてそこまでの経路を更新する。そのうえで、[距離(重み)、行き先]の要素を、配列に「距離でソートして」入れていく
(この更新は、リストのソートとともに行われるため、距離(重み)が小さい方から必ず使われるので、必ず最短のものを選ぶことになり、複数の候補の比較がいらない)
④②と③の操作を、始点を移しながら、訪問済みの頂点がなくなるまで続ける

という感じ


コードを見ながら確認する
heapの仕様だが、Lをリストとして、
①heappop(L)でリストから先頭の要素を削除 
②heappush(L,n)でリストにnを(ソートしたうえで)追加
となっている

import heapq
def dijkstra_heap(s):    #始点sから各頂点への最短距離
    d = [float("inf")] * n    #ここに始点sから各点への最短距離を格納
    used = [True] * n    #Trueは「最短距離が未確定」を意味する
    d[s] = 0    #始点sは当然距離0
    used[s] = False    #d[s]=0と確定したのでFalseに
    edgelist = []    #全部調べつくしたとき、このリストは空になる
    for e in edge[s]:   #edgelistに[重み,行き先]を入れる
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離(重み)のものを探す
        if not used[minedge[1]]:    #取り出した[重み,行き先]の「行き先」が、最短距離確定済み頂点なら
            continue     #引き返す(距離が無駄に増える)だけなので使わない
        v = minedge[1]    #行き先
        d[v] = minedge[0]    #距離(重み)
        used[v] = False    #「今」見た頂点はFalseにする
        for e in edge[v]:    #行き先から出る道[重み,行き先]の要素eに対して
            if used[e[1]]:    #行き先が「最短距離未確定」ならば
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])   #edgelistにソートしてぶち込む
    return d    #調べつくしたら、最短経路の入ったリストdを返す

n,w = map(int,input().split())   #nは頂点の数、wは辺の数を表す
edge = [[] for i in range(n)]    #edge[i]は、iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())    #x,yは頂点の番号、zは重み(距離)
    edge[x].append([z,y])
    edge[y].append([z,x]) 
print(dijkstra_heap(0))    #番号0の頂点からの最短経路を求める


この問題では、単に始点aからの最短経路を求めただけでは答えにならず、始点aから終点bに至るまでの最短経路の「数」を求める必要がある
ということで、結局ダイクストラ法を使うとはいえ、全頂点に対し、始点から各頂点への距離を出さないといけない

最短経路の数を求める時は動的計画法を使う やり方は、まずリストdpを要素の数だけ0埋めし、始点a(ここでは0インデックスなのでdp[a-1])を1にする
それから、dp[0]~dp[n-1]までリストの要素を更新していく 各kについてdp[k]の更新方法を述べる

どうするかというと、まず0~n-1のjに対し、とりあえずdp[a-1][j]が0以上n-1以下のiであるかどうかを判定する そして、dp[a-1][k] == i+1であれば、最短経路ならば当然dp[j][k] == 1となっているはずである(a-1→j→kと移ってくれば、a-1からjのコストはi、jからkのコストは1になるはず)
これを満たすようなjとkに限り、dp[k]がdp[j]+dp[k]として更新される

以上を繰り返すことで、終点bに至る経路数がdp[b-1]として出る(今回は10**9+7で割ったあまりを出すように言われているので、更新のたびに10**9+7で割っている)



以下はpython3による解答

import heapq
def dijkstra_heap(s):
    d = [float("inf")]*n
    used = [True]*n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n = int(input()) 
a,b = map(int,input().split())
M = int(input())
edge = [[] for i in range(n)]
for i in range(M):
    x,y = map(int,input().split())
    edge[x-1].append([1,y-1])
    edge[y-1].append([1,x-1]) 
L = []
for i in range(n):
    D = dijkstra_heap(i)
    L.append(D)
dp = [0]*n
dp[a-1] = 1
for i in range(n):
    for j in range(n):
        if L[a-1][j] != i:
            continue
        for k in range(n):
            if L[a-1][k] == i+1 and L[j][k] == 1:
                dp[k] = (dp[k]+dp[j])%(10**9+7)
print(dp[b-1])

juppy.hatenablog.com

こちらもじゅっぴーダイアリーにお世話になりました。ありがとうございます。




ちなみに、この問題をワーシャルフロイド法とダイクストラ法の二通りで解いたところ、ダイクストラ法の方が10倍近く速かった(いずれも間に合った)




ABC034C

なんだかんだ言って放置してたアレ 
簡単に言うと(H+W-2)!を(H-1)!*(W-1)!で割って10**9+7で割るとどんなもんよって話

10**9+7で割る操作は、足し算掛け算なら項ごとにやってもよい(まあ引き算もそうだけどあんまり使わないし、pythonは正しく計算してくれるらしいけど言語によってはうまくいかないこともあるので)
ただ、割り算に関しては、a/bをkで割ったあまりがc = a(modk),d = b(modk)としてc/dをkで割ったあまりと等しくなるとは限らないのでちょっと厄介

a÷b == a*(1÷b) (modk)

となることを用いる

1÷b (modk) はb**(-1) (modk)とも書かれ、これは逆元という(つまりbをかけるとkで割ったあまりが1になるような数)
だから、b**(-1)さえわかれば、aをbで割ったものをkで割ったときの余りは、aに(b**(-1))をかけたうえでkで割ったときの余りと等しく、つまりは掛け算と同じ形で扱えるようになる

さて、M = 10**9+7と置く Mは素数なので、フェルマーの小定理から、Mの倍数でない数bに対して、

b**(M-1) ≡ 1 (modM)

が成り立つ
ここから、

b**(M-2) ≡ b**(-1) (modk)

となり、

(a÷b)%M == (a*(1÷b))%M == (a*(b**(M-2)))%M == (a%M) * (b**(M-2)%M))

と計算される

さて、そこまでわかれば、割り算を掛け算と同じように扱えるようになったので好き放題してよい

分子は1からH+W-2まで、掛け算→Mで割ったあまりにする、というのを繰り返し
分母は1~H-1,1~W-1をかけてMで割ってを繰り返して計算した後、


(分子)* (((分母)** (M-2))%M) を計算し、これをMで割ったあまりをだせば、TLEすることなく答えが出る(TLEするのは、階乗の愚直な割り算にめっちゃ時間がとられるためなので)

(ここで割と大事なのは、掛け算した結果を割っても、余りには何ら影響がないということだったりする)


atcoder.jp