内容 公式解説と違う解き方なのでメモ。 問題 リスト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…

intro 備忘録的メモです。 motivation pythonで、dsfの帰りがけ順序探索(post-order-traversal)をやるときに、非再帰で実装したい issue TLEしてしまう。 おそらく、下のような実装になるはずで。 while文の中の、 for nex in adj[node]:の部分が、遅い node…

内容 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」…

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

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

内容 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の約数の箱に影響が出る。 玉を入れると、自分より大きい数の箱…

Abst ARC089のB問題 (500点) Checkerをpythonで解きました。 pypyで提出しました。 問題 queryとして、2Dのgridで、点の座標と色(黒orしろ)が与えられる gridを幅Kの正方形で白黒のチェック模様に塗る queryの座標と色の組み合わせを満たす個数を最大にする…

Abst ABC 131 C問題 Anti-Division (300点)をpythonで解きました。 問題 [A,B]の整数のうち、CでもDでも割り切れないものの個数を求める。 atcoder.jp 方針 [A,B]の個数という問題なので、 [0,B]の個数から [0,A-1]の個数を引く ことで答えを求める。 CでもD…

Intro ARC077 D問題 「11」(600点) をpythonで解きました! Point 逆元を使った組み合わせの計算 問題 1~nの数字からなる長さn+1の数列が与えられる。 (1~nの数字の中で、一つだけ２回出てくる数字があって、それいがいは1回しか出てこない) k=1...n+1につい…

Abstract ABC 122 D問題(400点) 「We like AGC」 を解きました。 python こんな人にオススメ 数え上げの練習がしたい dpの練習 problem 以下の条件を満たす文字列を AGC文字列 とする。 A,G,C,T の４文字でできている "AGC"という文字列を含まない 任意の文…

概要 Atcoderで開催されてた、M-SOLUTIONS プロコンオープン D問題(500点)の解説記事です。 python でときました。 問題 入力 頂点数Nの木が与えられる。 N個の自然数 内容 木の頂点に与えられた数字を当てはめていく。 edge(a,b)があった時に、そのスコアを…

概要 ABC 128 C問題のswitchesをpythonでときました。 問題 atcoder.jp 解法 スイッチの付け方を全探索する。 ポイント bitを使ってスイッチのon-offの状態を表して、全探索する。 回答 # python template for atcoder1 import sys sys.setrecursionlimit(10…