Rustコトハジメ

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

AGC037 反省会

AtCoder Grand Contest 037 - AtCoder Aだけはとった。が、300点というだけあって簡単だったと思う。しかし、以前のおれならうっかり落としていたかも知れないから、ちゃんと取り切るようになった点は成長を感じる。 あと、Bに取り組んでサンプルは通せてる…

【ABC137-E: Coins Respawn】グラフに対して前処理を行う

解けなかった問題だが、明らかに学びが多そうで、解いておきたかったので解いた。 E - Coins Respawn 問題 グラフが与えられる。ノード1からスタートし、各辺を通るごとに設定されたコインをもらえるが、ノードNについた時に通った辺の数*Pを請求される。同…

Rustで競プロするなら正の整数はusizeで扱うのが一番いいと思う理由

Rustにはプリミティブ型について、暗黙の型変換がありません。これは、競プロをする上ではとても不便です。例えば、整数型がboolに暗黙変換された方が、ビットDPなどでは特に、書きやすくなるでしょう。 ビットが立っているか調べるために、例えば、 if s & …

【AGC001-B: Mysterious Light】再帰的な性質に気づく方法

B - Mysterious Light N=1000までの部分点なら理解出来ましたし、コンテスト中にも気づくべきだと思いました。 問題 三角形の中を不思議な光が反射するから長さを求めなさい 考え方 このサンプルのうち、3番目と5番目の光に注目すると、どちらも平行四辺形の…

おれは青コーダーになるまでは絶対にAtCoderから逃げない

自分のモチベーション維持のために宣言しておく。筋トレをしてきて意識が高まっているというのもある。 おれの今のレートが6回参加して510で、過去最高のパフォーマンスが1398。 akiradeveloper - AtCoder レートの上昇はあんまり順調ではないが、個人的には…

BinaryHeapのデバグメッセージを信用するなかれ

標準ライブラリのBinaryHeapの罠 競プロで頻出のプライオリティキューですが、少しだけ注意点があります。それは、dbgマクロで表示した時の順番がpop順ではないことです。本当に正しくキューがセットされてるか知るためにデバグメッセージを出しても、そこに…

ABC137 反省会

AtCoder Beginner Contest 137 - AtCoder 今回も3完しか出来なかったが、今回のDはわかっちゃいなかったため、気分的な落ち込みはない。まだDを確実に解けるというレベルには達していないんだと思う。また一週間トレーニングします。 C 「32ビットで収まらな…

再帰型ビットDP「徒競走」

再帰で解くビットDPの実装演習。 問題によって、ループ(前向き)か再帰(後ろ向き)のどちらが自然かがあるような気がする。この問題は再帰の方が自然。 D - 徒競走 問題 N(16程度)人で徒競走をする、xさんとyさんの順序関係がM個与えられるから、矛盾しな…

座圧基本問題「ペンキの色」

実装演習として手を動かしてみましたが、1時間以上かかりました。実装的にハマった点が多かったので書き残しておきます。 ペンキの色 | Aizu Online Judge 問題 WxH(106)の平面にN(103)個のテープ(x1,y1,x2,y2)が重畳ありで貼ってある。この時、テープが貼っ…

ビットDP良問「ぬいぐるみの整理」

D - ぬいぐるみの整理 (Plush Toys) 今日の勉強メモです。ビットDPはたまに出てくるのと、わりと苦手意識があるので、良問っぽいのを実装訓練も兼ねて解いておいた。累積和とビットDPの組み合わせ。 問題 M(20)種類の数字が適当にN(105)個並べてある。このう…

座標圧縮を使う問題

座標圧縮は座標圧縮して数えて終わりもありますが、問題を解く前の前処理としてプラスアルファである場合が多いような気がしました。 xもyの重複のない点群は座圧くさい せいぜいN(1000オーダ)しかないものに帰着させる ということがポイントかと思いました…

ABC136 反省会

AtCoder Beginner Contest 136 - AtCoder 最悪すぎる。Dで発狂して終わってしまった。今週も4完以上するという目標を失敗してしまい、絶望している。 C おれは最初の要素だけは低くすることが無条件で良いので低くして、あとはindex=1から順に、広義単調増加…

ライツアウト系の基本を学ぶ

ライツアウト系の問題は、地道にシミュレートすると100%間に合わないので、フリップするとはその問題でいうとどういう意味を持つのか?ということを考える必要があります。そこまでの累積和的なものだったり、パリティだったり、問題の性質そのものを利用し…

大手前プロコン2019 反省会

AとCしか解けなかったです。Eは惜しかった。Bは問題文の誤読。Fも方針は見えていたので、個人的にそう悪いとは思っていない。G以降には着手すらしてない。全体的に問題文がいつもより長い気がした。 B B - 駒 (Pieces) 一度も動かされたことがない駒を1つ選…

二分探索を一般化するライブラリを作りました

二分探索の一般化 www.rustforbeginners.com で話したとおり、二分探索はTFの列に出現する最初のTを探す操作に他なりません。従って、インデックスを入力として、ブール値を出力とする関数を与えてあげれば、最初のTないしはFとTの境界を出力するという関数…

二分探索の本質を考える

二分探索について頭を整理します。 二分探索の応用事例 ソートされた列から最小値を探す 半分全列挙の相方を探す あるxについて成り立つか問いを設定して(貪欲に計算出来ることが多い)、問題条件にあったxを探す 二分探索とは?問い系の二分探索が本質 問…

ローリングハッシュ題材にした問題

ローリングハッシュとは? 蟻本上級のテク。決してエロい名前ではない。 文字列S(長さn)の中に文字列T(長さm)が存在するかを愚直に調べると、O(nm)かかる。これをO(n)程度にしたい。 そこで、文字列に対するハッシュ値を使うことにする。衝突は、諦める。競…

LISを題材にした問題

配列内の数の関係性について議論している問題はよく出されていて、LIS (Longest Increasing Sequenceの略) が題材となってるものはLISだと気づかないことが多すぎる。 この記事では、LISについて復習して、LISを題材とした問題例をいくつか挙げることにする…

転倒数を題材にした問題

転倒数とは 配列の中、インデックスがi < jなのに、ai > ajな(i,j)の数を言う。 これはバブルソートをする際のスワップの回数に等しい。 これを題材にした問題が時々出されるのでまとめておく。 転倒数の求め方 バブルソートの中でスワップの回数を計算すれ…

技術室奥プログラミングコンテスト#4 Day2 反省会

地獄のような難しさであった。Aしか解けなかった。 技術室奥プログラミングコンテスト#4 Day2 - AtCoder B 最初に出したのがリーフの数を数えて2以上だったら死というもの。これは4つを除いて全テスト通ってしまうけど、明らかに間違っている。リーフがない…

技術室奥プログラミングコンテスト#4 Day1 反省会

技術室奥プログラミングコンテスト#4 Day1 - AtCoder A 大きいサイドのやつは、Wより大きい微小な数を足すだけでいいじゃんまではわかったけど、以上はわからず謎の解答を出したが、なぜか通った。 B 正しく書けず3回WAした。これって、配列にKを入れてから…

ABC135 反省会

AtCoderの初回でいきなりABC2完というのをやらかしてしまい、これはちゃんとAtCoder自体を勉強しないと強くなれないということがわかり、AtCoderの問題を解きまくり、ABC3完、ABC4完と毎回上げてきた。ここからは4完を安定させて、あわよくば5完出来るという…

重複あり組み合わせの計算方法 (ABC110 D)

D - Factorization は、方針としては「素因数分解をしてその要素を振り分ける場合の数を計算する」で明らかですが、そこから方針が立たず、エディトリアルを見てもわからず、解説動画を見てなんとなくわかったようなわからないような感じになっていたのです…

LCAを実装した

LCA (Lowest Common Ancestor)は、木構造の中でもっとも低い共通の祖先を調べるデータ構造です。 これはナイーブに実装すると、ノード数分だけ時間がかかってしまいますが、Sparse Tableと同様のアイデアを用いることによってO(logN)まで落とすことが出来ま…

Sparse Tableを実装した

Sparse Tableというのは、配列上のある範囲の最小値(あるいは最大値)を持ったインデックスを返すためのデータ構造(いわゆるRMQ)で、ナイーブに実装すると明らかにO(N)かかるが、Sparse Tableだと構築にO(NlogN)かかるがクエリ自体はO(1)で終わる。 その…

Chu-Liu/Edmondsアルゴリズムを強連結成分分解を使って実装した

www.rustforbeginners.com で、SCCについて説明しました。今回は、SCCを応用して、最小全域有向木を探すアルゴリズムを実装します。一番参考になったのはこちらです。アルゴリズムとしては同じですが、SCCを使って自分で実装してみます。 www.creativ.xyz ア…

強連結成分分解

強連結成分分解(Strongly-Connected-Components, SCC)をメモっておきます。 強連結成分というのは、有向グラフにおいて、そのグループに含まれている点は、どの点u,vをとってもお互いに行き来出来るというものです。例えばサイクルなどは明らかに強連結成…

フォードファルカーソン法の復習

一回理解したと思ったんですが、もう一度読んだら全く理解不能だったため、蟻本に書いてあることを自分の言葉で書き直して復習します。 フォードファルカーソン法というのは、辺の容量が与えられたネットワークにおいてs-tの最大流を求めるアルゴリズムです…

牛ゲーの解法

スマホゲームを作ったり他のブログをやってたら2ヶ月間、競プロの勉強から離れていて、戻ってみたら牛ゲーのことすらすっかり忘れていたのでここで復習しておきます。(ものは忘れかけた頃に復習するのが良いのです。2ヶ月も開けたのは意図的です) 牛ゲーと…

ijkがMoongiftで紹介された

www.moongift.jp www.rustforbeginners.com おれが開発しているエディタijkが、Moongiftに紹介された。 Moongiftというのは新しいオープンソース・ソフトウェアを紹介している記事サイトで、時々ツイッターなどで見ることがあり、気になったものがあれば読む…