2021-12-01から1ヶ月間の記事一覧
問題：AtCoder Beginner Contest 233: E - Σ[k=0..10100]floor(X／10k) 解説 を計算せよという問題。 Xの制約が と大きいし、k=0から10100まで計算は普通にしていたら制限時間に間に合わない。 Xの桁数が最大500000なので、問題をエスパーすれば計算量O(桁数…
![はてなブックマーク - ABC233: E - Σ[k=0..10^100]floor(X／10^k) を解いた](https://b.hatena.ne.jp/entry/image/https://takeg.hatenadiary.jp/entry/2021/12/26/151954)
THIRD プログラミングコンテスト 2021 （AtCoder Heuristic Contest 007）の参加記録です。 ヒューリスティックコンテストには参加したこと無かったのですが、今回は4時間と短めの時間設定だったので参加してみました。 問題概要 800x800の二次元座標上に400…
問題：競プロ典型 90 問 073 - We Need Both a and b（★5） 解説 以下の木DPを構築して解きたい。 dp[u][j] := （頂点uを根とする部分木において、）頂点uを含む連結成分の状態がjのときの場合の数。ただしj=0は'a'しかない状態、j=1は'b'しかない状態、j=2…
