第三回アルゴリズム実技検定(PAST)

76点で中級。茶色にしてはできたと思った。途中で飯食ったの今思うと完全に余計。80点惜しかったなぁと思う。
コンテストページ
 ソースコード

String.lowerCase()で一発、やるだけ。

ある人が解けた問題の一覧と、ある問題を解いた人の人数を別で持っておいてそれぞれ計算。やるだけ。

公式を使えばいいけど数がでかすぎるのでBigDecimalでやった。その上でそれでも収まらない場合はBigDecimalから出る例外をキャッチする。

0, 1, 4, 7に関しては一箇所だけ見れば決まる場所があるので先に決める。残りはゴリ押し。

ここらへんで昼飯を食い始めてしまいロス、絶対にやめようね。

隣接リストでグラフを持って、色を保存する配列を1つ持ってその都度処理。

i行目とN - 1 - i行目に同じ文字が入ってるかどうかをaからzまで全探索。文字数が奇数な場合は真ん中はなんでもよい。

多分一番苦労した。無限にあるので幅優先でやると死にそうだけど範囲を-1000から1000程度に絞れば間に合う。実際は+1000して諸々を配列で保存できるようにしてやった。

普通に1次元でdpすると飛んでる途中で歩き出してもいい場合とかがわかんなくなったから最短時間を保存する配列とdpで記録する配列を分けてやった。

実際に行列を作る必要はもちろんない。行と列に関して何番目かを配列で持っておいて、行と列に対する操作が独立なことと2回転置すると元に戻ることを使って、転置した回数が奇数か偶数かで場合分けしてクエリを処理。

順番に処理をしていくと、先頭の子供ほど寿司の価値の最高が高くなるので誰が食べるかを2分探索で探すことができる。探せなかったら食べる子供がいないので-1。

それぞれのコンテナに対して、その下にあるコンテナ/その上にあるコンテナ/その机にある一番下のコンテナ/その机にある一番上のコンテナの4種類の配列を用意して各クエリを処理。完全にゴリ押しなので絶対にもっといい回答があると思うけどもう時間がなかったのでそのままAC。

ここで時間切れ。次がある場合は80点目標にしたい。(次回があるかは知らない本当は有料なので)