AtCoder Beginner Contest 179に参加しました。ABCDE5完(70:19)で918位でした。パフォーマンスは1549でレートは1493→1499。

感想

 特段大きな失敗をしたわけでもなくこの結果なので妥当かなぁという感じ。

A - Plural Form

 先週のAが異様に簡単だっただけに相対的に難しく感じましたが、別に難しくはないです。

B - Go to Jail

 制約からして愚直に前から調べていけばOK。

C - A x B + C

 ここでちょっと手が止まりました。A,B,C全てに対する全探索では間に合わなくて、AとBの2重forループで計算量的に大丈夫なのだろうか?だが、Cに対する全探索でA*B=N-Cを満たす約数列挙は面倒だしなぁ。と思ってとりあえず前者の方法を実装したところ、N=1e+6でも通ったので提出してAC。本番中は自信なかったのですが、調和級数の計算量はO(logN)なので結果的にO(NlogN)で普通に求まりますね。

D - Leaping Tak

 これ、セグメント木+DPで通しました。愚直なDPだとO(N2 )で通らないことを踏まえ、思いついた手法がセグメント木による区間和でした。まさかD問題でセグメント木必須の問題なんて出るわけないんだろうけど、もしかしてAtCoder STLの関係で簡単なセグメント木を使った問題が!?とか思いながら、他の手段を考えてる間に実装できると思ったので、とりあえず実装してACしました。結局imos法で解ける問題だったようですが、僕のようにセグメント木で通してる人もいたみたいですね。

E - Sequence Sum

 強いて言うならこの問題が戦犯ですね。最初はいくつか値を代入して実験的なことをし、M<=105 であることから、高々i<=MまでのA[i]において、一定周期で値が循環するループができるんだろうな、とはぼんやりと考えてました。ただ、実装が面倒くさそうだったので、数式的なアプローチとかでもっとスマートに解けないかなとなぜか思いついた手法とは別の解法を考え出そうとし、数式をこねくり回すも結局は前者の方法を実装するハメになりました。わりと早い段階で解法を思いついていたのになぜ実装しなかったんでしょうか・・・。こういう1ループ分の長さとスコアを求める問題は度々見かけますが、実装にやや苦手意識を持ってしまっているため、しっかりと身に着けたいです。また、ダブリングでも解けるようで、前に実装したことがある気もしますが、あまり身に付いてないため要復習ですね。

F - Simplified Reversi

 なんとなくセグメント木の臭いがしており、2Dのセグメント木について調べたりしていましたが、ピンとくるものがなく、そうこうしているうちに残り10分とかになってました。連想配列か一次元のセグメント木でなんとかなる感じの問題かなと思いつつ、(1,x)に置いた場合にxより右側の列は、以降の横向きクエリの影響を受けないことに気が付いたあたりで時間切れになりました。Eで時間を消費しすぎたというのもありますが、実力不足です。ちなみにセグメント木を用いたデータ構造で殴る解法でもいけますが、もっと単純な方法で解けるみたいです。

反省

 WAを出さなかったことは良かったです。ただ、E問題で時間を浪費しすぎたり、F問題もあれこれ調べてばかりで、知識&実力不足を痛感しました。セグメント木についてはまだ理解が不十分で、使いこなせていないので、この点もきちんと復習したいと思います。明日のACL Contest 1は不参加です。