妄想の一丁目

　昨日やった天国の一丁目についていろいろ考えていたことを残しておく。本編とはほぼ関係がない妄想。

ゲームシステムのシナリオに対する干渉

　3面の最後、発せられた弾幕を避けるかどうかはそのままこの場所に留まるか現世に帰るかの二択に対応しており、話の展開に大きく影響する。しかしここまでシューティングゲームとして、弾幕は避けるものとして進めてきたプレイヤーにとってみればここでもやはり避けた結果到達するものの方が正しいエンドなのであり、避けるのに失敗した結果到達するエンドは間違ったものとなるだろう。それはそこまでの文脈の妥当性とはまた違った次元としてエンドに優劣をつける要素になる。

　プレイヤーにある種の選択を迫るゲームでは、時にプレイヤーの「ゲームであるからこそ」発生する無責任な振る舞いを指摘するような仕掛けが施されている場合があるらしい。自分はやったことがないので言及するのも気が引けるが、たとえば殺す必要のないキャラクターを殺したりだとか、恋愛ゲームにおいて2周目では違うキャラクターを攻略し始めたりだとか、そういう行為についてある種糾弾するかのような展開が用意されているとのことだ。自分の理解ではそのような仕掛けが導入される理由は「ゲームの世界(虚構の世界)に対して真剣に向き合っているか？」という疑問の投げかけをしているのだと思っている。

　翻って天国の一丁目について考えると、文脈の妥当性を顧みず「今まで避けるのが正解だったから最後でも避ける」とすることに対して、先の問いかけと同様な形としてその安易さを糾弾する仕掛けを入れたくなる。実際のところ現世に帰る選択をすることが妥当であると判断できるほどの文脈があるわけでもなく、どちらかというとヒロインの独善性が目立つ選択であるとすら思える。だからこれは天国の一丁目についての話ではなくて、ただの妄想。

キャラクターを地獄に落とす

　天国の一丁目をプレイしたときにはそこが地獄であるという深読みをした。結果的にそれは違っていたようだが、キャラクターを地獄行きとすることについて考えてみたい。地獄に落とすためにはなんらかの罪を犯していないといけないわけだが、それがあまりにも重い罪であるとプレイヤーからの心象が悪くなってしまう。ここは天国と地獄というモチーフであることも考えて、「自殺」というのが罪とするのが良いんじゃないかと思った。

　主人公が地獄へ来た理由が自殺ならば、ただ現世に帰しただけではやはり同様のことが繰り返され、再び地獄で相見えることになるだろう。ヒロインがルールを破った罰として消滅させられなかったとして、(そして天使は死者の死因がわからないとして)2回目に会った時点でその意味がわかるだろうか。事態はループ物の様相を呈してきている。2回目でわからずとも3回目、4回目と繰り返されれば、遅からず死因には考えが及ぶだろう。何も語らずとりあえず現世に返せばそれで良いとするヒロインの独善的な態度では何も救えやしないというところに気づいてから物語は始まる。そもそも主人公が自殺する理由はヒロインが地獄にいることを知っているからなのだ。

　ところでヒロインも地獄にいるからには、やはり罪を犯していなければならない気がする。主人公と同じ理由では芸がないが、他に理由も思いつかない。これは困った。困ったのでヒロインの罪は遡及的に定められたものとしよう。つまり主人公を何度も自殺させることになったことそれ自体が罪であり、その罪によって地獄にいることにする。それは時空がねじれていないかって？ そんなのよくあることじゃないか。

　タイトルを回収する。主人公とヒロインが落ちた地獄は、しかし無間地獄ではないのであった。その地獄においてきちんと罪を清算することで天国へと昇っていく。主人公の罪は自殺であり、さらに言えば何度現世に戻ってもヒロインの気持ちを無視して何度でも地獄にやってくることである。ヒロインの罪は主人公の事情を顧みず何が何でも現世に返そうとするその態度自体と言える。これらが互いに向き合った真なる対話によって解消されるとき、ようやく二人は天国へいくことが許されるのだ。すなわち地獄は天国へ至る準備段階であり、さしずめ天国の一丁目、ということなのである(ちょっとこじつけ感があるか……)。

　最後に蛇足。これをゲームシステム的に再現するならば、最後のところだけプレイアブルキャラクターがヒロインになって、ヒロインvs主人公という形になりそう。主人公を打ち倒すと主人公は現世に帰るが、再びやってきて愕然とするエンド。打ち倒されれば二人ともこの場に残るが対話は行われず、この場が地獄であることが明かされ、二人は別々の場所でそれぞれに苦しむエンド。倒しも倒されもしないまま一定時間が経過するとセリフのやり取りが始まり、トゥルーエンド。こんなのいくらでも前例がありそうだなって思うのでボツです。終わり。

天国の一丁目

　天国の一丁目というゲームをやっています。

ゲーム面

　シューティングゲームは東方天空璋を少しやったことがあるくらいで、それもEasyをノーコンクリアはできないくらいの腕。というわけで今回もエンド2を見るのに結構苦労したわけだけど、それでも二日合わせて計5時間くらいのプレイ時間なのかな。慣れると多少避けられるようになってくるというのは本当にあって、こういう成長要素はゲームの良い点だなと思う。

　1面道中が普通に難しい。ボスはまぁなんとかというところだけど、ツツカナ(名前！)はともかくサクラチルがなんで当たらないのかよくわからないままだし実際時々当たる。にしてもマスティマはサクラチル、なのか。このキャラクターの本名は……。それはそういうことなんでしょうかね。

　2面のBGMが軽快で好き。しかしオトビの最初はまったく避け方がわからなかった。めちゃくちゃ逃げ回ってるとなんとかなるようなならないような。「ひぇ～～」の余裕そう感。Aim_to_GO_Tombosの最後終わった後も一発撃ってくる意地の悪さね。三翼のセラフィムもサクラチルと同じすり抜けで避けられたりダメだったり。上手い人は狙ってすり抜けられるのか？

　3面冒頭の会話、一枚絵が出てくる直前のセリフがすぐ飛ばされてしまうのでまともに読めないのは残念。vs門番はHeart of the Sunsetが本当に無理。一度もノーミスで抜けられてないと思う。Shooting Starも厳しい。Wondrously Beautiful Dayも無理。やはりラスボスだけあって強いんですね。音楽はここに来て解放される重低音が迫力を煽っていて良いんだけど、ボスの造形がもうちょっとおどろおどろしい感じでも合っていたのかなと思った。

シナリオ面

　冒頭の会話、「天国と呼ばれる場所」という言い方の時点であぁここは地獄なんだろうなと思ったよね。なんだろう、その想定がどこまで外れたものなのかというのも詳しいキャラ設定を見ると怪しいところなわけだけど。

　やはりステージが3つだけではなかなか説明不足になってしまうんだろうなと感じる。最後の二択は結局、撃たれた結果陥るエンド1の方が「間違った」ものであり、回避することで到達できるエンド2の方が「正しい」ものであるという印象になってしまう。シナリオに対するゲームシステムの干渉。正直エンド2の方が全てがむちゃくちゃになる結末かと思ったけど、そうでもなかったんだね。

　キャラクターの動機に説得力があるか。僕にはわからない。学者志望者がこんな動物を目撃してしまったら帰りたくなくなるのも当然なのでは？ そこについて何も考えないのだろうか？ だいたい学者みたいな現実レベルでの幸福にとどまった考え方をしている時点で器が小さいんだよな。2択を突きつけられたらその構造自体を破壊しにいくべきであり、今回なら門番の首をへし折って扉をこじ開けてこっちとあっちの行き来を自由にしてしまうことを目指さなければ。お前は何をしているんだという気持ちになる。

　最後にどうでもいいこととして、死後の世界というものを考えるたびに、そこでは自殺できるのかなということに思いをはせたくなる。天国では自殺したくなるような辛いことは起こらないって？ そう……。

AtCoder Grand Contest 029 C - Lexicographic constraints

問題

　個の未知の文字列について、これらが辞書順に並んでおりの長さはであるとわかっているとき、文字列に含まれる文字の種類数として最小の値を求めよ。

解法

　含まれる文字の種類数について二分探索をする。まで決まったとき次の最適なはより辞書順で大きいもののなかで一番小さいもの。つまり使う文字を から として

• のとき
  0で埋めていく。

• のとき
  以降の文字を消して番目の文字を一つ大きい文字にして必要なら以降上の桁へ繰り上げていく。

　ということをやっていけば良い。これは0以外の文字についてだけstd::map等で位置と文字の関係を保持していけばで判定できる。二分探索でさらにかかっても十分間に合う。

反省

　「最小の値を求めよ」という問われ方をしたときに二分探索が思い浮かばないなんてことは流石になくなってきたわけだけど、判定問題に落としたところで問題が簡単になっている気がしなかった。根本的に次に来るべき文字列が辞書順最小のものということを明示的に意識できていなかったし、当然文字目を一つ大きくして繰り上げしていけばいいという考えには至らなかった。もっと問題の性質について考察をできるようになりたい。

　実装面についてはstd::mapについてイテレータで範囲を指定してeraseするやり方があることを知った。別に計算量が変わる類の話ではないだろうけどeraseで帰ってくるのが次のイテレータだから……みたいなことを考える必要がないので少しだけコーディングが速くなりそうだしこういうのは有用だと思う。std::vectorとかでもこういう指定の仕方できるわけだから当然std::mapにもあるんじゃないかと考えるべきなんだろう。

//先を全部消す
mp.erase(mp.upper_bound(A[i - 1]), mp.end());

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N;
vector<ll> A;

bool isOK(ll x) {
    if (x == 1) {
        for (ll i = 1; i < N; i++) {
            if (A[i - 1] >= A[i]) {
                return false;
            }
        }
        return true;
    }

    //入ってないところは0ということを示す
    map<ll, ll> mp;

    for (ll i = 1; i < N; i++) {
        if (A[i - 1] < A[i]) {
            //0を入れていくだけなので何もしない
            continue;
        }

        //先を全部消す
        mp.erase(mp.upper_bound(A[i - 1]), mp.end());

        //x - 1でない位置を見つける
        ll j = A[i];
        while (mp[j] == x - 1 && j > 0) {
            mp.erase(j--);
        }

        if (j == 0) {
            //全部ダメ
            return false;
        }

        //ここの桁の値を1上げる
        mp[j]++;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    A.resize(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll ng = 0, ok = N;
    while (ng + 1 != ok) {
        ll mid = (ng + ok) / 2;
        (isOK(mid) ? ok = mid : ng = mid);
    }
    cout << ok << endl;
}

ACM-ICPC 2018 Asia Yokohama Regional 参加記

結果

本番まで

　メンバーの一人はキャンパスが違うということもあって特にチームで練習するということはなく、各個人で勝手に精進を重ねる程度。僕はARCの3問目を埋めていっていた。一応予選時からレートは+150くらい。まだ闇雲にでも解けば上がる段階ではある。

　リハーサルではCLionでちゃんとコーディングできることを確認する作業をメインに。日頃はVisual Studioを使っていてIDEを使えないとデバッグがまともにできない人間なのでCLionが使えるのはとても有難かった。しかしUS配列のキーボードに慣れていなくて、コーディングしづらいことにここに来て気づいたのはひどかった。US配列しかないことは事前に告知されていたけど、その影響度合いを舐めていた。大反省。

本番

　あまり作戦もなく3人でA問題から見ていって後は流れでという感じ。

　開始してすぐは緊張気味で、A問題の解法がパッとは思い浮かばず、メンバーが思いついたらしいので任せる。しかし微妙に詰まったようで、そこで別のメンバーが「数字以外は大きな定数をかければ単純なソートだけで済む」という実装を提案してくれたので僕が代わって書いてAC。ここでそんなに詰まらなかったのが精神的には良かったかもしれない。

　B問題に行くけどさっぱりわからなくてかなり時間が経つ。チームメンバーはC問題とか他の問題を見たりしていたようだけど僕はずっとB問題にかじりついていた。いろいろ考えていたらvector<map<int, int>>を使って「dp[i][j] =i番目まで見たときに公差jである部分列の最大長」というのが思いついたけど出してもTLE。でが通らないのは厳しいなぁと思いつつ、検証するために手元でのサンプルをランダム生成してジャッジのオプション通りにコンパイルして実行してみたところ10秒はいかないくらいだったので高速化で通せそうだと考えた。しかしcinをscanfにしたりmapをunordered_mapに替えたりしたけどTLEは消えず。ここらへんで2時間以上経過していて1完で終わってしまうのかなぁと冷えかかっていた。

　根本的に間違っていると判断して一から考え直して、(はソート済みとして)頂点から頂点へのコストを持ったエッジを張ってダイクストラ法みたいなことを考えて適当に実装したらなんか行けそうだったので出したら通った。後から冷静に考えるとグラフどうこうは全く意味がなく、小さい公差で最後まで行ったらそれ以上調べないとか、途中でぴったりな数字がなかったら終わりみたいな枝刈りを入れたのが重要だったようだ。計算量が見積もりが下手なので正当な解法なのかどうかが未だにわからない……。

　ほぼ同時にチームメンバーがC問題を通してくれたので3完できて少し安心する。順位表を見たり二人から話を聞いてG問題がいけそうという感じだったのでG問題を見る。ぱっと見で転倒数だったのであるびん君に転倒数のライブラリを写してもらいながら問題を考えていたところ、セグメント木を持って小さい方の数から左右の端の近い方に投げつけていけば解けそうだと思いつく。実装をしていたら同じ数字が複数あったときの処理に少し悩んだが、セグメント木をもう一つ用意して順番を決定するということをやって無理やり通した。これは完全に無駄なことをやっていて普通に1回で良かったんだけど本番中解いていたときは頭がおかしかった。

　Gを通したところで残り40分以下しかなくて、DとかKが簡単そうだということでDを見たけどさっぱり思いつかなかった。残り数分とかになってからは完全に反省会モードへ。目標としていた4完ができて良かった。しかし後から振り返るとACした問題でも提出したコードがひどくて、これは実装力不足と言うべきなのか考察力不足と言うべきなのか。もっと精進したい。

終わりに

　3日目の企業見学なども含めて学びの多い大会だった。年齢制限があるので僕は今回が最初で最後になってしまうけど、後輩の活躍に期待。

AtCoder Regular Contest 101 D - Median of Medians

問題

　長さの数列についてで切り取られる部分列の中央値をとする。全てのについてを並べた数列について中央値を求めよ。

解法

　解説そのまま。

　長さがである数列における中央値は「の中にそれより大きいものが個ある整数の中で最大のもの」である。つまりの中にある数より大きい整数が何個あるか求められれば二分探索できる。

　の中に以上の整数が何個入るか？ という問題を考えるとの各要素について必要な情報は以上であるかどうかだけ。よっての各要素を以上なら、そうでないならと変換した数列を考える。これの累積和を取った数列をとして、である数を求めればよい。これはであり、転倒数はで求まるので間に合う。

反省

　コンテスト終わったすぐ後に解説を見て、中央値は二分探索で求められるんだなーということまでは覚えていたがそこからが思い出せずまた解説を見ることに。この問題の変換はかなり難しいと思う。

　とりあえず作っておいたInversionCountのライブラリを使う機会が来た。マージソート的な実装でやっているんだけど、他の人の提出を見るとBITでやっているほうが多いかもしれない。確かに実行時間1155 msってのはちょっと不安だな。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class InversionCount {
public:
    InversionCount(vector<ll> target) : target_(target) {}
    ll count(ll left = 0, ll right = -1) {
        if (right < 0) {
            //rはtarget_.size()で初期化
            right = target_.size();
        }
        if (right <= left + 1) {
            return 0;
        }
        ll mid = (left + right) / 2;
        ll result = 0;
        //左半分を数える
        result += count(left, mid);

        //右半分を数える
        result += count(mid, right);

        //左右またぐ数を数える
        result += merge(left, mid, right);

        return result;
    }
private:
    ll merge(ll left, ll mid, ll right) {
        vector<ll> l, r;
        for (ll i = left; i < mid; i++) {
            l.push_back(target_[i]);
        }
        for (ll i = mid; i < right; i++) {
            r.push_back(target_[i]);
        }
        //番兵
        l.push_back(LLONG_MAX);
        r.push_back(LLONG_MAX);

        ll left_index = 0;
        ll right_index = 0;
        ll result = 0;
        for (ll i = left; i < right; i++) {
            if (l[left_index] <= r[right_index]) {
                target_[i] = l[left_index];
                left_index++;
            } else {
                target_[i] = r[right_index];
                right_index++;
                result += ((mid - left) - left_index);
            }
        }
        return result;
    }

    vector<ll> target_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }

    auto medianNum = [&](ll x) {
        vector<ll> b(N + 1, 0);
        for (ll i = 0; i < N; i++) {
            b[i + 1] = (a[i] >= x ? 1 : -1) + b[i];
        }
        InversionCount ic(b);
        return N * (N + 1) / 2 - ic.count();
    };

    ll ok = 0, ng = INT_MAX;
    while (ok + 1 != ng) {
        ll mid = (ok + ng) / 2;
        ll num = medianNum(mid);
        (2 * num >= N * (N + 1) / 2 ? ok = mid : ng = mid);
    }
    cout << ok << endl;
}

AtCoder Regular Contest 058 E - 和風いろはちゃん / Iroha and Haiku

問題

　長さがであり、各要素がからまでの整数である数列について、連続する部分列で和がとなるものがこの順で連続しているときを含むとする。を含むものが何通りか求めよ。

解法

　ほぼ解説の通り。

　を含まないものの数を考える。左から一つずつ数列の値を決定していくDPをしていくとき、必要な状態は直前の数列のいくつかである。具体的には和がまでとなるような直前の数列を保持していれば今考えているところの数字を決定できる。

　これは数字を,,, と符号化し、直前の数列とはこれを並べたものとして表現することで状態数を減らすことができる。直前の数列の和は符号化後の数字の長さとなるため、状態数はとなる。あとはこれを個分、各数字がからまで回していくだけなので全体の計算量は

　DPの遷移はたとえば直前の数列を符号化したものがであったとすると

今回の数字	遷移後の数列を符号化したもの
1	s1
2	s10
3	s100
4	s1000

　となるので、今回の数字をとすると結局をだけ左にシフトしたものとをだけ左にシフトしたもののorで書ける。

　「遷移した数列がを含んでいる⇔符号化したものについて個目,個目,個目のビットが立っている」なのであらかじめそのようなビットを立てたものを用意しておくとを含んでいるかの判定も簡単に行える。

反省

　数日前1時間10分ほど考えたが解けなかったので今日はすぐ解説を見たが、それでも1時間近くかかった。

　解いていたときは、の長さを全探索して含まれないところは自由に取れるというので解けるんじゃないかと勘違いしてサンプルが合わずずっと悩んでいた。問題を解いた人の記事を探してみると同じような誤解をしていた人もちらほら見かけるのでちょっと安心するなど。

　解説はぱっと見では何を言っているのかわからないし、実装もどうするのかよくわからなかったけれど、creep04の実装を参考になんとか理解してみるとすごく賢い解法で良い問題に思えた。こういう問題を解けるようになりたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, X, Y, Z;
    cin >> N >> X >> Y >> Z;

    constexpr ll MOD = (ll)1e9 + 7;
    const ll MAX = 1LL << (X + Y + Z - 1);

    //XYZを含む⇔符号化するとX + Y + Z - 1個目, Y + Z - 1個目, Z - 1個目のビットが立っている
    const ll NG_BITS = (1LL << (X + Y + Z - 1)) | (1LL << (Y + Z - 1)) | (1LL << (Z - 1));

    //dp[i][j] := i番目まで見て,直前の数列を符号化したものがjであるときのXYZとなっていない数
    vector<vector<ll>> dp(N + 1, vector<ll>(MAX, 0));
    dp[0][0] = 1;

    for (ll i = 0; i < N; i++) {
        for (ll j = 1; j <= 10; j++) {
            for (ll k = 0; k < MAX; k++) {
                //k:前回までのbit列
                //遷移:kをjだけ左にシフトして、そこに先頭だけ1を立てたものを入れる
                ll t = (k << j) | (1LL << (j - 1));

                //XYZとなっているかの判定
                if ((NG_BITS & t) != NG_BITS) {
                    //上の方は関係ないのでマスクする
                    t &= (MAX - 1);

                    dp[i + 1][t] += dp[i][k];
                    dp[i + 1][t] %= MOD;
                }
            }
        }
    }

    //全ての数からXYZとならない数を引く
    ll ans = 1;
    for (ll i = 0; i < N; i++) {
        ans *= 10;
        ans %= MOD;
    }

    for (ll i = 0; i < MAX; i++) {
        ans += MOD - dp[N][i];
        ans %= MOD;
    }
    cout << ans << endl;
}

AtCoder Regular Contest 057 C - 2乗根

問題

　の上桁がとなるような最小の正整数を求めよ。

解法

　解説そのまま。

　10進法でと表記されるものをとする。の上桁がとなっていることはある整数が存在しと同値。

　でこの条件を満たす正整数が存在する場合、ではより範囲が広がるのでやはり正整数が存在する。またで条件を満たすが存在しないとでも存在しない。よってを大きいほうから考えていき条件が満たされない状況になるまで小さくしていけば良い。

　これを整数の範囲で考えるので下限は切り上げ、上限は切り下げで考えていくと上手く範囲が取れる。

反省

　1時間44分(1WA)でAC。数が大きすぎてまともに扱えないので桁DP的な感じで決定していくのかとか、桁数に対する二分探索とかいろいろ考えたけど結局わからなかった。多倍長整数を使うとできるということを考えもしなかったのがひどいが、他の人の解法を見てもなんでこれで上手く範囲が取れているのかいまいち理解ができない。

　C++でやるなら#include <boost/multiprecision/cpp_int.hpp>としてboost::multiprecision::cpp_int;を使えば良いらしい。環境がないのでPythonで実装をした。

コード

　AtCoderでコードを見るとC++の文法を前提としているからかPythonの切り捨て除算//がコメントアウトっぽく表示されて非常に見にくい。

a = int(input())
b = a + 1

a = a * a
b = b * b - 1

while (a + 99) // 100 <= b // 100:
    a = (a + 99) // 100
    b //= 100
print(a)

AtCoder Regular Contest 056 C - 部門分け

問題

　人の社員をいくつかの部門に分けることを考える。社員との間には信頼度が定まっており、部門分けのスコアはを定数として

　として計算される。スコアの最大値を求めよ。

解法

　を社員の集合に対する問題の答えとする。の部分集合をとして、これが一つの部門であるとすると

　となる(解説を参照のこと)。これはに含まれる社員間の信頼度の総和から、に含まれる社員間の信頼度の総和およびに含まれる社員間の信頼度の総和を引いたものとなる。つまり任意の部分集合について社員間の信頼度の総和をあらかじめで求めておけば、DPの遷移はで行える。

　このDPの計算量はとなるため間に合う。

反省

　1時間59分(2WA)でAC。30分そこそこで部分点解法を書いたあとはあまり考察が進まず。集合に対してDPを考えるというのも典型なんだろう。しっかりできるようになっておきたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> w(N, vector<ll>(N));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            cin >> w[i][j];
        }
    }

    //各部分集合ごとの信頼度の和
    vector<ll> sum(1LL << N, 0);
    for (ll i = 0; i < (1LL << N); i++) {
        vector<ll> members;
        for (ll j = 0; j < N; j++) {
            if (i & (1LL << j)) {
                members.push_back(j);
            }
        }
        for (ll j = 0; j < members.size(); j++) {
            for (ll k = j + 1; k < members.size(); k++) {
                sum[i] += w[members[j]][members[k]];
            }
        }
    }

    //dp[i] := 頂点集合iに対する答え
    vector<ll> dp(1LL << N, 0);
    for (ll i = 1; i < (1LL << N); i++) {
        for (ll j = i; j > 0; j = (j - 1) & i) {
            dp[i] = max(dp[i], dp[i ^ j] + K - (sum[i] - sum[i ^ j] - sum[j]));
        }
    }
    cout << dp[(1LL << N) - 1] << endl;
}

AtCoder Regular Contest 055 C - ABCAC

問題

　文字列が与えられるので、それを空でない文字列を用いて (文字列を連結したもの)と分割する方法が何通りあるかを求めよ。

解法

　と分ける切れ目を全探索する。分けられた前半部分と後半部分で、prefixとsuffixがそれぞれ何文字一致しているかが分かれば、それをとして分割する方法が何通りあるかはで求められる。

　このprefix/suffixが何文字一致しているかはあらかじめもとのに対してZ-algorithmを適用すれば先頭に対する最長共通接頭辞の長さがでわかる。を反転したものに対してもZ-algorithmを適用することで末尾に対する最長共通接尾辞の長さもでわかるため、この問題が解ける。

反省

　2時間10分(1WA)でAC。1時間ほど考えてわからなかったのでとりあえず嘘っぽい部分点解法を出して諦めた。部分点解法は2回目のが出てくる位置、及びの長さをループし、さらに文字列比較でその長さ分だけかかるので、になっているのではないかという気がするが、800msecほどでなんとか部分点は取れだ。

　解説を読むと、最初はKMPとかを使って解くのかと思ったんだけど、書いてあるようにZ-algorithmを使えばスマートらしい。Z-algorithmはよく知らなかったので多少調べて、なんとなく確かに上手くいきそうだなーくらいの理解で他人の実装を写して出した。答えとして調整する部分もいまいち理解が浅くてもう一度出されても苦労しそうな問題に思える。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

//A[i] := SとSのi文字目以降の最長共通接頭辞の長さ
//としたものを返す
//参考:http://snuke.hatenablog.com/entry/2014/12/03/214243
vector<ll> Z_algorithm(string S) {
    vector<ll> A(S.size());
    A[0] = S.size();
    ll i = 1, j = 0;
    while (i < S.size()) {
        while (i + j < S.size() && S[j] == S[i + j]) {
            j++;
        }
        A[i] = j;
        if (j == 0) {
            i++;
            continue;
        }
        ll k = 1;
        while (i + k < S.size() && k + A[k] < j) {
            A[i + k] = A[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return A;
}

int main() {
    string S;
    cin >> S;

    vector<ll> z = Z_algorithm(S);
    reverse(S.begin(), S.end());
    vector<ll> rz = Z_algorithm(S);
    reverse(rz.begin(), rz.end());

    const ll n = S.size();
    ll ans = 0;

    for (ll i = n / 2 + 1; i < n; i++) {
        ll a = min(n - i - 1, z[i]);
        ll c = min(n - i - 1, rz[i - 1]);
        ans += max(min(a + c - (n - i) + 1, n - i - 1), (ll)0);
    }

    cout << ans << endl;
}

AtCoder Regular Contest 054 C - 鯛焼き

問題

　タイヤと木がそれぞれ個あり、各タイヤと木の組について相性が良いか悪いかが決まっている。相性の良いタイヤと木のみを組み合わせて全てのタイヤと木を組み合わせる方法が何通りあるか、その偶奇を求めよ。

解法

　行列式を計算して2で割った余りを求める。詳細は解説なり各種ブログで。

反省

　3時間14分(11WA)でAC。久しぶりに地獄という感じだった。

　考察は1時間で諦めた。完全マッチングの組み合わせ数って数えられるのかなとググってNP困難とか書いてあるのを見つけたくらい。行列として見てどうにかするっていうのも一瞬考えたけど行列式求めるだけで良いっていうのはわからなかった。

　大変だったのは解説を読んでから。行列式が求められない。後でわかったことは、整数行列の行列式の値は整数にはなるが、自分の実装では途中で小数まで考えないといけないはずの計算が発生していたので整数型では答えが合わなくなるということだった。ACしたときは適当にxor取っている他の人の実装パクったら通ったという感じ。

　整数型で計算途中にmodも取らず通している提出もあるので実装の問題なんだろう。自分の提出をdoubleにしても誤差でめちゃくちゃになっているようなので、この計算方法はダメらしい。整数型でmod2における逆元を計算するか、なぜか誤差の出ない上の方法でやるしかないようだ。

　テストケースが非公開なのはやはり地獄。あと数回分くらいの我慢だ……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

//n×n行列の行列式を求める
ll determinant(vector<vector<ll>> M) {
    const ll n = M.size();
    ll result = 1;
    for (ll i = 0; i < n; i++) {
        if (M[i][i] == 0) {
            //対角成分が0だった場合はその列の値が0でない行と交換する
            for (ll ni = i + 1; ni < n; ni++) {
                if (M[ni][i] != 0) {
                    swap(M[i], M[ni]);
                    //result = -result;
                    break;
                }
            }
        }

        if (M[i][i] == 0) {
            return 0;
        }

        for (ll ni = i + 1; ni < n; ni++) {
            //ni行のi列目を全て0にする
            //ll r = M[ni][i] / M[i][i];

            for (ll j = i + 1; j < n; j++) {
                //M[ni][j] -= r * M[i][j];
                M[ni][j] ^= M[ni][i] * M[i][j];
            }
        }

        //行列式は対角成分の積
        result *= M[i][i];
    }
    return result;
}

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> M(N, vector<ll>(N));
    for (ll i = 0; i < N; i++) {
        string S;
        cin >> S;
        for (ll j = 0; j < N; j++) {
            M[i][j] = S[j] - '0';
        }
    }

    cout << (determinant(M) % 2 == 0 ? "Even" : "Odd") << endl;
}