2023-09-01から1ヶ月間の記事一覧
atcoder.jp・説明 "9876543210"が最大の答えになるのでこれ以下の値を列挙する。今回はitertoolsのcombinationsを使った。 from itertools import combinations k=int(input()) C=[9,8,7,6,5,4,3,2,1,0] ans=[] for i in range(1,11): for c in combinations…
atcoder.jp・参考 トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320) - YouTube Sorted List — Sorted Containers 2.4.0 documentation・説明 SortedListを使うことで先頭の要素(昇順になっているので最小値)をpop(0)を使い、O(log…
atcoder.jp・説明 DFSで解ける。Aiから行けるBiをDFSしていき、原点からの距離を(distx, disty)で管理する。 注意点として、入力で g[b].append((a,-1*c,-1*d)) bから見たaの座標もappendしないといけないことに注意。 import sys sys.setrecursionlimit(10*…
atcoder.jp・説明 答えは連結成分の中で、最大の人数になる。なぜなら最大人数を全部の別々のグループに別けなければいけないからだ。 from atcoder import dsu n,m=map(int,input().split()) uf=dsu.DSU(n) for i in range(m): a,b=map(int,input().split()…
atcoder.jp・参考 AtCoder Regular Contest 106 B – Values を解いた記録 – Manuel1024の引きこもルーム・説明 Union-Findを使って実装した。操作によって連結成分毎の合計は変わらないことので、もし変わっていればNoになる。 atcoderで新しく使えるように…
atcoder.jp・参考 ABC319をPythonで解いてみたよ。(A～E問題) - Qiita・説明 TLEだったので、参考記事を参考にした。プログラムの説明は下のプログラムでコメントアウトしている。 import math n,x,y=map(int,input().split()) p=[] t=[] for i in range(n-1…
atcoder.jp・参考 ABC319をPythonで解いてみたよ。(A～E問題) - Qiita・説明 基本的には参考記事を参考にして、問題文の通りに実装した。 工夫としては f=[] for _ in range(3): a,b,c=map(int,input().split()) f.append(a) f.append(b) f.append(c) と入力…
atcoder.jp・やったこと atcoder ABC 213 E - Stronger Takahashiの勉強 - stosasa’s blogでやった問題と同じようにすれば解けるのでやってみた。0-1BFSで解ける。説明は下でコメントアウトしている。 from collections import deque H,W=map(int,input().sp…
atcoder.jp・参考 AtCoder ABC 213 E - Stronger Takahashi (水色, 500 点) - けんちょんの競プロ精進記録・やったこと 参考記事をpythonで書いて実装した。パンチすることによって2*2のマスに移動できるのでそれをコスト1、通常の移動をコスト0として0-1BFS…
atcoder.jp・参考 AtCoder Beginner Contest 216 - YouTube・説明 解き方は実際にシミュレーションするものとDAG判定するものがある(参考動画参照)。今回はシミュレーションする方で解いた。 しかし、TLEしたので原因を調べた。結論はリストをpopするときに…
atcoder.jp・参考 Editorial - THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） 「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】 - Qiita bitDP（集合を用いたDP）について - D言語で競プ…
atcoder.jp ・参考 THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318） - YouTube・説明 参考動画をPythonで実装した。真ん中だけ違うもの(動画のX?X) - 全部同じもの(動画のXXX)を求める。 また、参考動画でのとなる。ここでのn…
atcoder.jp・説明 まず、問題文のFを降順にソートしても変わらないのでソートする。Fの初めからD個ずつの和がPを超えた回数が1 日周遊パスを使った回数になる。あとは、通常料金のものを1 日周遊パスを使った料金に加算すればよい。 n,d,p=map(int,input().s…
