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

内容 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の子孫…