yukicoder contest 428

　Dまでの四完。Eが解けそうで解けず、FはTLEに苦しむ。

コンテストへのリンク

No.2732 Similar Permutations

　4で割った余りで分類し、同じものが二つあれば1,2を入れ替えて置けばOK。

　ただし、Nが5以上ならこれでOKだが、Nが小さいときはこれだと答えが探せない場合があるため全探索。

　コンテスト中、こういう解法を考えたがWAが出たので、何か考察ミスがあるのだろうと別の解法を探してしまった。

　が、コンテスト後、改めて考えて見ると正しそうな気がし、コードを見直したら実装ミスに気付いた。（Nが小さいとき全探索する部分でミスがあった）

　これで提出したがWA。

　Xで割った余りが3や4の場合は、1,2を置くのではダメですね。2,3を置くようにしてAC。

　解説を見たら、2で割った余り（つまり偶奇）が同じものが二つあれば、上と同じような議論ができるらしくびっくりした。

No.2733 Just K-times TSP

　各頂点を何回通ったかと、最後に通った頂点を持ってDPすれば良い。PyPyだと制限時間が厳しく、コンテスト後に定数倍高速化を頑張ってなんとか通した。

　しかし、writer解がPyPyで、シンプルかつ高速に書けていた。こういう風に書けば良かったのか……。

　同じような風に書こうとして上手くできず、itertools.productを使ったのだが。

No.2734 Addition and Multiplication in yukicoder (Hard)

　自力AC。

　ちょっと実験してみると、最終的にできる数字はA[i]たちを適切に並び替えたものになると分かった。

　なら、A[i]を文字列とみてソートし、その順に置いて行けば良いのかと思ったがこれだとWA。

　よく考えると、"2"と"21"なら"21"の方が先に置いた方がお得。

　じゃあ、"2"は"22222222222222222"として"21"は”212121212121212121"のように元の数字を繰り返したものとして判定すれば良さそう。こうみなしてソートした後、並べていったら（TLE、MLEにちょっと苦しんだけど）ACできました。