内容 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の(色の数)常になって辛い。 前の色の(左端、右端)だけ見れればいいので、[色数][…

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

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

内容 CFのRound #627 Div3のF問題、「MaximumWhiteSubtree」をpython(pypy)で解いた。 問題 入力 木が与えられる。 各ノードは、白か黒に塗られている。 出力 各頂点 v について、以下の問題を解く。 vを含む 部分木 Sを、[Sに含まれる白の頂点の数 - 黒の頂…

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

概要 ICPC 国内予選2010年のc問題を解きました。 judge.u-aizu.ac.jp pythonで時やりたかったけど、TLEな感じだたったので、 c++でやりました。 概要 x(x+1)(x+2)/6で表される数があって、 それを正四面体数と呼ぶ。 正四面体数をいくつか選んでその和が入力…