AtCoder Grand Contest 037

結果

順位   393rd / 2317
パフォーマンス   1841
レーティング  1885 → 1881(-4)

 800点のC問題を通せて喜んでいたけどレートは下がるのか。

 AtCoderをやっている上でmerom686氏のレートを超えるというのを一つ目標としてきていたのだけど、今回提出せず撤退もできたmerom686氏が最後C問題出してWAになってレート大暴落が発生しており、なんか超えてしまった。自分のレートも下がっているのでひどく微妙な感じだ。こういう事故っぽいのではなぁというのもあるし、そもそも黄色くなっていない時点で論外というのもそう。はい。漫然と黄色を目指します。

A - Dividing a String

 3文字以上の塊は出てこなさそうだなと直感で判断してDPをし始めた。初期化とか遷移での添字とかいろいろ手間取りつつWAも出しつつなんとか通したという感じでまったくスマートではない。

 提出

B - RGB Balls

 コンテスト中には解けなかった。A問題解いた直後に30分くらい考えてわからなかったので順位表の様子を見てC問題へ行った。C問題を解いた後戻ってきたけど方針すらさっぱり立たない感じで時間切れ。サンプルが見るからに掛け算をしてくださいという出力になっていることはわかったけどなにをどう数えつつ掛けていけば良いのかさっぱりわからなかった。今日解いてみたけど、解説PDFはなんだかよくわからなくて、とりあえずわりと貪欲っぽくやっていくとなんか数が合って通った。類問出されても解ける気がしない。

 提出

C - Numbers on a Circle

 後ろからやっていくということに気づいて、配列の中から最大値のインデックスを取り出すというところにやや悩んだ挙句セグメント木を持ち出してくるということをやった。冷静に考えればstd::priority_queueで十分なのに。まぁ将棋ソフトの方でセグメント木を使った最小位置の取得というのは書いていて、それをコピペするだけだったので時間の短縮にはなっていたかもしれない。

 B_i = A_iとなった場合に最大値として再び取り出すことがないようにセグメント木上では0にしておく変な実装になってしまい、初期化の部分でそれを忘れて2WAほど。綺麗な実装がよくわからなかった。

 提出