atcoder.jp・説明 C - Cross の類題をもとにして解ける。この問題は隣接した'#'の数を求める問題なのでこの問題のDFSを今考えている問題のマス全てで行い、隣接する'#'の数をansにappendする。答えはlen(ans)になる。 import sys sys.setrecursionlimit(10**…

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・やったこと 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・参考： DPのやり方はDistribution [AtCoder Beginner Contest 214 C] - はまやんはまやんはまやん ダイスクラ法はEditorial - AtCoder Beginner Contest 214を参考にした。・説明： この問題は2つやり方があり、DPとダイスクラ法でできる。 注意…

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 参考記事をPythonで実装した。 注意点としてBFSのcontinueする条件は s[nx][ny]!='.' とすると s[nx][ny]='G'(ゴール) のときをスルーしてしまうの…

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 引数に頂点vとvまでの長さlengthを持つ、DFSをしていく。最大の長さをansとして、length>ansのときansを更新していく。注意点として帰りがけに頂点v…

atcoder.jp・参考： よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録・やったこと：参考記事の内容をpythonで勉強した。長さがNのリストAをDFSで全探索する。その時の得点(score)が一番高いものがansになる。 #参考：ht…

atcoder.jp・参考： AtCoder ABC 310 D - Peaceful Teams (水色, 400 点) - けんちょんの競プロ精進記録・やったこと：参考記事をpythonで実装した。dfsで全探索することを使う(参考、 よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの…

atcoder.jp・参考： AtCoder ABC 313 B - Who is Saikyo? (灰色, 300 点) - けんちょんの競プロ精進記録・説明： 参考記事のやり方のうち2つをpythonで実装した。 1つ目は、一度も負けていない人を最強とする方法でtmpで負けた人のindexを0にする。負けてい…

atcoder.jp・参考： www.youtube.com・考え方：bfsで解く。1から行ける頂点の距離をdist1、N1+N2から行ける頂点の距離をdist2とする。あとはそれぞれのmaxを取って+1したのが最大の距離になる。 from collections import deque #入力 n1,n2,m=map(int, input…

atcoder.jp・参考： Editorial - AtCoder Beginner Contest 308・考え方：参考の通りDFSをして、H,W座標まで行けるのか(seen[h-1][w-1]を探索済みにできるか)をすればいい。snukeの文字の管理、例えば's'のあとに'n'とかはnx={}で辞書型で管理する。・ACコー…

atcoder.jp・参考： AtCoder ABC 138 D - Ki (緑色, 400 点) - けんちょんの競プロ精進記録Submission #7012551 - AtCoder Beginner Contest 138 ・説明：いもす法を木でやれば良い。いもす法については いもす法 - いもす研 (imos laboratory) を参考。 注…

atcoder.jp ・内容： 貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita の記事のbfsでの実装をpythonでやった。 ・説明：0から1,6,6*6,,,9,9*9,,,,の辺を取ったグラフと見ればbfsで求められる。詳しくは上の記事を参考。c++ではfor文で…

問題： atcoder.jp参考：https://qiita.com/sano192/items/c301aa0f8c5680eea429 https://zenn.dev/fjnkt98/articles/c9b21e90150e7b・前提知識：トポロジカルソートについて知っている(アルゴ式などを参考)。dfsについても(けんちょんさんのqiitaの記事など…

・問題： atcoder.jp・参考： Submission #16162979 - AtCoder Regular Contest 005 AtCoder ARC 005 C - 器物損壊！高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録・0-1BFS： 01-BFSのちょっと丁寧な解説 - ARMERIA・ダイクストラ法： グラフ理論⑤(…

・問題 atcoder.jp ・参考 AtCoder AGC 033 A - Darker and Darker (緑色, 300 点) - けんちょんの競プロ精進記録 ・考えたこと：DFSかBFSを使うことは分かったが具体的なやり方は思いつかなかった。上の記事を参考にして、スタートを'#'としてbfsをする。'#…

・問題 atcoder.jp・参考： スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita・注意点：参考文献を見れば基本大丈夫だが、スタートとゴールの座標をマイナス1する必要がある。(sx-=1,,,のように)・実装： from collections import deque H,W=…

・参考： BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita・内容：上の記事を参考にpythonでBFSを書いた。queueはcollectionsのdequeのほうが早いらしい。dequeはque=deque() #que.append(i)でappend,que.popleft()で左を取り出してキ…