Rustコトハジメ

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

競技プログラミング

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

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

LeetCode Weekly Contest 156

LeetCodeはだるいので、実際には解かず、解法を考えるだけにします。もし間違ってたらTwitterなどで教えてください。 その中で特に典型だったり、解いてみたい問題だけ解くという使い方にします。 エディトリアルがないため、復習効率が悪すぎる。 https://l…

【Educational DP-W Intervals】遅延セグツリーを使って最善値を管理する

W - Intervals 問題 長さNの01文字列と区間(l,r,a)について、文字列がこの区間の中に1が一つでも立っている場合スコアaを加算することにする。このような区間がM個ある場合に、最大スコアを求めよ。 方針 区間を右端について昇順で見ていく。今、rまでみた時…

【Educational DP-V Subtree】全方位木DP

V - Subtree 問題 木が与えられる。初めノードは白に塗られている。 各ノードをルートにした時、ルートから連続して黒に塗る方法は何通りあるか?答えはMで割って答えなさい。 制約: N=105, M=109 方針 各ノードをルートにした時にそこから連続して黒で塗る…

【Educational DP-B Frog 2】初歩的DP。DAGをかんじる

Aの一般化です。AはK=2の時でしかないため省略します。 B - Frog 2 問題 長さNのhiが与えられます。かえるは今、i=1にいます。そこから、i+1,i+2,...i+Kにジャンプ出来ます。ジャンプする先をjとすると、|hj-hi|のコストがかかります。 i=Nにたどり着くコス…

【Educational DP-U Grouping】ビットDPと足し合わせ高速化

U - Grouping 問題 N個のノードがあり、各ノードには得点Aijが決められている。 ノードをいくつかのグループに分割する。得点の最大値を求めよ。 制約: N=16, |Aij|=109 方針 E - Get Everything の強化版です。というのも事前計算をする必要があるのと、Nが…

【Educational DP-S Digit Sum】足してDの倍数 = mod Dで足して0

S - Digit Sum 問題 K以下の数字のうち、各桁の数を足し合わせた和がDの倍数なものは何個あるか? 制約: K=1010000, D=100 方針 10000桁について、全通り調べていたら910000ルートなので宇宙が滅びるまで終わりません。 次に、K以下でDの倍数のものを全部調…

ABC142反省会

初の5完!!!うおおおおおおおおおおおお!!!!!! ずっと惜しい時が続いていたので苦しかった。 といっても今回のEはどちらかというと簡単だったと思う。 最初にパラパラとEまで見て、解けると思ったのでEから解き始めた。20分くらいでAC。最近教育DPを…

【Educational DP-R Walk】DPの式を行列の掛け算とみる

R - Walk 問題 N個のノードがあり、隣接行列で有向辺の有無が与えられる。 この時、長さKのパスはいくつあるか?ただし、ループしてもよい。 制約: N=50, K=1018 方針 Kが死ぬほどでかいのがポイント。1018という数字からはダブリングの臭いがしますね。 も…

【Educational DP-Q Flowers】単調増加=小さい方から入れていく

気づくのに1時間以上かかりました。典型なので次は瞬見えしたい。 Q - Flowers 問題 花がN本並んでいる。それぞれ高さhi,価値aiである。 このうち高さが単調増加になるように何本かをとり、価値の和を最大化したい。その和を求めよ。 制約: N=105, hiは1から…

AtCoder Educational DP解法まとめ

Educational DP Contestはエディトリアルがなくて、他人の(多くの場合糞難読な)コードを読まないといけなくなることがあり、大変つらい思いをしたので、自分なりに解説をまとめることにしました。 【Educational DP-B Frog 2】初歩的DP。DAGをかんじる - R…

【yukicoder No.895 MESE】コンビネーションを注意深く計算する

No.895 MESE - yukicoder 問題 a+b+cビットの中に、aビット,bビット,cビット選び、それぞれx,y,zとする。x>y>zとなるようなzの総和を求めよ。 方針 明らかにMSB(x)は最上位でないといけない。また、MSB(z)はd-2以下でないといけない。 まずMSB(z)を決めて、…

yukicoder contest No.225 反省会

おれはyukicoderは勉強のために出てるので、今回は、絶対に解ける問題はとりあえずパスして、これは解きたいと思う問題を解くことにした。 Dが最近DP勉強でよく出てる数え上げ系ということと、結構汎用的な感じがしたので、この1問を解くという気持ちでやっ…

【Educational DP-Z Frog 3】Convex Hull Trickの勉強

はいはいグラフとみて最短路乙と思いきや、無理やんけと気づいて絶望した。 Z - Frog 3 問題 長さNの単調増加するhiが与えられる。かえるがi番目にいるとき、j=i+1,...,Nに飛ぶことが出来て、コスト(hj-hi)2+Cを払う。かえるは最初i=1にいる。i=Nに到達する…

【Educational DP-T Permutation】激ムズ。小さい方からk個がDPの添字

全くわからなかったです。運良くkmjpさんが解説してるのを見て、理解しました。 T - Permutation 問題 <と>で構成された長さN-1のSが与えられる。 順列Pを作りたい。ただし、P[i] S[i] P[j+1]のような関係でありたい。 場合の数を求めよ。 制約: N=3000 方針…

【Educational DP-M Candies】累積和を使って計算量を削減するDP

M - Candies 問題 K個のあめをN人の子供でわけます。ただし、i番目の子供は0個以上ai以下しかとることが出来ません。 場合の数を求めよ。 制約: K=105, ai=105, N=100 方針 0番目がb個とると、残りはK-bをN-1人でわけろという再帰構造になっていることに着目…

【Educational DP-J Sushi】期待値DPは遷移図を描いて式を立てる

一旦500ACをやめて、DP強化に回っています。わからなかった問題をしっかり分析します。 J - Sushi 問題 皿がN個あり、それぞれに1から3つの寿司が乗っている。N面のサイコロを振り、出た目の皿から寿司を一つ食べる。もし寿司がなかったら何もしない。 寿司…

【LeetCode No.1201 Smallest String With Swaps】スワップ可能なグループは任意の並びを作ることが可能

これどっかで見たことあると思ったんだけど、どこだったでしょうか。 https://leetcode.com/contest/weekly-contest-155/problems/smallest-string-with-swaps/ 問題 文字列と、インデックスのペアの列が与えられる。 ペアの中のスワップをどんな順番で何度…

【Code Festival 2018-D Three Letters】真ん中固定と左右ビットマップ

D - Three Letters 問題 文字列がN個与えられる。 文字列Sについて、SiSjSkを略称を呼ぶ。 出来るだけ多くの文字列に対する略称のうち、辞書順最小のものを求めよ 制約: 文字列の数は30000。文字列長の合計は90000 方針 3つということで真ん中固定っぽい空気…

【Code Thanks Festival 2017-F Limited Xor Subset】DPの計算量を減らすテクニック

F - Limited Xor Subset 問題 数列Aからいくつか選んでxorをKにする方法は何通りあるか? 制約: N=105, Sum(A)=105 方針 Aの頭から1つずつとるかとらないかの選択をするナップザック的なDPをすれば、明らかに答えにはたどり着きますが、Sum(A)が105であるこ…

Codeforcesでは整数型にusizeを使うのは危険

ハマりました。 www.rustforbeginners.com 以前にこんな記事を書きましたが、嘘でした。AtCoder, yukicoder, AOJあたりでは通用しますが、Codeforcesでは通用しません。 Codeforcesでは、usizeを使うのは危険です。 Codeforcesではusizeはたぶん32ビットで扱…

yukicoder contest No.224 反省会

疲れとインプラントの手術のダメージで死にかけてるが気合で参加した。 yukicoder contest 224 - yukicoder D 問題が理解出来なかった。 E ここでやっておいてよかったなぁと思った。 Nが異常にでかいのでひと目ダブリングだが、やったことがない問題なので…

いかにして解くか(競プロ編)

パズルのような問題を解くということには考え方の法則がある。 いかにして問題をとくか作者: G.ポリア,G. Polya,柿内賢信出版社/メーカー: 丸善発売日: 1975/04/01メディア: 単行本購入: 94人 クリック: 1,656回この商品を含むブログ (155件) を見る 競技プ…

順列の性質をまとめる

競プロで頻出の順列P。大抵は順列であることを利用して解く。 en.wikipedia.org 順列の問題に出会った時に、どういう性質を使ったかを書きとめていく。 ふつうの数列と何が違うか? 重複がない 自分より前の要素がわかれば、自分より後ろの要素が確定する k…

プライオリティキューを使って上位K個を維持する

D - 3N Numbers を解くためのテクニック。 プライオリティキューの中にまずK個を入れて、次から一つずつ取っていく際に、「一番小さいやつと新しいやつを加えて必要ならば入れ替える」という操作をすることで、プライオリティキューの中に上位K個の要素を保…

【AGC002-C Knot Puzzle】典型的誤解法の反例

C - Knot Puzzle この問題を間違えましたが、自分の解答がどう間違ってるか反例を見つけるのに時間がかかりました。他の人の解答を見ても、同じように間違えてる人が多いですから、これを共有します。 問題 ロープがN本繋いである。長さL以上連続していれば…

【ABC141-E Who Says a Pun?】Zアルゴリズムのverify

コンテスト中に解けなかったので勉強ライブ中に解いておきました。 問題 E - Who Says a Pun? 文字列中のオーバーラップしない2つの等しい部分文字列のうち、もっとも長いものの長さを求めよ 制約: N=103 方針 Nが小さいので二乗までは許される。 文字列の先…

ABC141 反省会

絶望した。頭が悪すぎる。4完で1000ちょいみたいなパフォーマンスを取り続けてもあまり意味がないので、夜遅くに参加して毎回体調崩すくらいなら、しばらくコンテスト休むかも知れない。 A-Dはいつもにも増してイージー。 E ある先頭から長さLのハッシュをロ…

LeetCodeのコンテスト参加はやめることにします

今日のLeetCodeは、Aしか解けなかったです。というかBを読み間違えて萎えてしまい、終わってしまいました。 LeetCodeの欠点は、AtCoderやyukicoderと違って入力が標準入力ではなく、関数を埋めよ形式なため、コードがすごく書きにくい(例えばRustだと、usiz…

yukicoder contest No.223 反省会

残念ながら2完のみ。Dは、自分のライブラリがバグってて死んだ。 A 倍数を約数と読み間違えて題意不明になり、出題者への不信感が募ったまま2回WAしたが、その後気づいた。 B はめられた。たぶん多くの人がやってしまったと思うけど、正方形を作っていくの…