SuperConに参加するのは今回が初めてです。
チーム紹介
PCKの相方だったpublic_yusukeさんは卒業してしまったので、弊学パソコン部の競プロerは僕だけになってしまいました（後輩にはAtCoderアカウントは作らせたけどコンテストは出ていない）。そこで問題は一人で考えることにして後輩に参加だけお願いすることにしました。今年から顧問の先生も変わったので、参加の旨を伝えたのも3日前だったのですが、何とか必要なものを提出することができました。
チーム名はeightbitです。半角英数字8文字以内だったので自己言及的に適当にeightbitにしました（半角英数字8文字は全然8bitではないのですが）。
自分の解答
問題の概要を説明すると、二つの文字列が与えられて「代入」と「入れ替え」という操作のみで変換することが可能かどうか、また可能な場合にはその手順を示すというものでした。操作にはコストが決まっており、正解数が同じ場合よりコストの小さい方が高く評価されます。
自分はまず、代入を済ませてから入れ替えをしようと考えました。まずに含まれる文字の数をカウントします。このとき
の文字数の線形結合が
の文字数になるので、26次元ベクトルの間の行列を求めることに対応します。同じ文字で置き換えない限りは文字数を減らした方がコストが低くなるので、そのような変換方法を個数制限なしナップザックで求めます。変換不可能な文字が存在する場合はNOを出力してプログラムを終了します。
は英小文字からなっており、途中の文字には大文字を使っても良いということだったので、すべて大文字を経由して変換しました。
次に入れ替えですが、最初はコストを最小にするような操作を見つけたので、それを書いていました。例えば54213という順列があった場合、1を左端に持ってくることを考えます。1の左隣から見ていって、入れ替えてもコストに無駄がないような数であれば入れ替えます。この場合1,2を入れ替えると2が遠ざかってしまいますが、1,4ならば無駄がないので入れ替えます。そのような数が必ず存在することは鳩ノ巣原理から簡単に示せます。
しかし操作数の上限がと、上記の
の方法では正解できないことに気付きました。結局、正解することを優先してコストのことは何も考えず、愚直に前から揃えていくという方法をとることにしました。
省いた部分もありますが大体こんな感じの解き方でした。
感想と結果
入れ替えの方法をもっと真面目に考えるべきでした。上手いアルゴリズムが思いつかなくても、いくつかの愚直な方法(前から揃える、後ろから揃えるなど)を比較して小さい方を取るなどの対処もできたはずです。問題に取り掛かるのも遅かったし、学校が始まって時間があまり取れなかったこともありますが、悔いは残ってしまいました。
Twitterを見る限り応募数はそんなに多くはないように見えました。また同校制限もあるので自称進としては相対的に有利だったのですが、かなり失敗したという感覚が強かったので、落ちるだろうなと思っていました。
SuperCon予選通過です！！！！やったー！！！ pic.twitter.com/tgtTmxnyLj
— season@競プロ休止 (@season1618) 2020年6月24日
SupercomputingContest2020/予選結果 - Supercomputing Programing Contest Official Site
予選通過することができたのでかなり驚きました。しかし同時に本戦の中止も発表されたので残念でした。
