Rustコトハジメ

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

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

【ABC123-D Cake 123】上位K個系の教育的良問

競プロあるあるテクですが、私もはじめに見た時はビビったので、教育的良問として紹介します。 D - Cake 123 問題 A1...AX, B1...BY, C1...CZからそれぞれ1つずつ値を選び、AxBxCについて上位K個を列挙します。 ただし、X,Y,Z=103ですが、Kは3000程度です。 …

【ABC106-D AtCoder Express 2】二次元累積和

D - AtCoder Express 2 ちなみに、二次元累積和を使うとさらに高速化できます。 それを用いるとO(N2+Q)が達成できますが、本問題ではここまでは要求されません。 その二次元累積和を使った別解で解いてしまいました。 問題 N個の駅がある。M本の電車が、Liか…

【ARC065-B 連結】Union Findを2つ使う

UFを2つ使うっぽいことはわかるが、いざ書こうと思うと書けなかった。結局わかってなかったという話。 D - 連結 / Connectivity 問題 N個の町がある。そこにK本の道路とL本の線路がある。 町iと町jは道路を使っても行き来出来るし、線路を使っても行き来出来…

【ABC096-D Five, Five Everywhere】5つ足して合成数とは

初見だと解けなかった問題 D - Five, Five Everywhere 問題 長さNの配列がある。要素はすべて異なる素数で、すべて55555以下である。この配列からどの5つを選んでも和が合成数となる。そのような配列を一つ見つけよ。Nは55以下。 方針 1つ見つけよ系は、何か…