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・参考: drken1215.hatenablog.com・やったこと:参考記事の考え方でpythonで実装した。 n=int(input()) a=list(map(int,input().split())) a.sort() avg=sum(a)//n rem=sum(a)%n #あまり #print(avg,rem) b=[avg for _ in range(n)] #aを変形し…
atcoder.jp・参考: ABC312 C問題(Invisible Hand)を解く - プロひろ・説明:二分探索で解く。okとngを二分探索で更新していきokが最終結果になる。( 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita を参照) import bisect n,m=m…
atcoder.jp・説明:左上と右下が一致しているか愚直にif文を書く。一致していたらflad,cntを加算する。全部一致したらOK。 n,m=map(int, input().split()) s=[input() for _ in range(n)] ans=[] for i in range(n-8): for j in range(m-8): flag=0 cnt=0 if…
atcoder.jp・参考: ABC310 B問題(Strictly Superior)を解く - プロひろ・備考:本番でWAが消せなかったので復習。基本的には問題文の条件の通りにやればよい。 n,m=map(int, input().split()) p=[] c=[] f=[] for _ in range(n): l=list(map(int, input()…
atcoder.jp・参考:AtCoder ABC 311 B - Vacation Together (灰色, 200 点) - けんちょんの競プロ精進記録・説明:本番でREが1つでたので復習。参考ではc++でやっているのでpythonで実装した。'o'が連続した日数をlengthで保持してresを更新していく。'o'が…
atcoder.jp・参考: Editorial - Toyota Programming Contest 2023#4(AtCoder Beginner Contest 311)・内容:参考の説明です。・考え方:閉路の頂点を見つけて、その頂点から閉路を一周する。その過程で閉路の頂点をbにappendしていく。 n=int(input()) a=…
atcoder.jp・考え方:二分探索で解ける。まず、setにして重複を消す。次に反転文字列が文字列全体にないか、二分探索してあったら答えを-1する。 import bisect n=int(input()) s=[] for _ in range(n): s.append(input()) s=list(set(s)) #setで重複を消す …
atcoder.jp ・考え方:前半後半に文字列を分ける。あとはa,bがどちらに属するかで変換を変える。文字やリストの交換は任意のx,y(文字、リストなど)に対してx,y=y,xと書ける。 ・参考: 【AtCoder解説】PythonでABC199のA,B,C問題を制する! - Qiita n=int(…
atcoder.jp ・参考: 【AtCoder解説】PythonでABC237のA,B,C,D,E,F問題を制する! - Qiita・考え方:先頭の'a'と後ろからの'a'を比べて、先頭のが多かったらNo。先頭のが少なかったら足りない分先頭に足して同じか見る。 s=input() ln=len(s)-len(s.lstrip('…
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・考え方:飲み終わるのが遅い順にソートして、累積和を取る。累積和がKを超えたら、そのindexがそのまま答えのaのindexに相当する。 n,k=map(int,input().split()) ab=[list(map(int,input().split())) for _ in range(n)] ab.sort(reverse=True)…
atcoder.jp・考え方:基本的にはs,tを前から比べていって違う文字が出たらそのindexを+1して出力する。・注意点:tの最後の文字のときはlen(s)+1を出力する。 s=input() t=input() n=len(s) for i in range(n): if s[i]!=t[i]: print(i+1) exit() print(n+1)…
atcoder.jp・参考: Editorial - AtCoder Beginner Contest 308・考え方:参考の通りDFSをして、H,W座標まで行けるのか(seen[h-1][w-1]を探索済みにできるか)をすればいい。snukeの文字の管理、例えば's'のあとに'n'とかはnx={}で辞書型で管理する。・ACコー…
atcoder.jp・参考: コード自体の参考 Submission #43161216 - AtCoder Beginner Contest 308 decimalの参考 Decimal (十進浮動小数点数型) ・注意点:pythonでは小数点15桁までしか表示できずそのためWAしてしまう。decimalモジュールを使うとこれを回避で…
atcoder.jp・参考: Submission #42910610 - Tokio Marine & Nichido Fire Insurance Programming Contest 2023(AtCoder Beginner Contest 307) ・考え方:'('が出てきたらある値(仮にaとする)を+1して、')'が出てきたとき0 n=int(input()) s=input() ans=[…
atcoder.jp・参考: AtCoder ABC 138 D - Ki (緑色, 400 点) - けんちょんの競プロ精進記録Submission #7012551 - AtCoder Beginner Contest 138 ・説明:いもす法を木でやれば良い。いもす法については いもす法 - いもす研 (imos laboratory) を参考。 注…
atcoder.jp参考: [ARC162] A - Ekiden Race|syamashi・基本的には参考記事の考え方でやる。しかし、往路(index)と総合順位を対応させて総合順位でソートする必要があり、それをenumarateで実装している。 t=int(input()) for _ in range(t): n=int(input()…
atcoder.jp・解説: Editorial - Toyota Programming Contest 2023#3(AtCoder Beginner Contest 306) ・反省点:食べたときと食べなかったときの遷移は別々にやるとWA。食べたときの遷移をして、食べたとき(dp[i+1][0],dp[i+1][1])と食べなかったとき(dp[…
atcoder.jp・説明: cntというリストのa[i]番目(cnt[a[i]])を+1して2になったらa[i]を出力する。つまり前から数えてa[i]が2回出たタイミングでa[i]を出力する。 n=int(input()) a=list(map(int,input().split())) cnt=[0 for _ in range(n+1)] for i in rang…
c++の for (int i=1;i<=n;i*=6) //何らかの処理というfor文をpythonで書くと i=1 while i<=n: #何らかの処理 i*=6 とかける。c++のほうがこの手のfor文は簡単にかける。・参考問題 atcoder.jp
atcoder.jp・参考: drken1215.hatenablog.com ・やり方: 基本的には上の記事を参考。jは0でcapslockキーがoff,1でon。dp[i][j]はi文字でのjがON,OFFであったときにかかる時間。 capslockの遷移はdp[i][0]=min(dp[i][0],dp[i][1]+Z)、dp[i][1]=min(dp[i][1]…
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 #42147989 - KYOCERA Programming Contest 2023(AtCoder Beginner Contest 305) ・考え方:前処理をしてクエリの中の処理を軽くする。二分探索を使うのでスライスにおけるAのi番目までの睡眠時間を前処理として行えば良い。…
atcoder.jp・説明:与えられたマップに対して行ごとと列ごとに'#'の数を求める。'#'の数は必ずどこかの行、列で他の行、列より1小さい。よって行、列毎に'#'の最大値を取り、その数-1の値がある行と列を求めれば良い。 ・実装例 h,w=map(int,input().split()…
atcoder.jp#説明:アルファベットと数字の対応を辞書型で記憶する。ここでc[p]はcのキーがpのvalueという意味。あとはvalue同士の差を取れば良い。・実装例 p,q=map(str,input().split()) c={'A':0,'B':3,'C':4,'D':8,'E':9,'F':14,'G':23} print(abs(c[q]-…
・問題: onlinejudge.u-aizu.ac.jp・ダイクストラ法の詳しい解説:グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube・やること:ダイクストラ法のプログラムの勉強のため上のAOJの問題を解く。・プログラムの説明:はじめに辺がないときの処理をする。ま…
・問題: atcoder.jp・参考: Submission #16162979 - AtCoder Regular Contest 005 AtCoder ARC 005 C - 器物損壊!高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録・0-1BFS: 01-BFSのちょっと丁寧な解説 - ARMERIA・ダイクストラ法: グラフ理論⑤(…