こんばんは。シャニマスにドはまりして一日つぶしたとーです。
解くに至った問題(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]]
をまとめてほしいと思ってもまとめてくれないので、中身をタプルにする必要がある
こんばんわ。とーです。
二月からAtCoderに本腰入れて取り組み始め、一か月が経ちました。(とほぼ同時に50記事になったのでこの記事を書きました)
継続は力なりというのでしょうか、レートの伸びが目に見えて嬉しい限りです。
さて、この一か月(2/10~3/10)で、ABCのB,C問題を中心に198問解きました
そしてレートの推移がこちらになります
実は、この一年間で過去に競プロを始めようと思ったことが二回ほどあったのですが
一回目:四月初め。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で求まる
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
☆☆☆全探索(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
☆☆二分探索
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 - 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))
操作編
☆☆☆スタック、キュー
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
こんにちは。昨日緑に上がれなくて悔し涙で枕を濡らしたとーです。
解くに至った問題(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でこの問題を解く人が参考にしてくれると嬉しい
こんにちは。えっちな音声を聞いてたら今日はバカ早く起きました。とーです。
解くに至った問題(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!を踊るとー
こんにちは。心機一転して今日は8時に起きたとーです。
解くに至った問題(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])
こちらもじゅっぴーダイアリーにお世話になりました。ありがとうございます。
ちなみに、この問題をワーシャルフロイド法とダイクストラ法の二通りで解いたところ、ダイクストラ法の方が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するのは、階乗の愚直な割り算にめっちゃ時間がとられるためなので)
(ここで割と大事なのは、掛け算した結果を割っても、余りには何ら影響がないということだったりする)
こんにちは。成績の事が気になりすぎて昨日はほとんど眠れなかったとーです。
成績が出て、二年への進級が確定しました。\エライ/
累計したところ、
優上5
優28
良12
可3
で、平均は81強くらいになりそうです なんとか理情への道をつなぎました
あとは2Sでもうちょっと頑張ってできるだけ平均を伸ばしたいです
振り返り
英語
必修は全部優、総合もタームの方は良でしたがセメスターの方は優が来ました まあそれなりに頑張ったのでよかった
チャイ語
1Aも優でした 欲を言えばもっと欲しかったんですけど
数学
1Aは全部優以上が来て自分でも驚いています それだけに1Sの失点がめちゃくちゃ惜しい
理科系必修
構造化学も電磁気も良 電磁気はしかたないとして構造化学良ってマジですか.............................................そうですか...............................................一番頑張った科目なのになあ
総合
言語応用論は優上が来ました 嬉しい アルゴは良 それはそう
とは思いませんか?(強引)
数列の部分和に関する問題って、ABCのC,DとかAGCのA,Bとか、まあまあ結構な頻度で出ているので、問題とその解き方をまとめておこうと思い立った
主に累積和やしゃくとり法などについてまとめる
AGC023A
A - Zero-Sum Ranges
問題文
長さNの整数列Aがあります。Aの空でない連続する部分列であって、その総和が0になるものの個数を求めてください。 ただし、ここで数えるのは部分列の取り出し方であることに注意してください。つまり、ある2つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。
例えば、
1 3 -4 2 2 -2
の中の、総和が0になる部分列は
(1,3,-4),(-4,2,2),(2,-2)の3つですよって話
答え
累積和を計算し、その和が共通の部分に着目する
先ほどの例での累積和を計算すると、(初項は何も足さないという意味で0にする、これは「初項からの和を選ぶ」というために重要な操作)
0 1 4 0 2 4 2
である
この部分和の数列で、値が等しいところを二つもってくれば、その間の和は(なにも増えていないので)0になる だから、答えは同じ累積和となる場所の選び方に等しい(0,2,4はそれぞれ1組ずつ選べるので、計3通りになる)
以下はpython3によるコード
N = int(input()) A = list(map(int,input().split())) R = [0] #Rは累積和を格納するリストです for i in range(N): R.append(R[i]+A[i]) #累積和を入れます R.sort() R.append(10**18) #カウントを止めます(番兵) cnt = 1 ans = 0 cur = R[0] #curは今見ている累積和を表します for i in range(1,N+2): #番兵の所で止まるように、N+1まで数えます if cur == R[i]: cnt += 1 #curと新たに見たR[i]が等しければインクリメント else: ans += cnt*(cnt-1)//2 cur = R[i] #違っていたら、curをR[i]に更新 cnt = 1 #cntを1に戻す print(ans)
ABC037C
C - 総和
問題文
長さNの数列 {a_i}と1以上N以下の整数Kが与えられます。この数列には長さKの連続する部分列がN-K+1個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。
例えば、N==5,K==3であれば、
1 2 4 8 16
という数列の中に、長さ3の部分列は(1,2,4),(2,4,8),(4,8,16)の3つがあり、これらの総和は7+14+28=49となる
答え
普通に和を計算してると、Kが大体N/2くらいだった時に、その部分を計算するのでO(N)、さらにそれをN/2回やることになりさらにO(N)でO(N**2)となり、N==10**5ではさすがに間に合わない
累積和を使うことで、計算をO(N)まで落とすことが可能(累積和を計算しておけば、K項間の和は一回の引き算で求まるため)
以下はpython3によるコード
N,K = map(int,input().split()) L = list(map(int,input().split())) R = [0] #累積和を格納します ans = 0 for i in range(0,N): R.append(R[i]+L[i]) for j in range(N-K+1): ans += R[j+K]-R[j] #K項離れた累積和の差が加算されます print(ans)
ABC105D
D - Candy Distribution
問題文
N個の箱が左右一列に並んでおり、左からi番目の箱にはA_i個のお菓子が入っています。あなたは、連続したいくつかの箱からお菓子を取り出してM人の子供たちに均等に配りたいと考えています。そこで、以下を満たす組(l,r)の総数を求めてください。
例えば、4 1 5という入力が与えられて、M == 2であった場合は、
(4)と(4,1,5)という二組が、2の倍数になる
答え
累積和と同じ要領で、i番目までの和をMで割った余りを保持しておく
そして、その余りが等しいものを選べば、その間にある項の総和はMでわった余りが0になる
以下はpython3によるコード
N,M = map(int,input().split()) L = list(map(int,input().split())) L.insert(0,0) #Lの先頭に0(Mで割った余りが0)をいれた for i in range(1,N+1): L[i] = (L[i-1]+L[i])%M #累積和を計算する所を、Mで割るように変更 L.sort() p = L[0] cnt = 1 ans = 0 L.append(0) for i in range(N+1): if L[i+1] == p: #あとは同じ数字の組を数える cnt += 1 else: if cnt == 1: cnt = 1 p = L[i+1] else: ans += (cnt)*(cnt-1)//2 cnt = 1 p = L[i+1] print(ans)
ABC032C
C - 列
問題文
長さNの非負整数列S=s1,s2,...,sNと整数Kがあります。 あなたの仕事は、以下の条件を満たすSの連続する部分列のうち、最も長いものの長さを求めることです。部分列の長さは1以上の列でないといけません。
もし条件を満たす部分列が一つも存在しないときは、0を出力してください。
答え
しゃくとり法を使う
注意すべきことは2/28の記事に大体書いてあります
以下はpython3によるコード
N,K = map(int,input().split()) L = [] for i in range(N): L.append(int(input())) startindex = 0 #最初はスタートとエンドの番号が0になっています endindex = 0 length = 0 #ここで尺取り虫の長さを管理します mul = 1 #積を管理します ans = 0 #最終的な答えです while startindex <= N-1: #スタートがまだ数列の終わりに無い時の話です if 0 < mul <= K: #積が0より大きくK以下であれば if endindex < N: #エンドインデックスを考慮して if mul*L[endindex] <= K: #エンドインデックスを掛けて良いなら mul = mul*L[endindex] #掛けます endindex += 1 #エンドインデックスを+1して length += 1 #尺取り虫の長さを1増やします if ans < length: ans = length #答えを更新するかの判断 else: #エンドインデックスが掛けられないなら if startindex == endindex: #スタートとエンドが同じなら startindex += 1 #スタートとエンドを1つずつずらします endindex += 1 else: #スタートとエンドが違うなら mul = mul//L[startindex] #スタートで割ります startindex += 1 #尺取り虫が後ろの方から進みます length -= 1 else: startindex = N #エンドインデックスが数列の終わりまで来たので、これ以上伸ばしません elif mul > K: if K != 0: mul = mul//L[startindex] startindex += 1 length -= 1 else: #K==0という特殊な状況を考えます L.sort() #リストの中に0があるかを探すためにソートします if L[0] != 0: startindex = N ans = 0 #Kが0であるうえ、リストの中に0がないなら用無しです else: startindex = N #0があれば任意の長さでOKなので打ち切ります ans = N else: #積が途中で0になってしまったら、Kが任意の値であっても数列は任意の長さが取れます ans = N startindex = N print(ans)
こんにちは。今日も昼過ぎに起きました。とーです。
解くに至った問題(7問)
ABC:019B/025B/038C/047B/068D/105D
ARC:022B
ABC105D
また部分数列の問題 部分和でMで割った余りが0になるようなところはいくつありますかってのを求める
結局、これも累積和を計算し、あるところとあるところの累積和を引いたものをMで割ると0になるならば(つまり、二つの累積和はMで割った余りが等しい)、その間の累積和はMで割り切れますよということを使ってやっていく
累積和と言っても、Mで割ったあまりのみが気になるので、累積和を計算する過程でMで割る操作をすれば、勝手にM以下の数字に変換される
あとは、余りが同じものの数を数え、そこから2つ選ぶ場合の数を計算して足し合わせれば答えになる
解けなかった問題
ABC:098D/106D/118D
こんばんは。昼過ぎに起きて人生が終了しがちです。とーです。
AtCoder
解くに至った問題(1問)
ABC:120D
ABC120D
島の間に橋が架かっていて、これを一本ずつ落としていったら、いくつかの橋を使って互いに行き来できなくなる島のペアの数を列挙していこうねっていう趣旨の問題
昨日の記事に思考の流れを書いた通り、UF木を扱ううえで「枝を切る」という操作はやりにくい(というか実装法を知らない)ので、逆に後ろの方から橋を架けていくというやり方を採用していく
さて、橋を架けるという操作を扱う時、この問題で考えなければならないのは「橋を架けることで新たに行き来可能になる島は何通りあるか」ということである
結論から言ってしまえば、
①橋を架けた島同士が、UF木で同じ根を持っていた場合(つまり同じグループ)、新たに行き来できるようになる島はない
②橋を架けた島同士が、UF木で違う根を持っていた場合、新たに行き来できるようになる島のペア数は、その根を持つ島(繋いだ島と同じグループに属する島)の数を掛け合わせたものになる(例として、根1に島が二つ(ア、イ)、根2に島が3つ(ウ、エ、オ)属していたら、イとウをつなぐことで、この二つの島を介してア、イ、ウ、エ、オは全て行き来できるようになり、新たに行き来できるようになった島のペア数は2*3 == 6)
この二つだけを念頭に置けばよい
問題を解くうえで、「根に島がいくつ属しているか」という情報が必要になる
今回はsizeという値で管理することにする sizeは、最初どの島も1を持っているが、UF木で言うところのuniteの操作をするたびに、吸収した側の島の値に、吸収された側の根のsizeを加えていくことで、共通の根を持つグループの要素数を管理することができる
以下にコードを書いていく
まずは入力N,Mと橋の情報を格納するリストL、そしてサイズ付きUFの実装を行う
N,M = map(int,input().split()) L = [] for i in range(M): L.append(list(map(int,input().split()))) L.reverse() #橋が0の状態から架けていくので、リストを逆順にする(この順番で橋を架けていく) par = [] rank = [0]*N size = [1]*N #サイズの情報を加えたUFを作っていく 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): #ここもsizeを加えて改良する x = find(x,par) y = find(y,par) if x != y: if rank[x] < rank[y]: par[x] = y size[y] += size[x] #sizeの変更方法は上で説明した通り 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)
ここから、「入力で与えられた島をつなげると、新たに行き来できる島の組がいくつできるか」を調べていく 数え方は上で述べた
res = [] #ここに「新しく行き来できるようになった島のペア数」を保管する for i in range(M): A = find(L[i][0]-1,par) #入力は0インデックスに注意 B = find(L[i][1]-1,par) if A == B: res.append(0) #同じ根を持っていたら新たに行き来できる島のペアは増えない resに0を入れる else: res.append(size[A]*size[B]) #違う根であれば、sizeで保管した要素数を掛け合わせる unite(A,B,par,rank,size) #ペア数をresに入れたら、島同士を結ぶ ans = 0 for i in range(M): ans += res[M-i-1] #行き来できるようになった島を数えたので、逆順に出力すれば「橋を落とすことで行き来できなくなる島の数」になる print(ans)
今回もじゅっぴーダイアリーを参考にさせていただきました はてな記法の件もこの場を借りてお礼を申し上げます ありがとうございました
juppy.hatenablog.com
テスト
N,Q = map(int,input().split()) 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(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)
ここまではOK
A,B,C = map(int,input().split()) if B//A >= C: print(C) else: print(B//A)
こんにちは。金恋GTのグランドエンディングまで見て涙したオタクです。いやーよかった.........................................................................................................................................................................................................................................................................................................................................................。
解くに至った問題(7問)
ABC:042B/075B,C/120A,B,C
AGC:007A
ABC075B
グリッドを操作する苦手なタイプの問題。放置しまくってました。
結局、難しいところは「周囲八方向が'.'か'#'かを確認する際の例外処理」に集約されると思われる
例えばグリッドの外周であれば多くても五か所(角に至っては三か所)だけを調べればよいが、周りにほかのマスがある場合は八か所全部調べないといけない、といったことを、いちいち場合分けして処理するのが面倒くさいというところを解消したい
で、そういう時に「あらかじめ移動する方向の差分のリストを持っておく」というのが便利である
例えば、
dx = [0,0,1,1,1,-1,-1,-1]
dy = [1,-1,1,-1,0,1,-1,0]
としておけば、(dx[k],dy[k])をそれぞれx方向、y方向の移動と捉えることで、8通りすべて賄うことができる
さらに、例外処理は面倒なので、全八通りを出したうえで、
①(調べるマスの行番号)+dy[k]が0未満、もしくはH以上であれば調べない
②(調べるマスの列番号)+dx[k]が0未満、もしくはW以上であれば調べない
とすれば、実質的に例外処理をしたことと同じになる
全方位を探索するのに、こういう工夫ができると楽
また、昨日もちらっと書いたが、例えば
L = [['A','B','C'],['D','E','F'],['G','H','I']]
というリストを
ABC
DEF
GHI
と出力したい場合は、
for i in range(3):
for j in range(3):
print(L[i][j],end = '') #行ごとに改行なしで出力
print() #一行出力しきったら改行
とすればよい
AGC007A
与えられた模様が右、下の移動のみで進んでいけるかどうかを判定する問題
右に行けば列番号が1、下に行けば行番号が1増えることから、結局(1,1)から(H,W)に移動するまでの間にH+W-2回の移動する必要がある
(1,1)にも模様'#'がついていることを考えれば、全体で'#'の数を合計するとH+W-1になるので、これが与えられた情報と合致するかを判定すればよい
ABC042B
文字列を辞書式に並べてつなげて出力する問題
文字列の比較は不等号でできて、小さいほうが辞書で先に出てくる方になる(それはそう)
解けなかった問題
ABC:120D
ABC120D
見た瞬間「UF木やんけ!」と思ったものの与えられる橋の情報が多く、それだけで逐一確認していくのは不可能だと判断
次に「あれ、逆順から島をつなげていって、行き来できる島を数えていけばよくね?」と考えたものの実装できず
サイズ付きのUF木なるものがあるらしい これはrank(木の根っこ)の情報に加えて、各要素が所属するグループの全要素数の情報を付与したもの
これがあれば、
①島同士が最初から同じグループに所属していた→島をつなぐ作業により新たに行き来できる島はないため+0
②島同士が別グループに所属していた→島をつなぐ作業によって新たに行き来できる島は(今連結した島を含め)その島同士が所属するグループの全要素数に等しいので、答えにグループの要素数の積を足す、そして、そのグループ同士をuniteでくっつける
結局これをM回繰り返せばよくなり、時間的には間に合う
明日実装してみます サイズ付きUF木を学習する
ウニ
アリア鳥取れました うれしい
Warcry地帯は擦ったら全ピカしました 最近擦りに自信がつき始めています
この曲、とにかく巻き込みやすいから大変だし、それだけじゃなくてラストのフリックも地味に抜けやすくてなかなか手こずる奴でしたが鳥取れて感無量でした
そろそろ15.5も見えてきそうなので、上位の曲を練習していきたいです
こんにちは。一時に寝たのに起きたら十二時になっていて自分の体のポンコツさを実感しています。とーです。
解くに至った問題(10問)
CADDi 2018 for Beginners:B
全国統一プログラミング王決定戦 エキシビション:B
CODE FESTIVAL 2017 qual A:B
CODE FESTIVAL 2017 qual C:B
AGC:017A
ABC:021B/026C/104C/107B/119C
CODE FESTIVAL 2017 qual A B
N行M列のオセロみたいに、石が全部白を表にしておいてあり、白黒を反転させることができる 黒の数を与えられた数と等しくできますか?という問題
行をひっくり返すことをk回、列をひっくり返すことをl回やったとすると、黒が表を向いている石の数は
k*(M-l)+l*(N-k)
となる
なぜなら、k*(M-l)はk回分の行のひっくり返しをしたうえで(この時ひっくり返した行はすべて黒)、l回のひっくり返しをしていない列を選ぶ(ひっくり返した列を選ぶとまた白に戻ってしまう)場合の数と等しいからである(l*(N-k)も同じ)
んで、これが与えられた数と等しくなるかを全探索すればよい(N,K<=1000なので間に合う)
ABC107B
Grid Compression
列や行を圧縮できるところまで圧縮しましょうねという問題
愚直に列や行を取り除いて圧縮するアルゴリズムを考えていたけど、ちょっとそれは厳しいかなーと思い答えを見たところ、
「'#'が含まれる行、列をマークしておき、その行と列が交差する部分に存在する要素のみが残る」
とのこと
実際それはそうという感じで、マークがつかない→列or行がすべて'.'で構成されているため当然取り除かれるし、交差しているところは行で取り除く作業にも列で取り除く作業にも引っかからないから取り除かれない
考え方はこれでよいので、あとは実装を頑張る
行と列の数だけFalseで埋めたリストを持っておく
row = [False]*H
col = [False]*W
リストL[i][j]が'#'であれば、row[i] = True, col[j] = Trueとしてあげれば、その部分は交差しているのでOK(つまり、i行目とj列目は取り除かれない)
それが終わったら、今度はTrueになっている各行に対し、その行の中で列リストがTrueに代わっている成分だけをprintするようにしてあげればよい
列の改行はいらないが、行ごとの改行はいるので、そこに注意しながら出力する
(改行がいらないときはprint(なんちゃら,end = '' )とすればよいし、改行がいるときはprint()と下に添えればよい)
True/Falseで管理する便利さをまた一つ実感した
ABC021B
最短経路か否かを判定する問題
重みの無い経路における最短経路は閉路(同じところを二度以上通ること)がない(だから、現れる頂点はユニーク)ということに注意すればよい
ABC026C
木構造のようになった上司、部下の関係から、トップの人の給料を求めようという趣旨の問題
あれ?UF使えそう?とか思ったけど、木構造かつその構造が下にどんどん広がっていってよいということから、UFとはちょい違う実装をしなければいけない
やってみたがちょっと厳しそうだったので断念 解説ACをしました
肝心なところは、「自分の社員番号よりも社員番号の小さい人しか上司になれない」ということ
だから、番号を逆順に辿っていくことで、最終的にトップの人が求まればよい
考え方は以下の通り
まず、i番目に社員番号i+1番の人の給料、直属の部下を入れるリストPay_Subを作る
例えば(トップ含め)7人であれば、
Pay_Sub == [[1,],[1,],[1,],[1,],[1,],[1,],[1,]]
みたいな感じ
そして、部下の情報を入れていく
入力が
1
1
2
2
3
3
みたいな感じであれば、
Pay_Sub == 1,[1,2,[1,[3,4]],[1,[5,6]],[1,],[1,],[1,],[1,[]]]
のように入る
そして、リストの中を逆順に見ていき、
len(Pay_Sub[i][1]) != 0のとき(つまり部下がいる場合)、
新たに作ったリストに部下の給料を入れていき、そのmax,minを調べてPay_Sub[i][0](社員番号i+1番の人の給料)を更新、というのを、iがN-1から0までやればよい
そして、最終的にPay_Sub[0][0]が答えとなる
ABC119C
本番中にACできなかった問題
竹がN本あれば、一本の竹につき、Aに使う、Bに使う、Cに使う、使わないの4パターンがあり、それを全探索すればよい N<=8なので多くても65536通りになり間に合う
また、竹をつなげてから伸ばしたり縮めたりすることと、一本一本の竹を伸ばしたり縮めたりしてからそれらの竹をつなげる作業は等価なので、今回は簡単な「全部繋げてから差分を伸ばす、縮める」でやるのがよさそう
竹をどこに使うかの全探索のやり方が分からず(解説には再帰を使ってやる手法が書いてあったけどこれが思いつくほど精進を積んでない)、0から4**Nを4進法で表し、それぞれの桁を竹一本一本に割り当て、(無から有を生やすことは出来ないので、最低一つの竹をA,B,Cに使うことに注意)0だったら使わない、1だったら竹Aに使う......みたいな感じでやり、このやり方でも一応ACできたが、4進法に直すところで明らかに時間を食っており、改善が必要
誰か教えてください
一応10進法をn進法に変換する簡単なやり方があったのでそれを載せておく
①10進法をn進法に直し、文字列として出力
X = int(input())
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)
②10進法をn進法に直し、左から規定の桁まで0埋めしたのを出力
X = int(input())
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)
print(Base_10_to_n(X, n).zfill(P)) #P桁埋める zfillは文字列のみ有効
参考にさせていただいたのはこちらのページです。ありがとうございます。
Python Tips:Python でゼロパディングしたい - Life with Python
ABC104C
これも実質的に全探索の問題 工夫が必要で、問題を①全部解く②ちょっと解く③一問も解かない、の三つに分類して、そのうえで「ちょっと解く」は0か1種類でよい(二種類以上を解くのであれば、点の高い方を解いた方が得だから)ということを念頭に置いて解く 全探索は上で紹介した二進法表記でイケるらしい(想定解がそれだから全探索するときN進法に置き換えるのはあながち間違いではないか......?)