Rustコトハジメ

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

競技プログラミング

【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 順列の問題に出会った時に、どういう性質を使ったかを書きとめていく。 ふつうの数列と何が違うか? 重複がない 自分より前の要素がわかれば、自分より後ろの要素が確定する 1…

プライオリティキューを使って上位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 はめられた。たぶん多くの人がやってしまったと思うけど、正方形を作っていくの…

おれの自作スキップリストでABC140-Eを通したぞ!!!

ふらふらです。おれお疲れ様。スキップリストはこれにて一旦終了。 www.rustforbeginners.com で、ABC140-EはRustの1.17以上じゃないとrange関数がないから不利という話をしました。 www.rustforbeginners.com これに対して、コンパイラのアップデートが今す…

スキップリストをてきとうに実装したがだめだめだったというお話

AtCoderのRustコンパイラはまだ1.15であり、順序つきセットのrange関数を使うことが出来ない。これがあるなしで差が出る問題が存在するため、自分で順序つきセットを実装しようという発想になった。BTreeSetを再実装しても面白くないのと、そもそもめんどく…

【天下一プログラマーコンテスト2016予選B-B 天下一魔力発電】右から括弧列を見ていく

たぶん想定と違うので紹介。O(N) 問題 括弧列がある。左から辿っていき、その都度反転することが許される。 移動がコスト1、反転がコスト1とした時、この括弧列を対応がとれたものにするにはコストいくらかかるか? 方針 対応がとれているかの判定にはスタ…

BTreeSetをタプルで使用した時のrange関数の挙動

Rustで競プロをする時に役立ちそうな情報です。 何かソート可能な値であれば二分木に突っ込むことは可能だろうというのは想像が付きますが、rangeもタプルで使うことが出来るようです。 use std::collections::BTreeSet; fn main() { let mut s=BTreeSet::ne…

【yukicoder No.877 Range ReLU Query】2つの汎用的な解法

いかにも競プロ臭のする問題。感動した。 No.877 Range ReLU Query - yukicoder 問題 長さNの数列Aが与えられる。 長さQのクエリ(l,r,x)が与えられる。 各クエリについて、[l,r]の範囲でmax(ai-x, 0)の和を計算せよ。 制約: N<=105, Q<=105 方針1: beet法 ラ…

【ABC140-F Many Slimes】multisetがほしい

ABC140-Eではsorted setがないから解けなかった。 www.rustforbeginners.com 今回の問題は、Rustがそもそもmultisetがないから死ぬという問題。まぁ、仮にsorted setがあればあとは別途カウンタを持って出来るような気はするが。いずれにしろ、コンパイラバ…

【ABC140-E Second Sum】BTreeSetを使って実装する (1.17以上限定)

E - Second Sum 問題 長さNの順列Pが与えられる。 このうち、範囲[l,r]について2番目に大きいものをXlrとする。 すべての範囲について、Xlrを足し合わせた合計を求めよ。 方針 二番目に大きいというのがどういうことなのか考える。これは、あるPiを含む範囲…

【AOJ0603 電飾】ABC140-Dの類問

ABC140-DがDにしては難しく、類問があったらいいなと思いました。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0603 ここでも紹介しましたが改めて。 ライツアウト系の基本を学ぶ - Rustコトハジメ 問題 長さNの01列Aが与えられる。 010101の…

LeetCode Weekly Contest 153 反省会

初LeetCode。3完。まぁ、Cまで解き切ったことは評価出来る。 LeetCodeの形式はめんどくさい。あとRustの場合、整数値が全部i32で渡されるから、usizeに変換しないといけなかったり、相当うざい。変なimportが残ってると、コンパイルエラーになったりもする。…

ABC140 反省会

AtCoder Beginner Contest 140 - AtCoder 4完。今回の4完はむしろよくやった方。 この前は5完まで22秒足りなかったが、今回は1分前に4完の解法を提出した。Dが全くわからなくて本当にやばかった。実際難しかったようである。 1-2-3-7-5-5って感じのコンテス…

yukicoder contest No.222 反省会

鬼のセグメントツリー祭。★の数的に頭の3問しか勝負にならなそうなので、これだけは解くぞと思って望んだが、Cが解けなかった。2完。順位は77/133 A No.875 Range Mindex Query - yukicoder ただ最小値を求めるだから簡単だが、そのインデックスを求めろとい…

【DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C ロト2】約数の数に問題を圧縮する系

なるほどなーと思う問題でした。自力AC出来なかったです。109の約数がたかだか1300個程度しかないという知識を活かして問題を圧縮する系です。今回もそんな臭いはしたけど、一歩踏み込めなかったです。 C - ロト2 問題 長さNの数列aが与えられる。このうちai…

【第5回 ドワンゴからの挑戦状 予選 B Sum AND Subarrays】本当に400点なのか?

XORを扱う問題は多いけどANDを扱う問題は少ない。大変良く出来た問題だと思ったのでまとめ。 B - Sum AND Subarrays 問題 長さNの数列が与えられる。(N=103) この数列のうち、範囲[l,r]の和はN(N-1)/2個あるが、この中からK個選び、ANDをとりたい。その時の…

【ARC076-B Built?】クラスカル法の理解「どうせ選ばれない枝には興味がない」

D - Built? 問題 平面上にN個の点がある。点(a,b)と点(c,d)を結ぶ時、コストmin(|a-c|,|b-d|)がかかる。いくつかの点を結んで、N個の点を連結させたい。その時の合計コストはいくらか? 方針 最小全域木のコストを調べればよい。(閉路があるなら、枝を削除…

【AGC034-A Kenken Race】ある瞬間に着目する

A - Kenken Race 問題 N個のマスがあり、石が置いてあったり置いてなかったりする。Nは5乗。 すぬけくんはAから、ふぬけくんはB(A<B)から、それぞれCとDを目指す。一回の操作につき、自分の1つ右か自分の2つ右にしか移動出来ない。石のあるマスや、相方がいるマスには移動出来ないとすると、これは達成可能か? 方針 一人でやるならば簡単。 C<Dの時も簡単。まずはふぬけを動かしてからすぬけを動かせば一人でやるのに等しい。 C>Dは、すぬけくんがふぬけくんを追い越す必要があるため、追い越すとはどういうことなのかに注目する。 すると、 SF○ (○はすぬ</b)から、それぞれcとdを目指す。一回の操作につき、自分の1つ右か自分の2つ右にしか移動出来ない。石のあるマスや、相方がいるマスには移動出来ないとすると、これは達成可能か?>…

【AGC032-A Limited Insertion】最終図を想像する + 厳しい方から攻める + 逆算する

AGCはAでもすでに難しいことがある。早くB,Cで打率5割マンになりたい。 A - Limited Insertion 競プロあるあるな考え方なので紹介します。 問題 長さNの数列を以下のようにして作る。 i(1<=i<=N)番目の操作ではj(1<=j<=i)をj番目に挿入する こうやって出来た…

【TTPC2019-F Road Construction】グラフの変形

コンテスト中に解けなかったので解いておきます。 F - Road Construction 問題 コストつきのグラフが与えられる。これらの辺は最初、有効になっていない。このうち、いずれかの辺を有効化して、wからx、yからzの両方が通るようにしたい。最小のコストはいく…