Rustコトハジメ

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

【Codeforces #590 (Div 3) E Special Permutations】数字を先頭に持っていくと何が変わるのか?

良い問題だと思いました。自分の理解と遠くて、エディトリを読むのに苦労した。所要時間1時間以上(IQ30) 図解してまとめます。 Problem - E - Codeforces 問題 Piをi,1,2,3,4,...i-1,i+1,...Nという順列とする。(iを頭に持っていったやつ) 長さMの数列X…

LeetCode Weekly Contest No.157

考察の訓練です。方針案のみ示します。実装意味ない。 https://leetcode.com/contest/weekly-contest-157 C 問題 N2グリッドに0から100以下の整数が並べてある。あなたは好きな位置からはじめて、上下左右に動ける。ただし、すでに訪れたところは0になり、0…

【yukicode No.899 γatheree】オイラーツアー:BFSでたどると同じ階層のノードが連続になる

No.899 γatheree - yukicoder 問題 木(N=105)が与えられる。それぞれのノードにはAi匹の妖精がいる。 ノードkを指定すると、kから距離2にあるノードにいる妖精を集めることが出来る。 クエリ「ノードkを指定したあとに、ノードkにいる妖精の数を求める」 をQ…

【蟻本】オイラーツアーとRMQを組み合わせてLCAを実装する

今日はオイラーツアーの日と決めたので、オイラーツアーの理解を深めるために、オイラーツアーとRMQの組み合わせでLCA(Lowest Common Ancestor)を実装するという蟻本に書いてあるネタをまとめておきます。 この部分は一度読んだ時に、IQが低すぎてあまり理解…

【yukicoder No.900 aδδitivee】オイラーツアー:木を一直線にする

実装が難しくてしてませんが、考え方だけは理解したので書いておきます。 No.900 aδδitivee - yukicoder 問題 木が与えられる。以下2種類のクエリを処理せよ a(v): v以下のエッジに重みxを追加する q(v): 0からvまでの重みの総和を求めよ 初期値はどうでもい…

おれの競プロライブラリが一日に1回くらいクローンされてる件に感謝

競技プログラミングは、外野がおそらくそう想像しているように、ライブラリを組み合わせてはい終わりという問題はほぼないものの、一方で、その解法の中で特定のデータ構造がないと解けないということがよくあります。例えば、セグメントツリーなんかは、コ…

これからの勉強方針を考えよう

今現在、AtCoderのレートが970で、たぶんぼちぼちやっていれば水色までは行くだろうなという見込みは立ってきた。 今の目標は、最終目標である青の実力をつけることなのだが、ここにはかなり乖離がある。青に行くためには1600を出せばよいということではなく…