tooh’s diary

半角全角、常体敬体が入り乱れるカオス

精進(python3)

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解説がの最後らへんが意味不明だったので最初の方に準拠して考えます 問題の趣旨としては「数列中の数字を適切に数列の先頭か末尾に持って行って昇順に復元してくださいね」とい…

3/27 AtCoder(-2進法)

こんばんは。しばらく更新しなかったのはチュウニズムの方ばかりコミットしていたためです。とーです。(AtCoderのstreak自体は地味に続いています)AtCoder ABC105C与えられた数字を-2進数で表す問題 2進数とかではなくて負の数で与えられているのが何とも…

3/22 AtCoder(ceilを使う時の注意、DP、N!を素因数分解)

ARC004C二点間の距離がn個与えられて、点1と点nの距離の最小値はなんぼという問題点が並んでる順番で距離が与えられているので、折り返すのは最長辺の両端でないといけない(逆にそこじゃないところで折ると長さが伸びてしまう) 求める値は、辺の長さの総和…

3/21 AtCoder(最長共通部分列、期待値の線形性)

こんばんは。寝ても寝ても眠いとーです。ARC092CN個の座標が与えられて、xy座標の大きいものと小さいものをペアにしていきましょうという問題想定解が頭良すぎた 自分で最初考えていてのは、xの小さい順にソートしてそれをxの小さい方から覆っていくようにと…

3/19 AtCoder(PyPy3)

こんにちは。気分が悪くて半日お布団の中にいたとーです。AtCoderARC013A以前解けなかったきりしばらく放置していた問題荷物の長さの順列を持ってきて、与えられた容器の辺をその順列の第一、二、三要素で割り切って、掛け合わせたものが容器に入る荷物の数…

3/18 AtCoder(漸化式dp)

こんばんは。特に何もすることなく春休みが終わっていくことに嘆くとーです。今日から解くに至った問題は記録しないことにします。めんどいので。AGC031Bjuppy.hatenablog.comいつもお世話になっているじゅっぴーダイアリーを読んで、自分なりに考えたことを…

3/17 AtCoder(素因数分解)

こんばんは。昨日のAGCのショックでしばらく立ち直れなかったとーです。AtCoder解くに至った問題AGC:031A ARC:097C Tenka1 Programmer Contest:C CADDi 2018:C codeFlyer:B AGC031A解き方はすぐ思いついたのですが、まず10**9+7で割ったあまりを問われている…

3/16 AtCoder(最長部分増加列)

こんばんは。生活リズムが完全に崩壊したとーです。AtCoder解くに至った問題ABC:006D/035D AGC:009A/013A/018A/021AABC006D解説AC LIS(Longest Increasing Subsequence)の問題カードを挿入することで位置を変化させる必要がない部分は「前から見ていって増加…

3/15 AtCoder(巨大な数をある数で割ったときの余りを求める、順列)

こんにちは。肉を食べると確実に腹をこわすとーです。AtCoder解くに至った問題(7問)ABC:012D/021D/030D/046D/047D/052D/073DABC030D例えば、1234567890という数字の列が10**5回続くような巨大な数字(つまり10**6桁)を10**9+7で割ったあまりを突然求めたく…

3/14 AtCoder

こんばんは。シャニマスにドはまりして一日つぶしたとーです。解くに至った問題(2問)AGC:006A CODE FESTIVAL 2016 qual A:B CODE FESTIVAL 2016 qual A B同じものをまとめてくれるset()はリスト内の要素が変数やタプルの時のみ使えることに注意 例えば L =…

3/13 AtCoder

こんばんは。花粉症でくしゃみと鼻水と目のかゆみの三重苦に悩まされているとーです。AtCoder解くに至った問題(8問)ABC:070D/078D/089D AGC:006B/008A,B/014B キーエンスプロコン2019:C 今日は考察ゲーの問題ばかりで解説ACに逃げがちでした......ABC070D …

一か月のまとめ

こんばんわ。とーです。 二月からAtCoderに本腰入れて取り組み始め、一か月が経ちました。(とほぼ同時に50記事になったのでこの記事を書きました) 継続は力なりというのでしょうか、レートの伸びが目に見えて嬉しい限りです。さて、この一か月(2/10~3/10)…