Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

2019-08-22から1日間の記事一覧

【ABC051-D Candidates of No Shortest Paths】ワシャフロの理解

D - Candidates of No Shortest Paths 問題 無向連結グラフが与えられる。その中で、どの最短路にも含まれていない辺の数を求めなさい。最短経路が計算出来る原理の理解を求められる問題。 方針 ワシャフロで全点最短路を計算して、ある辺(i,j)について、 dp…

【ARC054-B ムーアの法則】三分探索

B - ムーアの法則 問題 今の計算機の能力ではP時間かかるタスクがある。しかし、計算機の能力は1.5年で2倍ずつ上がっていく。最短で何時間後にタスクを終わらせることが出来るか? 方針 は下に凸な関数なので三分探索で求めることが出来る。はっきり言ってそ…

【yukicoder No.599 回分かい】DPとロリハ

No.599 回文かい - yukicoder 問題 文字列Sが与えられる。Sを部分列(S[1],S[2],...S[K])に分解した時、S[i]==S[k+1-i]の時、これを回文かい分解と呼ぶことにする。 文字列Sの回文かい分解は何通りあるか計算せよ。 方針 DPです。先頭のi個と後方のi個を取り…

Rustはmodの挙動がPythonなどと違うので注意

競プロでは、modをとることがよくありますが、Rustでは(たぶんC++でも?)注意が必要です。 fn main() { dbg!(-7%3); dbg!(-7%-3); dbg!(7%3); dbg!(7%-3); } は、 [prog.rs:5] -7 % 3 = -1 [prog.rs:6] -7 % -3 = -1 [prog.rs:7] 7 % 3 = 1 [prog.rs:8] 7 …