内容 公式解説と違う解き方なのでメモ。 問題 リストAとクエリ(L,R,X)が与えられる。 Aの区間[L,R]に含まれる 数字X の個数を求める。 atcoder.jp 考えたこと(1-originで書いてます) F(L,R) =Aの区間[L,R]に含まれる 数字X の個数とする。 F(L,R) = F(1,R)-F…

内容 CodeForces 712 Div2 F問題を、pythonでといた 問題 https://codeforces.com/contest/1504/problem/Fcodeforces.com 考えたこと 解説ACです。 codeforces.com ポイント 減少列を分解するの頭いい。(minf>maxfのとこ) この条件の時、new_eleは、seq1,seq…

内容 CodeForces 712 Div2 E問題を、pythonでといた 問題 codeforces.com 考えたこと TSPだけど、N<=10*5なので、greedyとかで行けそう。 beautyが大きいところから、小さいところには、cでいける。 一番beautyが大きい都市まで行けば、あとは、残りを辿るだ…

内容 ARC116のD問題 I wanna win the game をpythonで解説AC (解説というよりは、自分用のメモ) 問題 atcoder.jp editorial解と youtube解説の解の二つでといた。 考えたこと ポイント 実装 youtube liveの解法(桁ごとにDPしてく) 多分 O(logM*N**2) 定数倍…

内容 Atcoder Beginner contest E問題 Travelerをpython でAC 問題 atcoder.jp 考えたこと 各色ごとに、左端で終わるか、右端で終わるかのどちらかが最適。 色ごとに試すと、2の(色の数)常になって辛い。 前の色の(左端、右端)だけ見れればいいので、[色数][…

内容 第5回 ドワンゴからの挑戦状 予選 C - k-DMCをpythonで解いた。 問題 atcoder.jp 考えたこと クエリの数が少ないので、各クエリにO(N)くらいで答えればいいや。 区間の幅を固定して、スライドさせていくと解けそう。 尺取りだ! ポイント 区間の中の、D…

内容 DDPC B問題 "DDPC 特別ビュッフェII"を、pythonで解いた。 にぶたんのメモ。 問題 atcoder.jp 考えたこと 条件を満たす最小時間を求めろ。 美味しさが高いものから食べていけばよさそう。 二分探索でいけるのでは ?と思い、二分探索 ポイント 制限時間…

内容 CODE FESTIVAL2015 予選A D問題「壊れた電車」をpythonで解いた。 二分探索をバグらせがちなので、メモとして。 問題 atcoder.jp 考えたこと 最小値を求める問題で、にぶんたんができそうなので、 にぶたんする。 ポイント シミュレーションの時に、左…

内容 AOJ "Matrix Chain Multiplication"を pythonでといた。 下のやつの区間DP編 qiita.com 問題 複数の行列の積を計算するときに、どの順番で計算すると、scalarの乗算が少なくなるのか? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_…

内容 Atcoder 187 E問題(500) Through Pathをpython で 解説AC 問題 atcoder.jp ポイント 木の上で、imos法を使う。 適当に頂点を置くと、queryは、次のどちらかに言い換えができる。 ある頂点 k の子孫に xを足す ある頂点 kの子孫以外にxを足す rootの子孫…

内容 Atcoder ARC103 のE問題(700) Tr\eeをpythonで解いた。 問題 atcoder.jp 考えたこと S[i]=="1"の時に、N頂点は iとN-iに別れる-> S[i]==1ならS[N-i]==1 木だから葉が存在する。そこできると、1とN-1に別れるはず。-> S[1]==0 ポイント 頂点のidの大きい…

内容 Atcoder Beginner Contest 013 D問題 「阿弥陀」をpythonで解いた。 問題 阿弥陀くじが一つ与えられる。 そのあみだくじを、D個縦につなげる。 つなげたあと、各スタート地点からたどり着く場所を求めろ。 atcoder.jp 考えたこと あみだくじは、同じも…

内容 Atcoder Beginner Contest 013 D問題 「阿弥陀」をpythonで解いた。 問題 阿弥陀くじが一つ与えられる。 そのあみだくじを、D個縦につなげる。 つなげたあと、各スタート地点からたどり着く場所を求めろ。 atcoder.jp 考えたこと あみだくじは、同じも…

内容 ABC170のE問題(500) Smart Infantsを解いた。 コンテスト中には解けなかったが、この類の問題を解けるようになりたいので、メモで残す。 問題 園児と幼稚園がある。 園児は、それぞれどこかの幼稚園に所属していて、atcoderのrateを持っている。 *園児…

内容 ABC164 のE問題(500点) Two Currenciesを、python出といた。 問題 atcoder.jp 考えたこと 各頂点への最短時間なので、dijkstraしたい。 移動できるかどうかは所持金に関わってくる。 所持金も状態として持ちたい。 ポイント u->vの移動にかかる金額は高…

内容 ABC164 のE問題(500点) Two Currenciesを、python出といた。 問題 atcoder.jp 考えたこと 各頂点への最短時間なので、dijkstraしたい。 移動できるかどうかは所持金に関わってくる。 所持金も状態として持ちたい。 ポイント u->vの移動にかかる金額は高…

内容 ABC069のD - Decrease (Contestant ver.)(600点)をpythonで解いた。 問題 atcoder.jp 考えたこと 操作を逆から考えて、答えを構築する。 とりあえず、N=50にして、初期値をN-1にして構築してみる。 各iでの操作回数をできるだけ同じようにすることで、…

内容 ABC145のE問題(500点)「All you can eat」をpython出といた。 提出はpypy 問題 atcoder.jp 考えたこと ナップサックな感じだし、制約がN=3000なので、N**2でできそうなDPを思いつく。 T-1に頼んだものは、食べ終わることができる。 料理を頼んだ時、そ…

内容 Atcoder Tenka1 Programmer Beginner Contest のC問題：Alignをpythonでといた。 問題 atcoder.jp 考えたこと 解説にもある通り、ギザギザな感じにすると良い。 a

内容 ABC 157のE問題をpythonで解いた 問題 atcoder.jp 考えたこと 問題を見る感じ、seg木じゃんとなるので、segtreeで考える。 ポイント * 各ノードが、区間にどのアルファベットを持つかを記録できる必要がある。 ここで、setとかでやると、TLEしてしまう…

内容 ABC 154のE問題：Almost Everywhere Zeroをpythonで解いた。 問題 問題シンプルで、 1 以上N以下の整数であって、10 進法で表したときに0 でない数字がちょうど K 個あるようなものの個数を求めてください。 atcoder.jp 考えたこと 以前といた「桁DP」…

概要 Code Jam 2020のQualification RoundのA~C問題をpythonでときましたメモ。 (A~Cしか解けなかったため) 問題はこちら codingcompetitions.withgoogle.com A: Vestigium def solve(): N = int(input()) grid = [[v for v in map(int, input().split())] f…

内容 EC R-83 D問題 Count the Arraysをpythonでと解きました。 問題 codeforces.com 以下の条件を満たす配列 A の数を求める len(A)=N Aの要素は [1,M] ちょうど一つ、等しい数のペアを含む あるインデックス iが存在し、1~iまでは単調増加、i~Nまでは単調…

内容 CFのRound #590 Div3のD問題、Distinct Characters Queriesをpythonで解きました。 問題 文字列S(アルファベット小文字)とQ個のクエリが与えられる。 クエリは二種類あって、 (1 x y) -> 文字列のx番目の文字を、yに書き換える。 (2 l r) -> 文字列の[l…

内容 ABC137 E問題Coins Respawnをpythonで解きました。 問題 atcoder.jp 考えたこと 問題見た感じ、辺のコストを(-cost+P)にして、負の辺がある最短経路問題じゃんと思った。 負の重みの辺があるので、ダイクストラは使えなくて、 ベルマンフォード を使う…

内容 Educational Codeforces Round 69 A "DIY Wodden Ladder"を解きました。 python3 問題 本文 K段のはしごを作りたい。 K段のはしごは、 長さK+1以上の棒２本(はしごのbase) 長さ１以上の棒 k本(はしごのstep) で構成される baseの2本は違う長さで良いし…

内容 Educational Codeforces Round 69 DIv2 B "Pillars" を解きました。 python3 問題 本文 N本の柱がある。(1~N)これらは、横一列に並んでいる。 それぞれの柱には、半径 r_iの円盤が乗っている。 円盤は隣の柱に移動することができる。 円盤の移動には、…

内容 ABC 134 C(300点) "Exception Handling"を解きました。 問題 https://atcoder.jp/contests/abc134/tasks/abc134_c 考えたこと 自分より左の区間のmaxと、自分より右の区間のmaxを比べて大きい方を出せばいい。 ポイント 左から見ていく場合の最大値と、…

内容 ABC 134 D(400点) "Preparing Boxes"を解きました。 pypyで提出(pythonだとTLEしてしまったため) 問題 https://atcoder.jp/contests/abc134/tasks/abc134_d 考えたこと iの箱に入れると、iの約数の箱に影響が出る。 玉を入れると、自分より大きい数の箱…

Intro Educational Codeforces Round67(Div2)のAをpython で解きました。 codeforces.com A: Stickers and Toys 問題文 おもちゃ屋でチョコエッグが売ってて、中にはおもちゃが入っている。 チョコエッグの中身は３種類ある。 sticker のみが一つ入っている …