AGC031 参加メモ

https://atcoder.jp/contests/agc031

ABC卒業して間もなく参加するか迷いましたが、相性のよい問題が多かったからか黄パフォ出せました！

A

問題文が難しかったです。 （（各アルファベットの個数+1）の総積） - 1 が解ですね。

B

石を2回以上塗り替えても意味ないことを利用して、数列Cから以下のグラフを作成しました。

• 頂点: 1, 2, ..., N
• 辺:
  • 1->2->3->...->N
  • i->j where i < j, C_i = C_j, C_k = C_i なる i < k < j は存在しない

あとは、頂点1からNまでの経路数をカウントするだけです。 カウントする際はDPすればよいです。

C

実装にすごく手こずりました。

まず、N=3の場合の立方体の頂点を訪問するイメージを浮かべました。 各頂点について、隣り合う頂点が異なる色になるように二色で彩色すると、AとBの異なるビットが奇数個の場合のみYESであることが分かります。

YESの場合、ルートを列挙する必要があるのですが、再帰により気合で通しました。 Bと異なるN-1次元を巡回->Bと同一の次元に移動->Bと異なるN-2次元を巡回->Bと同一の次元に移動->... というイメージです。

D, E, F

手付かず