読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

GCJ 2017 Qual

A 問題

+- の列があって、連続する K マスを反転するのを繰り返して全部 + にする問題。まったく同じ問題が蟻本にある。

B 問題

10 進表記で数字が昇順になるような N 以下の最大の整数を求める問題。なるべく上位桁は動かさない方がいいということ、ある桁の数字を 1 減らしたらそれに続く数字はすべて 9 にすればいいことを踏まえれば解くことができる。

C 問題

区間の長さだけ保持しておけばよくて、大きい区間から順に分割していくのを繰り返せば良い。 分割過程では値が重複しやすいため、同じ長さの区間をまとめて処理すれば速くなりそうである。

分割の様子を図にすると以下の通り。

木の高さは O(log n) である。また、各レベルにおける値の種類数はたかだか 2 である(これは最大値と最小値の差がたかだか 1 であることから分かる)。ゆえにまとめて処理すれば O(log n) 回で収まる。

D 問題

条件を整理すると

  • どの列/行も、x を 2 つ以上含まない
  • どの列/行も、x と o の両方を同時に含まない
  • どの列/行も、o を 2 つ以上含まない
  • どの対角線も、+ を 2 つ以上含まない
  • どの対角線も、+ と o の両方を同時に含まない
  • どの対角線も、o を 2 つ以上含まない

となる。あるマスに o が書かれているというのは、あるマスに + と x の両方が書かれていると言い換えられる。この言い換えにより条件はよりシンプルになる。

  • どの列/行も、x を 2 つ以上含まない
  • どの対角線も、+ を 2 つ以上含まない

+/x を o に変える操作は許されているので、+/x は完全に独立して考えることができる。よって、それぞれ独立に最大化すればよい。これは貪欲にできる。


Splay Tree の可視化

ChromeFirefox では少なくとも見れます。重くて見れない方はごめんなさい。

https://pekempey.github.io/splay_tree/splay_tree.html

Link-Cut Treeの可視化(失敗作)

Link-Cut Treeをうまく可視化できないか考えてました。

exposeの可視化を目標としていましたが、うまい可視化が思いつかなかったので、あまり役に立たない可視化だけ公開します。察しのいい人なら実装まで想像がつくと思いますが、二分木のmerge/splitに慣れていない人だとこれだけを見て動作を理解するのは厳しいかと思います。

expose というのは頂点 u と根をパスで繋げるという操作です。

ChromeFirefoxでは少なくとも見れます。重くて見れない人はごめんなさい。

https://pekempey.github.io/link_cut_tree/lctree.html

高速版。lctreeの高速さが感じ取れます。
https://pekempey.github.io/link_cut_tree/lctree_fast.html

木の描画はいい感じのライブラリがあったら差し替えたいものです…(Reingold-Tilfordとかいうのが良さそうなのかな)

Mo's Algorithmの可視化

SVG で描いてみた。処理落ちしたらごめんなさい(結構重い気がする)。

https://pekempey.github.io/mo_algorithm/mo.html

Internet Explorer では見れないのでご了承ください。

HourRank 19 screencast

Google Drive 上に screencast を置いといた。コードを書いてる最中にかなり手が止まってて面白い。
https://drive.google.com/open?id=0B-_lUQRjdBisWXBMWFBNNDlmbEU

全く関係ないけど前回のABC057のscreencastも置いておいた。
https://drive.google.com/open?id=0B-_lUQRjdBisaWs1MWxZUTVIXzQ


B も C も典型的だったが、C の実装で迷走してしまい(しかも結構バグって)辛かった。思いついた処理をスッと書けなかったのは気分が悪いが、順位は悪くなかったので良しとしたい。

問題文の細部を読むのが面倒だったのと、サンプルを手計算するのが面倒だったという理由で愚直解を一度書いたんだけど明らかにタイムロスである。

競技中に書いたコードとは少し異なる。更新する箇所が結構多くて書いてて混乱する。全方位は慣れないなぁ…。

max は逆元がないから面倒なんだけど、multiset で全部処理してしまえば簡単。しかし 2sec ぎりぎり。