A - Round Up the Mean

int型の割り算は小数点以下切り捨てなので、a+bに1足してから2で割れば切り上げた平均値が出てくる。

なぜか僕は(a+b)%2の値を見てから処理していましたが。

B - Two Anagrams

Cしか触ったことのなかった身にとっては、C++の　ちからって　すげー！　と思った問題。

stringコンテナのs,tを用意して文字列を代入し、sort(s.begin(),s.end()); sort(t.begin(),t.end(),greater<char>());を実行する。

すると、sの中身は昇順、tの中身は降順にソートされる。

で、if(s<t)がtrueならYes、falseならNoを出力。

ソートアルゴリズム書く必要もなし。strcmp使わなくてOK。~~そう、C++ならね~~

数字nがm回出現したとき、

-n>mならm個消す

-n<mなら`m-n'個消す

というのを、全てのnに対して確認する。

この時、数字nが何回出てきたかをカウントする配列count[]が必要になってくる。

しかし、count[]の長さは普通に考えると10⁹必要。メモリ足りない。

そこで、数列の長さNが10⁵以下に制限されていることに注目。

10⁵を超える数字nはn回以上出るわけがない。つまり、常にn>mを満たす。

ということで、10⁵を超える数字が出てきたら無条件で消すことにする。

そうすれば、10⁵以上の数字をカウントする必要がなくなるので、count[]の長さは10⁵で十分。計算量はO(N)で解ける。

……模範解答は連想配列使ってましたね。研究が必要そうです。

最初は深さ優先探索して、その後メモ化したんですが、向き情報をDPの情報に入れていなかったので撃沈。タイムオーバー。

しかも、この方法ですらTLEになるらしい。O(N³)ならそこそこ速くない……？

x軸方向の移動とy軸方向の動きを分離すればO{N²}で解けるそう。

最初の提出時にデバッグ用のprintfを貼りっぱなしにしていたのは秘密。

今回はstringの書式確認やらDPの凡ミスやら、時間の無駄遣いをしすぎました。

次回は変なミスしないようにします。