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…