Rustコトハジメ

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

yukicoder contest No.223 反省会

残念ながら2完のみ。Dは、自分のライブラリがバグってて死んだ。

A

倍数を約数と読み間違えて題意不明になり、出題者への不信感が募ったまま2回WAしたが、その後気づいた。

B

はめられた。たぶん多くの人がやってしまったと思うけど、正方形を作っていくのが最善と信じてしまい、2つWAがとれなかった。

C

ライツアウトにありがちな、111の繋がりだけに注目すれば良いという話。

  • 1が一回ならそのまま消せばいい
  • 1が2回なら、単に消してもいいが、11->100とする方が全体的には得。もしこれが上の桁と繋がらなければ消せばいいし(合計コスト2)、繋がれば消すコストが省ける

という考察が出来ればおわる。

インターバルに区切って、それが接続できる場合に接続するみたいな話は座圧でも出てくる。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0536

「問題の性質を利用して情報を圧縮して考える」というのはよくある。例えば、ABCから成る文字列の中でABCをBCAに並び替えるとしたら何回出来ますか?という問題は、「BCは並び替わらない」ということに注目すると、BC=Dと置き換えて圧縮することができる。

難易度も高くなく、教育的な問題だと思った。

D

ある値で割ってしまうと、後にそれより大きな値が出てきても変化しないことは明らか。ヒープ性みたいな話で、log回しか変更されないのかなと思った。

だから、ある時に、割る値より大きなものを列挙して、それが効率的に出来ればよい。まさに最近やってたskiplistの出番ではないか!と思って、それをラップしたmultisetを使って実装したが、multisetの実装が間違っていて死んだ。ratedなコンテストで死ぬよりは良かったと考える。

skiplistに目がくらんで、優先度キューを使うという発想は思い浮かばなかった。

わりと計算量が重かったらしく、まともなC++のコードでも300msくらい。おれのコードは1500msでぎりぎりだった。