Rustコトハジメ

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

大手前プロコン2019 反省会

AとCしか解けなかったです。Eは惜しかった。Bは問題文の誤読。Fも方針は見えていたので、個人的にそう悪いとは思っていない。G以降には着手すらしてない。全体的に問題文がいつもより長い気がした。

B

B - 駒 (Pieces)

一度も動かされたことがない駒を1つ選び

これを読み間違えた。「各ターンごとに」なのか「いままでに」なのかがわからなかった。ここはきちんと書いてほしいと思った。

読み間違えた結果、同じ駒を何度も動かすことが可能になってしまい、解法が思いつかなかった。制約がわかっていれば、B相当という感じ。1時間悩んでもわからず先に進み、Cが簡単だったので、Bがこんなに難しいわけはないと思い戻ってみたが、結局わからなかった。

C

C - カード並べ 2 (Arranging Card 2)

これはカウントを育てていけばいいだけ。カウントは単調にしか増えないから、リピート回数は単調に減る。

差分更新系?グリーディ?分類がわかりませんが、データ構造を持ちながらイテレートする問題はよくある。ウィンドウなのかな。

D

D - FizzBuzz (FizzBuzz)

N桁の数字を先頭から読んでいき、その度にFizzBuzzをする。発したFizzBuzzがM個与えられるから、数字が何通りありえるか計算せよという問題。

これは単純にわからなかった。というか、mod 3で状態を作ってしっかりと分類してDPするという方針自体は立ったけど、考えが整理出来ずに実装まで着手出来なかった。これは解きたかった。DPの良問だと思った。あとで自力で解答しておきたい。

E

E - 最悪の教頭 (Worst Head Teacher)

これは位置(x,i)がO(1)で計算出来ることがわかればあとは二分探索とわかるのだが、残念ながら二分探索のコードが正しく書けなかった。悔しいのでコンテスト後に、おれの考えた最強のにぶたん抽象化ライブラリを作り、やっつけた。

www.rustforbeginners.com

F

F - 天秤とコイン (Balance and Coins)

ただの累積和+DP。正しい方針は立っていたが、Eで詰まって心が折れたため投了した。