AtCoder Grand Contest 052 E. 3 Letters
atcoder.jp
苦労した問題は後々のために記事を書いておこうかな・・・と
自力でのACは無理で、公式解説を読んでも理解できませんでした。
結局、以下のページを大いに参考にしました。
AtCoder Grand Contest 052 A,B,C,E問題メモ [いかたこのたこつぼ]
私の解法は、いかたこさんのページで紹介されている2つの解法をマージしたようなものになっています。
解説 (というか思考過程の気持ち)
端を例外とすると、できる操作は ABA → ACA みたいに、同じ文字に挟まれているときだけです。まず、文字列なのでこの操作における不変量を考えたくなります。
ABCを012に対応付けます。mod3で隣接項の差を考えてみましょう。
隣接項の差は
ABA は 1,2 (B-A=1 , A-B=2)
ACA は 2,1 (C-A=2 , A-C=1)
となります。
これは、2である項から1を引き、隣の1に1を加えるという操作と言い換えられます。
不変量として、「隣接項差列の総和」が使えそうです。これを活用したい！！
端の処理を不変量に組み込む方法を考えます。
まず、隣接項差列が初項の情報を持っていないのが嫌です。初項の情報がないと、列から文字列を一意に復元できません。
そこで、隣接項差列の先頭に初項の値をpushしてみます。
ABAならば、{0,1,2} CBAならば {2,2,2} です。
さて、この列で初項を変更するとどうなるでしょうか？
ABA→CBA は {0,1,2}→{2,2,2} なので、残念ながら総和は不変ではありません。
でも、CBAが {-1,2,2} ならばどうでしょうか…？
「初項の値をpushする際、mod3で正しい値なら何をpushしても良い」というルールにすることで、初項の情報を追加しつつ、「総和が等しい」条件も守れました。
こうすることで、初項に対する操作を「ある値から1引いて、隣を1増やす」操作にまとめることができました。
では、次に最終項の操作を考えます。
ABA→ABC とすると {0,1,2} → {0,1,1} となります。
これでは総和が変わってしまって嫌です。
これは、適当な(情報を持たない)値を後ろにpushすることで解決できます。
ABA を {0,1,2,-3}
ABC を {0,1,1,-2}
とします。(総和が等しいと嬉しいので、総和が0になるようにpushしました)
すると、最終項に対する操作も「ある値から1引いて、隣を1増やす」とみなすことができます。
このようにして作った列 (エンコード済列と呼びます) の集合から、元の文字列への写像は単射となっています。
また、「ある値から1引いて、隣を1増やす(ただし、端以外は1,2を保つ必要がある)」操作の集合から、元の文字列への操作への写像も単射です。
後は、この列上での最小操作回数(最短距離)を求めればOKです。
さて、２つの総和が等しいエンコード列間の距離を考えてみます。
これは、以下の方法で求められます。
まず、累積和を取る。(サンプル1が例です)
CABC : {2,1,1,1,-5} → [2,3,4,5,0]
CBAC : {2,2,2,2,-8} → [2,4,6,8,0]
次に、縦で見て差の絶対値を取ります。→ [0,1,2,3,0]
これの総和 (=6) が答えです。
証明は面倒ですが、累積和の差は「それより左に1がどれだけ余っているか？/足りないか？」を表していることを考えると分かります。
また、値が移動していく過程を考えると、「最初・最後以外の項は全て 1,2 の内のどちらかである」という条件を保ったまま移動させることが可能で有ることが分かるので、これが最小回数と一致します。
距離の求め方が分かったので、最後に元の問題を解きましょう。
まず、文字列Tをエンコードします。
次に文字列Sをエンコードするのですが、エンコードは全射ではあるけれど単射ではないので、いくらかの自由度が有ります。具体的には、初項を mod3 が等しい範囲内で自由に変更できます。(併せて最終項も変わります。)
Sのエンコード列の初項を増加せていった時、Tのエンコード列との距離は下に凸な形になります。そのため、三分探索で最小の値を求めることができます。
以下はACコードです。
Codeforces Round #732 (Div. 1)_C AquaMoon and Permutations
あまりに解説が薄すぎてかなり苦労をしたのでメモ
～～問題概要～～
のサイズの行列
を考えます。
各行は、
の順列です。
上半分は、ラテン方格になっています。
下半分は、ラテン方格とは限りません。
全ての
について
を満たす
が存在します。
個の行の選び方のうち、それらを繋ぎ合わせたものがラテン方格となる選び方を数えあげ、更に一つ構築してください。
解説
公式の解説はこちら
解説が短すぎる…というわけで、証明も含めて分かりやすく解説していきたいと思います。
列目に、数
がある状態をタプル
で表したいと思います。
すると、各行は 個のタプルの集合と言い換えられます。
この時、問題は、 個の行から
個の行を選んで、
種類ある全てのタプルを揃える問題と言い換えることができます。各行が
個のタプルを持つので、全種類のタプルを
個ずつ揃える必要があります。
まず、固有(1回しか登場しない)のタプルを持つ行は必ず採用されます。このような行を全てpickupします。
pickupした行と、共通のタプルを持つ行は選ばれることはありません。このような行をすべて削除します。
削除した後、削除していない行の集合に新たな固有のタプルが生まれた場合、それを含む行もpickupします。これを再帰的に行います。
操作後、pickupも削除もされていない行の集合について考えます。まず、問題のこの部分に着目します。
- 全ての
すなわち、1つの行がpickupされるとそれに対応する行
は、
をpickupした時か、それ以前に必ず削除されています。
pickupした行の数以上の数の行が削除行きになっているため、 に含まれる行の内、半数以上が
の上半分由来です。
に含まれる行のうち、
個が上半分由来だとしましょう。
まず、 に含まれる行に含まれるタプルは、全て
内に2回以上登場します。これは、固有のタプルを含む行は全てpickupしたことから自明です。
また、上半分由来のタプルは重複しません(上半分はラテン方格なので)。
そのため、上半分由来の行の持つタプルの種類数は 個で、全て
つずつです。
上半分由来ではない行の個数を、 とします。これが含むタプルの個数は、
個です。全ての種類のタプルは2回ずつ登場しなくてはいけないので、
個の中には上半分由来の
種類のタプルが全て含まれています。
であることから、
が示され、全てのタプルが
にちょうど2回だけ登場することが分かります。さらに言えば、全てのタプルが上半分由来の行と、下半分由来の行にちょうど1回ずつ登場します。
さて、各行をノードとしたグラフを考えます。
同一のタプルを持つノード間に辺を引くと、これは二部グラフになります。
この二部グラフのサイズがの頂点集合のうち、全ての辺について両端点の内、ちょうど片方だけが集合に含まれているような頂点集合の個数を求めればよいです。
グラフの形の特殊性から、これは連結成分数 とすると
になります(実は二部グラフなら常に成立しますね)。
まず、上半分由来の頂点と下半分由来の頂点はペアになっていると考えられます。上半分由来の頂点には、タプル
を持つ下半分由来の頂点をペアにすればいいですね。
つまり、グラフは以下のような形になります。
縦の2頂点が対応していると考えてください。縦のペアのうち、赤か青のどちらかを選ばないと行けませんが、1箇所赤を選ぶと決めると、芋蔓式に連結成分内全て赤を選ばないといけなくなるのがわかると思います。
これで問題を解くことができました。めちゃくちゃ難しいですね……
実装も重くて大変でした まだバグが残ってる可能性も高いです
ICPC2020国内予選参加記
初投稿です。チームメイトも書いてるし、せっかくだし書いてみるか～な軽いノリで書いています。チームメイトの名前出しちゃってますが、そもそもここを見るひとは知ってるやろ…(自分は有名人ではないので？)と思って書いちゃいました、ごめんね
前日譚
ICPC参加は今年で2回目です。去年は同級生二人とでましたが、どちらも競プロが合わなかったみたいで今年はどうするかな～と漠然と思っていました。
5月ごろにtuteさんからお誘いいただき、maze氏含めて3人で出場することに。当時はまだAtCoder青だったので、正直お荷物にならないか不安でした。が、tuteさんの「今週末黄色期待してる～」という圧(?)のDMのおかげもあって黄色になり、チームのカラフルさに貢献する結末は回避できました。
その後は ?UPC系に出たり、模擬国内等で結構チーム連の練習をしました。後は直前に同じチームで出たPG Battleが3位でかなり嬉しかったです。結果発表ではあまりの衝撃に飛び上がりました。
前日
ICPC的な問題に不安があったので、お荷物にならないように実装問題が出たらそれをやろうと思っていました。とりあえずサイコロ対策&Streak繋ぎでAtCoDeerくんと立方体づくりをAC。簡単だったなー模擬国内のArrowDiceもやるか～と威勢よく問題を開いたところ、"本場のサイコロ"の放つ凄まじい邪悪なオーラに圧倒されてしまい、解かずに解法だけ読んで寝ちゃいました……(最悪)
当日
普通に3限(授業内演習付き)があったので授業前にリハーサルのJだけやって授業へ。授業後はなんか緊張してずっとソワソワしていました。直前になってtuteさんからサイコロライブラリの存在を聞き、「サイコロなんて実装するだけやろｗ」と舐めていた事を深く反省しました……
コンテスト開始・・・の筈だった
5分ぐらい前からtuteさんとdiscordで通話開始し、直前にmaze君も滑り込んでコンテスト開始……と思ったところ、なんかよくわからないエラーが。運営への連絡は電話しかなかったので、押し付け合いの結果maze君が電話(ありがたい)。つながらなかったのでうちのチーム固有の現象じゃないだろうと安心してこのまま3h待機ですか？みたいなことを言って軽いノリで待っていました。しばらくして再読み込みするとリハーサルの画面が表示されたので、30分延期かな？とか話していた記憶があります。
突然のコンテスト開始
適当に再読み込みしつつ待っていたら突然問題が表示されて不意打ちのような形で臨戦態勢に。AとBを自分とmaze君の並列で通した後、Cにtuteさんが苦戦してる間にEを読みに行きました。
Eをなぜか数え上げではなく最大の桂馬の個数と勘違いし、二部グラフの最大独立集合じゃん！勝った！！と勝手に喜んでいたところ、数え上げであることを指摘され撃沈……(ちゃんと問題文を読もう)
その後はCが他の2人のおかげで通り、Eを考えていたらなんかFが解かれていました(tuteさん強すぎる…)。
Dが割と通されているのにちゃんと考察しないのは流石にまずいと思い、Dへ。最初はトリッキーな方法を考えていたのですが、通されすぎだし探索では？と方針を変えたところ解法がすっと思いつきました(これが無かったら椅子暖め人員になるところだった…) 活躍できてよかったです。
構文解析的な問題の実装に自信がなかったのでmaze君に実装をお任せし、再びEへ。手元でいろいろ実験してもいい感じのdp推移が見つからず、四苦八苦。maze君がDを通し戻ってきて全員がEを考える形になりました。しばらくすると二人が何やらコードを書き始めて、Eなんもわからん状態だった自分は置いて行かれたような気分になっていました。
5問通ってるし、予選は突破できるやろノリだった自分はEをほっぽり出してGHへ。二人はEをちゃんと考えて偉いな～と思っていたところ、こちらの反応が通じていないような感じがし、確認するとなんとマイクがミュートになっていました…(20~30分ぐらい虚空に向かって会話していた…)
後はGHとEを行ったり来たりしている間にコンテスト終了になりました。
感想
去年、まだ茶色だった時に参加したICPC予選で学内5位で敗退し、その時見たアジア進出チームの雄姿に憧れ来年こそは…！と心に決めた目標が達成できてよかったです。自分一人の力では進出は不可能だったと思うので、チームメイトの二人には感謝しかありません。Twitterで、"感動した" "自分も頑張りたい"と言ったくださった方々もおり、去年の進出チームから貰った希望や闘争心をまた次へと繋いで行けたような気がしてとてもしみじみとした気持ちになりました。
反省点としては、実装に自信がなさ過ぎるゆえにチームメイトに実装を投げつけすぎなので、実装は任せろ！というレベルまで実装力を上げたいです。(あとは典型力も付けたいです…)
とりあえずアジアもあるので、そこで活躍できるように頑張って精進したいと思います。
