2020-01-01から1年間の記事一覧
内容 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までは単調…
内容 ECF R-83のC問題をpythonで解いた。 問題 codeforces.com 配列 [v_1, .. v_n]が与えられる。各要素は0で初期化されている。 配列に対して、下記の操作を行う i-th stepにおいて、(i=0から始まる) 配列の要素を一つ選んで、kiを加える or 何もしない 任…
内容 CFのRound #627 Div3のF問題、「MaximumWhiteSubtree」をpython(pypy)で解いた。 問題 入力 木が与えられる。 各ノードは、白か黒に塗られている。 出力 各頂点 v について、以下の問題を解く。 vを含む 部分木 Sを、[Sに含まれる白の頂点の数 - 黒の頂…
