キーエンス プログラミング コンテスト 2020 D - Swap and Flip (700)

atcoder.jp

editional と解法が違うらしかったので自分の解放をメモするという目的で5億年ぶりくらいに解説記事を書きます (というか bitDP 解なに)

問題概要

表にA_i, 裏にB_i と書かれたカードが N 枚並んでいる．
隣り合うカードを swap と同時にそれら二枚を裏返すという操作を繰り返して，最終的に表の数字が左から広義単調増加となるように並び替えなさい． (できるなら最小手順)
(説明の都合上カードの i は0-indexed で 0<=i<N にしてます)

制約

• 1 <= N <= 18
• 1 <= A_i,B_i <= 50 (0<=i<N)

考えたこと

• まず適当に実験をしてみると，|最後の位置-最初の位置| の偶奇で表になってるか裏になってるかは一意に決まる．
• 例えば i = 1 のカードが最終的に i=0, i=2 とかに来るなら裏向きになってる
• つまりある数字を持っていける位置というのがだいたい決まってる．

• サンプル 1 を図にするとこんな感じ，隣り合うカードを入れ替える=矢印で結ばれてる数字を入れ替えるなので中央の4は左右の下側にしか行けない．

• このままでは見通しが悪いので次のように言い換えます．

i%2==1 のカードは最初からひっくり返しておいて，隣り合うカードを swapを何回か行い，表裏表裏…と見ていってできる順列を広義単調増加にしたい

これを図示するとこんな感じ

(これが最初の問題と同値なのはまあ図を見ればそれはそうって気分になるので，なりませんか？)

• こうするとどのカードが裏で表でとか何も考える必要がなくなって位置関係だけ見ればいいので嬉しい

• そして左から偶数番目，奇数番目に来るカードを分ける分け方は N 個から N//2 個選ぶので N_C_N//2 通り(N=18で48620通り) なので全探索できそう

• 左から偶(奇)数番目にくるやつは，最終的に表(裏)が選択されるので表(裏)の値でソートしてあるのが必要条件．

• ここで値が被ってるとめんどくさくなる気がするのですが，(値, 初期index) の二値でソートを掛けると同じ時に初期 index の順番が崩れないようになって，最小手数を考えるとこれが唯一最適． (最終的に同じ値同士で初期 index が崩れてる場合そこをひっくり返すための swap が行われており，それは無くても良い操作なので)

• なので，偶奇に選択されるカードに二分 -> それぞれソート -> それらを組み合わせて全体で広義単調増加になっているかを確認 -> なってるなら操作回数を計算して ans を更新

• 初期 index と最終 index が与えられて swap 回数を求めるのは転倒数なのでバブルソートとかで O(N²)でできます

実装

※ コンテスト中に通したものが解説には汚かったので適当に書き直してます

インプット

i%2 == 1 の時にひっくり返していれる．ついでに初期 index を持っておく

import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

組み合わせ全探索 and 解の更新

Python だと itertools を使うと組み合わせの全探索が簡単にできて嬉しいです．
Acards が偶数番目に来る， Bcards が奇数番目に来るやつで，それぞれ Ais/Bis に (値，初期index) のタプルを入れてソートします．
(こういう後で更新するわけではなくデータだけ保持したいような奴はリストではなくタプルで持つと若干早いです)
そして組み合わせて条件を満たしてないのははじいて，後は solve() で転倒数を求めて答えの更新をして終わり．

どうでもいいことを書いておくと ans の初期値に INF=float("INF") を使っているのですがこれ int 型とかとの比較がそんなに早くないので非推奨らしいです．
今回みたいな一個の解の初期値に入れる分には良いけど，配列全体の初期値とかに入れて配列長だけ比較が走ったりするとかだと差がつくかも．

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n: # 組み合わせた時広義単調増加になってない
            flag = True
            break
        bn = n
        ii.append(i)

    if flag: continue 

    ans = min(ans,solve(ii))

提出

Python3 (1508ms) atcoder.jp

PyPy3 (1026ms) atcoder.jp

bitDP だと結構 Pythonだとギリギリだったらしいですが， 組み合わせ全探索をするとN_C_N//2*O(N²) とかなのでまあ numpy とかしなくても生Pythonでも通るくらいにはなります．

感想

これをさっさと解けたのは良かった．(まあ bitDP が見えなかったおかげで解法ガチャに勝利したみたいなところはあるのですが)
けど 一時間あったのに E が解けなかったのは辛いですね．． 700 を50分で通したので温まりを確信してちょっと集中が切れてしまったのですが結局900が結構解かれて微増くらいでした．

ところで明日の10時から卒論の進捗報告会があって一応そこまでに一通り完成させて見せますって言ってるのですが，まだ完成してません．大丈夫なのですか