AtCoder Beginner Contest 167 - いろいろな記録

ABC167お疲れ様でした。

73分5完1ペナでパフォーマンスは1564でした。反省が少し多いです。

2'15 AC

最初一瞬読解ミスしました。Pythonなら一瞬だなとか思ってました。

7'35 AC (1WA)

早とちりして1ペナ出しました。つらい。てか遅すぎる。B問題でもまず落ち着いて場合分けしてから一気に書き上げる。

20'37 AC

bit全探索するだけ。添字をバグらせて5分ほど溶けたのでしんどい。

51'08 AC

dfsを使ってループを検出して、頑張って場合分けしました。ダブリング知らなかったマンです。添字でごちゃごちゃして時間かかりすぎ。ちゃんとノートにメモ取ってから一気に書き上げたほうがいいですね。

73'06 AC

面白い問題でした。「隣同士が違う」ものに着目して考えると、隣同士同じ色のペアが $i$ 個になる場合の数は、 $n$ 個のボールの $n-1$ 個の隙間に $n-i-1$ 個の仕切りを入れていく場合の数に言い換えられます。

あとは、各ブロックに対して、先頭なら $m$ 種類、そうでないなら $m-1$ 種類の色の割り当てかたがあるので、適宜modを取りながらかけていけば良いです。

f:id:bustle0309:20200511101507j:plain

最初DPかと思ったんですが、メモリが足りないことに気づいて数学に切り替えられたのでよかったです。

解けそうだった。残念。

方針としては、'(' の数が ')' の数を超えないように繋げて、かつ '(' と ')' の個数が同じであればいいです。一つの文字列内での '(' と ')' を累積和的に管理するという方法をTwitterで見たのでやってみます。

---

Eの反応が早かっただけに青パフォ逃してしまったことを残念に思っています。

たらればですが、Bで3分、Cで5分、Dで5分巻いてノーペナならば55分で5完となり、パフォーマンスは1700ほどでした。

今回は特に、丁寧にメモをしてからコードを書くということをおろそかにした結果、ミスして手戻りするということが多かったので、もう少し地に足つけてコンテストに望もうと思います。

あと速解きも練習します。これはバチャコンに出るしかないですね。

次回も頑張りましょう。