こんにちは。昨日緑に上がれなくて悔し涙で枕を濡らしたとーです。
解くに至った問題（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恐るべし
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]]) #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でこの問題を解く人が参考にしてくれると嬉しい
