こんにちは。昨日緑に上がれなくて悔し涙で枕を濡らしたとーです。
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())
d = [[float("inf")]*n for i in range(n)]
L = []
for i in range(n):
d[i][i] = 0
for i in range(m):
a,b,l = map(int,input().split())
if a == 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を使ってあげる必要があります）
さて、pythonでFIFO（先入れ先出し）を実装する方法を説明します 今日は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]])
L[sy-1][sx-1] = 0
while len(que) > 0:
cur = que.popleft()
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
que.append([cur[0]+dy_dx[i][0],cur[1]+dy_dx[i][1]])
print(L[gy-1][gx-1])
python3でこの問題を解く人が参考にしてくれると嬉しい
