Rustコトハジメ

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

【yukicoder No.911 ラッキーソート】わからないので問題を分解します

複雑すぎて、解説も読んでもよくわからなかったので、とりあえずこれなら解けるだろうというところまで問題を分解しまくって簡単にします。 No.911 ラッキーソート - yukicoder 問題 方針 分解1「範囲の分解」 分解2「ビットの分解」 分解3「再帰」 問題 N個…

凸性の利用

600点で頻出なので整理します。 凸+凸=凸を利用した問題は多く出題されます。凸グラフを足し合わせると、やはり凸グラフになります。 例えば、 www.rustforbeginners.com は、|x-ai|というグラフの形に下凸に着目して、和も下凸になるという性質を利用した問…

【ABC131 F - Must Be Rectangular!】長方形の座標をグラフ上の辺とみる

F - Must Be Rectangular! 問題 二次元座標上に点がN個与えられる。 (a,b),(a,d),(c,b),(c,d)のうち3点があるものについて、残りの1点を補完することが許される。 この時、何回補完することが出来るか。 方針 一番左上の点から、自分の真右と真下にある点を…

【ABC127 F - Absolute Minima】夜な夜な実装したTreapでトライ

F - Absolute Minima 問題 単純化します。 問題は噛み砕いていくと、数字が1つずつ与えられた時、その都度、 大きさ順に並べて真ん中の数字を求めよ その数字より前と後ろの数字の和をそれぞれ求めよ という問題になります。 実装 fn solve() { input!{ new…

【第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion】括弧列のようなライツアウト

わかんなかったです。 C - Cell Inversion 問題 2NのマスにB,Wが書かれている。各マスを一回しか選ばないという制約のもとで区間[i,j]を選び、区間のBWを反転させる。最終的に全Wとなる区間の選び方は何通りあるか? 制約: N=105 方針 2つのオーバーラップし…

【エクサウィザーズ2019 C - Snuke the Wizard】ゴーレムは道連れ、世は情け

ネタバレ風で問題のタイトルをつけたらどうなるかと考えたらこうなりました。 C - Snuke the Wizard 問題 A-Z文字列が書いたマスがN個があり、初期にはゴーレムが一体ずつ乗っています。 M個のクエリ(c, L|R)が与えられます。各クエリでは、文字cが書いてる…

【codeFlyer オープンコンテスト C - 部分文字列と括弧】括弧列の性質に関する基本問題

C - 部分文字列と括弧 問題 与えられた括弧列のうち部分括弧列は何個あるか? 制約: N=105 方針 括弧列は頻繁に題材になりますから、基本的な性質をここで抑えておきます。他にも、min segやUnion Findを使うなど、基本的なテクのコンビネーションで、非常に…

【Codeforces 1244 (Div 2) - E Minimize Difference】答えの形を決め打ちして二段階の二分探索

アイデアはシンプルですが、実装がめちゃくちゃ難しかったです。一次元の累積和とか二分探索は逆方向を扱うことも多いので、何かライブラリで工夫したいですがきれいなアイデアはあるんでしょうかね。あと、BinarySearchライブラリはi64で受けてしまってます…

【Codeforces 1244 (Div 2) C - The Football Season】どうやったら回数を減らせるか?

ほぼわかってたと思うんだけど混乱してたせいでぐちゃぐちゃになってだめだった。こういう問題は特に、考察で詰めて一刀両断しないと場合分けでおかしなことになる。 https://codeforces.com/contest/1244/problem/C 問題 pとnが与えられる wx+dy=p x+y+z=n …

【KUPC2019 B - ナップザック問題】セット売りナップザック問題

ライターの解説がなくて、解けてない人が取り残されているので解説を書いておきます。 B - ナップサック問題 問題 n個の商品があり、重さwi, 価値viである。あなたは重さがWを超えないようにこの中から商品を選び、価値を最大化したい。(これがふつうのナッ…

【KUPC2019 D - Maximin Game】カタラン数

カタラン数をこの際きちんと知っておこうと思いました。カタラン数+αの問題です。自分は+αの部分は気づきましたが、カタラン数が計算出来ませんでした。 D - Maximin Game 問題 2行n列に1..2nの数字を並べる。 ただし、 同じ行について、左<右である 与えら…

【KUPC2019 F - カズマ王国の陥没】二次元累積和 = 左端と右端に対する範囲クエリ

良い問題で、大変勉強になりました。感謝します。コンテスト中に考えてたことも含めて書きます。 F - カズマ王国の陥落 問題 思考1 思考2 真の方針 実装 考察 問題 十分に簡潔なので略。勇者がうんぬんはだるいので、攻撃と防御と呼ぶことにします。 教育DP…

組み合わせの種類まとめ

どれが使えるのか混乱することがあるため、考え方を自分なりにまとめることとした。 数え上げ系は頻繁に出てくるので、この本をいつか読んで理解を深めたい。 離散数学「数え上げ理論」―「おみやげの配り方」から「Nクイーン問題」まで (ブルーバックス)作者…

【yukicoder No.904 サメトロ】証明ができん

サメトロって何でしょう?サメがトロールしてんのか? No.904 サメトロ - yukicoder 問題 問題文が十分簡易なので略 方針 まず、Sum(Ai) = Sum(Bi)は即分かる。物理とか電気の流量の話で考えてもいいし、もっと抽象的にグラフの話と考えてもいい。 これだけ…

【Mujin Programming Challenge 2018 E - 迷路】動的なダイクストラ法

解法が面白いと思いました。 動的ダイクストラ法というのは私が勝手にそう呼ぼうとしているだけです。 問題 迷路がある。始点から終点にたどり着きたいが、動きには以下の制限がある。時間ごとに、 とどまる d[t%K]の方向に動く(d[i] = 上下左右どれか) の…

【Codeforces 1238 (Div 2) E - Keyboard Purchase】ビットDP

Problem - E - Codeforces 問題 文字列が与えられ、ここにm種類の文字が入っているとする。 あなたは一本の指でキーボードを使う。キーボードには、m種類の文字を横に並べる。 文字列を打つ。この時のコストは指の移動距離の総和である。コストの最小値は? …

【Codeforces 1238 (Div 2) C - Standard Free2play】Let's understand the problem sentence!

Problem - C - Codeforces The problem C in the div 2 contest is notorious for the problem sentence which is just difficult to understand that even a competitor ranked in yellow in AtCoder failed 5 times as he misunderstood the problem as fo…

【Codeforces 1238 (Div 2) D - AB-String】回文といえばManacherかな?

大変典型臭がするので自分の考察だけ書いておきます。あとでエディトリを見て、考えが間違ってたら追記します。 Problem - D - Codeforces 問題 ある文字列に含まれるどの文字も、2文字以上の何らかの回文に含まれている場合、それを良い文字列と呼ぶ。 ABの…

【Educational DP-Y Grid 2】使えないパスを減算する

Y - Grid 2 問題 HxWのグリッドに、通れない壁がN個ある。(1,1)から出発して(H,W)にたどり着くパスはいくつあるか? 制約: N=3000, H,W=105 方針 HWの積が1010なので、ふつうの数え上げをするとしんどいです。最初、座圧して場所によって非壁一マスの価値が…

【Educational DP-X Tower】ブロックを交換可能とはどういうことか考える

教育DPの後半は自力AC出来ないものが多かったですが、これはコンビニに行く途中にたまたま閃いて絶叫しました。 X - Tower 問題 ブロックがN個あり、ブロックiの重さはwi, 丈夫さはsi, 価値はviです。 ブロックは、その上に積んであるブロックの重さがsi以下…

【ARC075 C - Meaningful Mean】平均がK以上

理解したのでまとめておきます。 E - Meaningful Mean 問題 数列Aが与えられる。N(N+1)/2個ある区間のうち、平均がK以上のものはいくつあるか? 制約: Ai=109, N=105 方針 平均Kと聞くと脊髄反射的に引きたくなります。つまり数列をDi=Ai-Kとして、この区間…

【Educational DP-L Deque】ゲームDPは何を最大化(最小化)するかを考える

L - Deque 問題 長さNの数列Aがあります。 先手後手の順で、前方か後方から数字を引き抜いていきます。 最終的に、先手の取った数字の和をX、後手のをYとすると、 先手はX-Yを最大化するように、後手はX-Yを最小化するように手を選びます。 スコアの最大値を…

【Code Thanks Festival 2018 H - Median Game】中央値Xが実現出来るかでにぶたん

解けなかったです。エディトリの理解。正しいとは限りません。 汎用性の高い考え方な気がしました。 H - Median Game 問題 カードの山をAliceから引いていく。 引いた都度、整数の和を記録していく。 最後に、書き出した整数のうち中央値(偶数の場合は中央…

【Code Thanks Festival 2018 G - Sum of Cards】円周上のDP

解説を読んでDPだと言われても全くわからず、DP力が足りないから分からないのだと思って教育DPの全解きをし、戻ってきたら理解出来たという話。 G - Sum of Cards 問題 N枚のカードの表にAi、裏にBiが書いてある。Ai,Biともに1..Nの順列。 見えてるカードの…

【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回くらいクローンされてる件に感謝

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