記事一覧
ABC225 D問題[双方向連結リスト][リストのアンパック]
■要約
実際に参戦中，なんとなく貪欲に探索すればできそうな気がしたが，実装に至らず．
上のサイトを参考にさせていただくと，どうやら，双方向連結リストというデータ構造を使えば上手く行ったみたいだ．これは特に難しいことではなく，各番号の前と後ろに何の番号が繋がっているかを保存しておけば良いというものだ．これを使えば，簡単に電車の前後ろに連結しているものだけを保存しておけるので，いちいち今電車がど
![Python データ構造整理[heapq][deque]](https://assets.st-note.com/production/uploads/images/60554718/rectangle_large_type_2_6f3fac49fa4f497cbe17f45ec5ecc7dd.jpeg?width=800)
Python データ構造整理[heapq][deque]
■本記事について
今回の記事ではいつもAtcoder中にpythonの普通のリストだと計算量的に間に合わないけどなんかデータ型使えば上手く行けたはず，，，ってのを記事にしてまとめておきます．
■リスト型の計算量について
リスト型については上の記事を大変参考にさせて頂きました．下の図は上の記事より引用させて頂いております．要素の挿入や，削除，要素の探索，特定範囲のリストの取り出しはO(n)
ABC217 D問題
■要約
切っていく場所を順番付きのリストに保存して，c=1のときも2のときも何番目にxがあるか知ればよいから二分探索でその場所を見つければO(NlogN)でイケルと思った．しかし，pythonには順番付きリストというものが存在しないらしい(C++などはあるみたい)．平衡二分探索木というものを使えば良いらしいが本番中にはACできなかった．平衡二分探索木の中のAVL木というものを使うと，
上図の
![Atcoder 典型90問 076★3[二分探索][累積和]](https://assets.st-note.com/production/uploads/images/59964841/rectangle_large_type_2_49318182fe319160c7160d14161d61d6.jpeg?width=800)
Atcoder 典型90問 076★3[二分探索][累積和]
■要約
問題の流れは理解していたが，実装が難しかったことと，二分探索で条件を満たすRを見つけるという考え方が浮かばなかった．確かに二分探索ならO(logN)で見つけることができるので，こういう使い方もできるかのと勉強になった．
簡単に問題を解く流れを書くと以下のよう．
①連続するピースを表せるように，ケーキ２周分に配列を拡張する．▶ N番目から数える連続するケーキの組み合わせを表現できる
Atcoder典型90問 069★3[繰り返し２乗法]
■要約
N=1以外の時は，総数がK*(K-1)*(K-2)^(N-2)になることはすぐに分かったが，累乗の計算量はO(N)なのでどうしようかと考えていた．調べたら，繰り返し2乗法というものがあり，計算量をO(logN)に減らせる．
説明は他の方々がとてもわかり易いものを記載しているので割愛する．
pythonだとわざわざ実装しなくても
pow(x,y,n)でx^yをnで割ったあまりをO(l
![Atcoder 典型90問032 - AtCoder Ekiden（★3）[順列全探索][配列で隣接を評価]](https://assets.st-note.com/production/uploads/images/59222389/rectangle_large_type_2_0659bc6a7b726b77221c347445df13dc.jpeg?width=800)
Atcoder 典型90問032 - AtCoder Ekiden（★3）[順列全探索][配列で隣接を評価]
■要約
正直★3の中では今まで解いてきた問題で一番複雑だった．解き方はすぐに思いついた．Nがとても小さいので，①各区間の走り方の全パターンを考えて，②それぞれに対して噂話を評価して，区間にかかる時間を更新していけばよいと考えた．①については，pythonでは
num = list(range(N))ptn = list(itertools.permutations(num))
のようにす
![Atcoder典型90問027(★2)[in][listとset]](https://assets.st-note.com/production/uploads/images/59155287/rectangle_large_type_2_6d636fb4eae2ceebeb1c61c23bcd8556.jpeg?width=800)
Atcoder典型90問027(★2)[in][listとset]
■要約
解き方はすぐに思いついた．でてきた単語をリストに入れていって毎回の入力で得た単語がそのリストの中に入っているか確かめていけば良いと考えた．しかし，pythonではlist型におけるinの平均計算量はO(N)のため，毎回のループでこれを行うとO(N^2)の計算量が必要になりTLEとなってしまう．これを防ぐ方法は案外簡単で，set型を用いればよい．setは同じ値の重複を許さないような型なの
![ABC 典型90問 010(★2)[累積和]](https://assets.st-note.com/production/uploads/images/59056718/rectangle_large_type_2_ee579e1c0dd01ffd4d4bb0a975835bae.jpeg?width=800)
ABC 典型90問 010(★2)[累積和]
■要約
生徒は2クラスあって，各クラスのある区間のテストの点数の和を求める問題．まず，①各生徒のテストの点数の保持の仕方に工夫がいる．最初は辞書とかがいいのかと思ったがいつか解いた問題で使った，N個の長さの配列を2つ用意してi番目に得点を代入すればよいことが思いついた．次にQ個のクエリについて，毎回指定範囲の和を求めると計算量がO(NQ)でTLEしてしまうことに気がついた．今回はある区間の総和
![Atcoder典型90問 007(★3)[二分探索]](https://assets.st-note.com/production/uploads/images/59016730/rectangle_large_type_2_0359aba3f93ce7818e178223924d366a.png?width=800)
Atcoder典型90問 007(★3)[二分探索]
■要約
問題文通り考えるとQ人の生徒について，N個のクラスを考えないといけないのでO(NQ) = 10^10でだめなことが分かる．そこで今自分が使えるアルゴリズムを考えると，bit全探索/二分探索/累積和ぐらいであり，これらが使えないか考えた．すると，今回の問題は，全部の差を考えるんじゃなくて，生徒Bのレーティングが，クラスのレーティング配列Aのどの値に近ければわかればいいので，配列Aをソート
ABC212 C問題[二分探索]
Difficultty : 246
■要約
久々に参加したABCで解くことが出来なかった悔しい問題．二重ループでは余裕でTLEなので愚直でないことは分かる．過去に解いた問題で，配列関係の最小の〇〇や，最大の〇〇系はほぼ二分探索というツイートを見て二分探索を使うことは分かったが実装や考え方がさっぱりだった．今回真剣にとき直して，なんとなく苦手意識を持っていた二分探索を理解できた．（気がする．．
![Atcoder 典型90問004-★2[前処理][配列処理]](https://assets.st-note.com/production/uploads/images/58860235/rectangle_large_type_2_af3439f12d1ba2edf5b5a13a9ca69d39.png?width=800)
Atcoder 典型90問004-★2[前処理][配列処理]
■誤解答
方針自体はすぐに思いついた．求めたい場所に対して縦と横の総和からその場所の値を引けば良いと考え実装．この際，行列の縦と横の総和の取り方が分からず迷う．縦の総和はlistで行けるが，横の総和はnpにしないとsum関数を使って上手くできない．
import numpy as npH, W = map(int, input().split())ans = 0a = [list(map(in
![典型90問002[bit全探索][カッコ列]](https://assets.st-note.com/production/uploads/images/58629759/rectangle_large_type_2_4458837ab5c615794b21d041c44e85ba.png?width=800)
典型90問002[bit全探索][カッコ列]
大変お久しぶりです．死ぬほど忙しかった修士1年の前期が終わり余裕が出来たので久々に競プロを再開して行きたいと思います．M1前期は就活や授業，研究，学会とてんこもりでしたのでまた機会があったら振り替えっていきたいと思います．
友人(tukasくん)に過去問もいいけど典型90問も良いよと進められたのでしばらくは★3以下を解いて入茶を目指していきます．
■方針
"("と")"の2パターンの並び
![ABC 178 C問題 [数学的に解く]](https://assets.st-note.com/production/uploads/images/53113097/rectangle_large_type_2_cd793cdab9330796de3219cc9e7449ff.png?width=800)
ABC 178 C問題 [数学的に解く]
difficulty:653
要約
最初イマイチ問題の意味が掴めなかったが，5分ほど考えて，ようは0~9しか含まないN個の文字列の中で，必ず0,9を含むような文字列のパターンはどのようなものがあるか？という数Aの組み合わせのような問題に帰着した．
ここまで思考できれば，どっかに0か9がこればいいんだけど，それをいちいち全部考えていくことより，逆に0,9を必ず含まない場合を考えて，それを全通り
ABC202 参戦記
パフォーマンス：565(A, B, Cの3完)
レーティング：344 → 367
3完したけどどうやらC問題が大分簡単だったみたいでパフォーマンスとしてはそんなに．しかしだいぶ本番でC問題までは解けるようになってきたので少し自信になった．
A問題
すべての面は足したら7になるのでもう片方は7-a, 7-b, 7-cになる．
a,b,c = map(int, input().split()
![ABC168 C問題[bit全探索]](https://assets.st-note.com/production/uploads/images/52877802/rectangle_large_type_2_86b6ee9485b0dba44c47b265decd6f70.png?width=800)
ABC168 C問題[bit全探索]
要約
C_n円の本がN冊あって，各本について読めばM個の能力がA_nm上がっていき，一番安い値段で，すべての能力がXを超す時の値段を求める問題．
直近のABCの問題でこのような条件から3個選んで．．って問題は二分探索を使って解いていたのでそのように解くかと考えていたら，N,Mは共に最大12なので，各本の買い方は最大で2^12 = 4096 = O(10^3)なので全パターン考えても余裕な事に気