塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

精進(python3)

Pythonの深さ優先探索で失敗した話

ハミルトン閉路が存在するか判定する問題。入力は、 n m x_1 y_1 x_2 y_2 ... ... x_m y_m で与えられる。(nは頂点数、mは辺の数。x_i,y_iは頂点x_iとy_iを結ぶ辺が存在することを表す) #合ってるコード(しかしこれもn=15くらいだと落ちるね......) n,m = …

復習 4/18,4/19

O(n)で前計算することで、各nCrをO(1)で求められるようにする。 mod = 10**9+7 MAX = 10**5+1 #nは10**5までを想定 fact = [1]*(MAX+1) for i in range(1, MAX+1): fact[i] = (fact[i-1]*i)%mod inv = [1]*(MAX+1) for i in range(2, MAX+1): inv[i] = inv[m…

復習 4/9,4/10,4/11

atcoder.jp1からkまでのiに対して、 ・「i回目に働くのは一番早くて何日目?」 ・「i回目に働くのは一番遅くて何日目?」 というのを格納した配列A,Bを考える。いずれも、oxの列を前から、後ろから見ていくことで可能。結論から言うと、A,Bについて、A[i] ==…

復習 4/2,4/3

atcoder.jp必勝法ゲー。dpで遷移を見る。「j枚目で回ってきたときに勝てるか?」をdp[j]で管理する。 取れる枚数がn種類(a_1...a_n)あったとき、dp[j-a_i]が全て「win」であれば、必ず相手に「勝てる」状態で回してしまうことになるため、dp[j] = lose 逆…

復習 3/31,4/1

atcoder.jpまずは美味しい順にソートして上からK個取る。そこから、残りのN-K個のうちでどれかと交換することで満足度が上がるかどうかを見ていくわけだが、この時、すでに取っているネタの種類がi種類であれば、そこから種類を減らすことによって満足度は決…

復習 3/30

atcoder.jp逆元使ってn_C_k(を10**9+7で割った余り)を高速で求める、それはそうみたいな問題なんだけど、流石にテンプレをペタって貼り付けてn=10**5,kを1~10**5まで計算するのはしんどい(factorialの都合上)n_C_k-1からn_C_nまでを一気に求める問題であ…

復習 3/26, 3/27

atcoder.jp桁DP的な発想 解説読んでパッと理解できなかったatcoder.jpこれも桁DP的発想atcoder.jp提出した後で「2,8とかの組み合わせの時無理じゃね?」とか気付く。ちゃんと考察をしましょう。atcoder.jpグラフの用語を知った。 ・直径:一番遠い点間の距離…

復習 3/21

atcoder.jp総和が不変であり、その約数がgcdの候補であることは気づけた。そしてその後に分配するフェーズで余りを横に並べて右側はプラスされる側、左側はマイナスされる側と分けてそれぞれをチェックするところまでは発想できた。 (例) 約数=5で割った…

復習 3/19,3/20

atcoder.jp数字が「ある」ところを探すんじゃなくて、「ない」ところを探すという発想の転換。難しい。atcoder.jp発想の問題じゃなくて、大きな数字を扱うときは注意しましょうねという話。基本的にpythonは大きな数字はメモリの許す限り扱えるけど、例えば …

復習 3/16,3/17

atcoder.jps = 10**100とかいう良く分からん表現に振り回された感がすごいやることとしては、いっぱいつなげる方(s)に対し、sのi番目(iは0~len(s)-1、つまりsの各文字)の文字に対して、そこから数えてa,b,c....が次に最短でいつ出てくるかを数える(これをや…

復習 3/15

クッソサボってた しょうがないねatcoder.jp s = 'AAA' s = 'B' + s #s = 'BAAA' 上の例みたいに、文字列の先頭に新たな文字をくっつけるのは、末尾にくっつけるよりもかなり時間がかかるので注意すべしatcoder.jpサイズ付きUF木で一撃 こういうのが普通にで…

Python3でまったり競技プログラミング 3日目(二分探索)

続かね〜〜〜〜〜〜wwwwwwwwwwwwwwwhttp://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D&lang=jp n,k = map(int,input().split()) W = [] for i in range(n): W.append(int(input())) l = max(W)-1 #トラックの積載容量は少なくとも「荷物…

Python3でまったり競技プログラミング 2日目(DP)

はわわ〜〜〜〜〜〜〜〜。 今日はDP。 Edit Distance (Levenshtein Distance) | Aizu Online Judgeレーベンシュタイン距離(編集距離)は何回の操作である文字列を別の文字列に変形できるか、を表したもの。 qiita.com 詳しい説明と実装方法は上に載ってる。…

Python3でまったり競技プログラミング 1日目(貪欲法)

プログラミング最近全然やってなかったのでリハビリ。1週間続くかな。続くといいな。実践的プログラミングの資料から適当に抜粋してやっていこうと思う。Make Purse Light | Aizu Online Judge coin = [10,50,100,500,999999] J = True while True: n = int(…

空白区切りで出力

T = [1,2,3,4] print(' '.join(map(str, T))) ってやると 1 2 3 4 って出力される

ベルマンフォード法

ある一点からスタートし、そこから残りの全ての頂点に達するのに必要な最短コストを計算するときに使える。計算量は、頂点V、辺の数EとしてO(VE)。負の辺があっても使えるのが、ダイクストラ法と違うところ(強み)。構造は単純で、頂点の数vから1引いた数だ…

幅優先探索(BFS)、深さ優先探索(DFS)の問題

幅優先探索と深さ優先探索は似たような問題をカバーできるけど、幅優先の方があんまり考えなくても実装できる(気がする)。幅優先はキュー、深さ優先はスタックと仲良し。 幅優先探索 幅優先探索は、基本的に「次に訪れる島」をキューの形で保持しておくこ…

6/21 AOJ(クラスカル法)

こんにちは。2S1の成績がとりあえず一安心できるくらいでホッとしているとーです。学校の授業でクラスカル法をやったので復習。プリム法を勉強したのですがこっちは結構噛み砕くのが難しくかったのでまた後回し。どうやら実行時間は大して変わらないっぽい?…

6/10(5/1) データ構造:stack,queue/priority queue、連想配列:map

5/1に書き始めたデータ構造の記事を今更書きます。怠惰。データ構造 stack(スタック)とqueue(キュー)がある。くえぅえではない。簡単なイメージは、 ・スタックは「積み上げられた書類の山」。書類は上へ上へと積まれていき、あなたはそれを上から処理す…

AtCoder,AOJ(再帰、dpの初期化)

こんにちは。無気力に日々を過ごしています。とーです。ABC115Dバンズとパティだけで構成されるハンバーガーをめっちゃ重ねて、その下からX層を食べるとパティは何枚食べられますか、という問題。ちなみに僕はチーズバーガーが大好きです。解き方は、「レベ…

4/20 AtCoder(python3、プリム法)

ARC076D プリム法とは >>>頂点をすべて結ぶのに必要な最小のコストを、辺E,頂点VとしてO(ElogV)で求めるアルゴリズム構造は ①「『既に訪れた頂点(ア)』と繋がる『まだ訪れていない頂点(イ)』」とを結ぶ辺のリストの中で(ここではあくまで辺が主役)、最もコ…

二ヶ月のまとめ

こんばんは。とーです。AtCoderを再開してから2ヶ月が経ちました一か月で120問くらい解きました Dに挑戦するようになったのですがなかなか厳しいです 水色になりたいけど基本的にC速解きが要求されるようになる昨今本当につらいです レートの推移がこちらで…

4/11 AtCoder

こんにちは。最近10時に寝て7時に起きるという小学生顔負けの生活リズムのとーです。ABC087D二人の人の間の距離が渡されるのでそれらの情報が矛盾していないかどうかを確認する問題 解き方としては、起点の情報から見ていって、座標の情報がまだ更新されてい…

4/10 AtCoder

こんばんは。毎日めちゃくちゃ疲れているとーです。ARC098D数列の和とXORが等しくなる部分はいくつありますか、という問題 基本的に、XORと普通の和では、同じビットが立っているところはXORでは0になるので、XORの方が小さくなるということを念頭に置く (…

4/4 AtCoder(情報落ち)

こんばんは。春休み最終日なのに17:00に起きたとーです。 Code Festival Team Relay A問題文は割愛解説で、math.floor( (K-A)/(A-B) )使えばいいよって書いてあったのだが、例えば、K = 10*18, A = 2, B = 1という入力の場合、K-A == 999999999999999998 A-B…

4/3 AtCoder

こんにちは。なんだか風邪気味でちょっと厳しいとーです。AGC002B 箱がN個あり、赤いボールが1つ、白いボールがN-1個入ってる これを与えられた操作でボールを移す作業をしたとき、赤いボールが入っている可能性のある箱はいくつありますか、という問題最初…

4/2 AtCoder

こんばんは。健康診断に行ったら無限人の人間がいて精神が崩壊したとーです。ABC103D横一列に並んだ島のi,i+1番目に橋が架かっていて、与えられた入力の島を行き来できなくするのに落とす必要のある橋の最小本数は?という問題右側の方に番号の大きい島が書…

AtCoder Beginner Contest C問題 まとめ(随時更新)

D埋めが厳しくなってきたので、C問題を復習しつつ主観的難易度をまとめます。下にスクロールすると解法が(一行程度ですが)バリバリ書いてあるので閲覧注意。 開催されたのが最近になるように並んでいます ☆の数が多いほど難しいです 教育的だなあと感じた…

3/31 AtCoder(半分全列挙、二分探索)

こんばんは。1ACするのが重くなってきてだんだん競プロモチベが下がっているとーです。ABC018D問題が長くて怠い女子N,男子M人がいる中から女子P,男子Q人を選ぶ。女子x_iと男子y_i一人ずつの組に対してz_iというパラメータがいくつか与えられており、男子と女…

3/29 AtCoder(1ずつ増加するLIS)

こんばんは。その日の獣には、をやっとプレイし始めました。とーです。AGC024C解説がの最後らへんが意味不明だったので最初の方に準拠して考えます 問題の趣旨としては「数列中の数字を適切に数列の先頭か末尾に持って行って昇順に復元してくださいね」とい…