今年読んで面白かった本・漫画等10作

 再読したものも含めているけどとりあえず10作品(シリーズ)を列挙。根本的に読んだ量が少ないので選ぶのに苦労した……。

 対談系の新書。どちらかというと仏教の話が面白かったか。大乗仏教に対するなんとなく抱いていた違和感が上手く説明されていたと思うし、原始の仏教観に対する納得度も高い。読んだのが2018年頭なので正直もうあまり覚えていないところも多いが、なんだかんだ知に対して誠実にやっていきましょうみたいな内容だった気がする。やっていきたいですね。

月に吠えらんねえ(1) (アフタヌーンKC)

月に吠えらんねえ(1) (アフタヌーンKC)

 萩原朔太郎とか北原白秋とか実在した人物をキャラクター化した感じの漫画。自分が文豪に詳しくないというのもあるし、この手の作品はいまいち好きになれなくて食わず嫌いしていたけれど、これは文句なく面白かった。精神が衰弱している様子の描写が素晴らしい。縊死体が本当になんの意味も持たないものなら異常なホラー的で良いと思ったけど、話が進んでいくにつれて多少そこは(部分的にだが)解明されるところもある。それはそれでまた重要なテーマとなっているため面白いことは面白いけど、理屈ぬきにおかしな世界でも僕は好きだったな。

 ミステリです。誰が何と言おうとミステリ漫画です。城平京フリークとして今年もスパイラルとか雨の日も神様と相撲をとかいろいろ読んではいるんだけど、あえて一つ挙げるならこれかなという感じ。漫画版にはあまり城平京自信ががっつり関わっているわけではないらしく、細かいキャラクターの動かし方とかが城平っぽくなくて新鮮。特に男側のキャラがうじうじなよなよした感じがあまりしないのは珍しい気がする。まぁでもやっぱり漫画にしてそこまで見栄えが良くなるというタイプの作品でもないとは思うし、小説版の方まだ読んでないんですが今すぐ読みます。

物語論 基礎と応用 (講談社選書メチエ)

物語論 基礎と応用 (講談社選書メチエ)

 物語に関する基礎的な用語とかの解説本。今まで物語の構造とかについて全然知らないまま作品に触れていたんだなぁということが思い知らされる。別にこういう知識が無いといけないということはないと思うけれど、見え方が一歩深まってさらに楽しめる可能性はあると思う。

 先崎学九段の闘病記。プロ棋士が7手詰めを解けないという事実は重い。何度か見聞きすることではあったものの、うつ病というのはなんというか本当に身体の怪我とかに近いものなのだなぁと改めて感じる。プロスポーツ選手だって骨折すれば良いパフォーマンスは発揮できないということと同じようなことなのだろう。頭の問題となると見えにくくてわかりにくいところはどうしてもあるのだろうが。

 上手く休むことができれば(ブランク等の分はあるにしても)ある程度は元のレベルまで戻るという点もやはり怪我と近い認識で良いのかなと思っている。復帰してからも苦戦している印象ではあるけれど、先崎九段、応援しています。

人間とは何か (岩波文庫)

人間とは何か (岩波文庫)

 哲学系。古い本だし特段目新しいことを言っているというわけでもないとは思うけど、だいたい個人という概念だとか、自由意志というものだとかに対して感じている印象が上手く表現されているように思う。この辺の話をする前には前提を合わせるためにとりあえず読んでもらいたい、そんな一冊。

 青春系。爽やかに生徒会ものやっていくのかと思ったら途中からめちゃくちゃ甘い恋愛話が始まったりもする。4,5巻とかの破壊力がすごかった。2年生組が好きなんですね。

 普段あまりこういう現実性の高い青春ものってあまり好きになれないことが多いんだけど、この作品は珍しくもう何度も読み返すものになっている。相田裕GUNSLINGER GIRLも面白かったし、パワーのある漫画家だと思います。

 面白かったかというと僕には合わなかったというのが正直なところだけど、しかし迸るエネルギーのようなものは感じる。ただ厚いからでは? とかそういうこと言わない。

 あとがきが一番すっきりしたかもしれない。根幹となる理念というのがはっきりあってその結果生まれたものなんだろう。十分に味わうためにはジョーカーとかも読んだ方が良いらしいが、うーん、そこまでするかどうか。

いなくなれ、群青 (新潮文庫nex)

いなくなれ、群青 (新潮文庫nex)

 自分が大事にしている信念があって、それを体現するものがいたらきっと美しいままでいて欲しいと思うだろう。美しいものへの憧憬を守るためになんとか意地張って頑張るものが、しかし最後にひっくり返されるのって素晴らしい展開だと思う。続きもあるけど今のところは最初のこの巻が一番いいかな。

 今年はサクラダリセットも読み返して河野裕の良さを再確認した。キャラの作りとか意地の張り方とか解決の仕方とか、どこか城平京に似たところがありませんか? ちゃんと考えているわけじゃないけどこういうところで何かしら分類ができたら良いな。

異セカイ系 (講談社タイガ)

異セカイ系 (講談社タイガ)

 小説なのか批評なのかすら知らないまま手に取った本。これも大変面白かった。タイトルだけ見てちょっとでも惹かれるものがあるなら以下を読まずにさっさと読んだ方がいいかもしれない。

 セカイ系の趣が強い作品ではあると思う。肥大した自意識と循環する愛。そういうのを作品の仕掛けを使って華やかに見せてくれる作品が僕は好きだ。しかし最後の方、僕は蛇足と感じた数ページが、セカイ系からは一歩踏み超える部分だったりするんだろうか。語りの対象に他人が混じり始め、セカイから世界への転生が見えてしまう、そこに寂しさを感じないことはない。

あとがき

 こうして振り返ってみてもやはり小説を全然読めていない年だった。特に読んだことのない作品にあまり手が伸びなくて、過去に読んで面白かったものばかりをもう一度読むことの方が多い。自分の好きなジャンルがよくわからないというのも発掘が難しい理由の一つではあると思うんだけど、ミステリ~セカイ系あたりを多少合わない作品と出会うことも許容していろいろ読んでいくしかなさそう。来年は作品に触れることについてお金や時間を惜しまない一年にしたい。

Windows10でPyTorchのC++API exampleを動かしたかった話

 PyTorchのC++APIについてexample-app.cppとmnist.cppをコンパイルして動かすところまでできたが、学習がバグっておりダメそうだったという話。

直ったそうです→リンク

導入まで

 導入方法は基本的にVisual StudioのCMakeパッケージを入れてそれでコンパイルするというだけ。環境はWindows10、Visual Studio2017、CUDA9.0、cuDNN7.0.5。

 まずLibTorchをここから落としてくる。環境を設定するとリンクが表示される。

f:id:tokumini:20181226143631p:plain

 Visual StudioにCMakeツールを入れる。もとから入っていたのでこれだけでいいのか少し自信はない。

f:id:tokumini:20181226143839p:plain

 まずはTensorの表示をするだけのexample-app.cppから。適当なフォルダを作ってVisual Studioから開いてCMakeLists.txtとexample-app.cppを書く。ソリューションを作ってしまうと何をどうコンパイルしているのかよくわからなくなってしまったのでVisual Studioの「フォルダを開く」でやってしまうのが個人的にはわかりやすいと思う。

 ライブラリについて、公式のページではコンパイル時の引数で

cmake -DCMAKE_PREFIX_PATH=/absolute/path/to/libtorch

 ということをしていたが面倒だったので直接環境変数をいじってパスを通した。

f:id:tokumini:20181226151153p:plain

 たくさん警告が出るしエラーも1と表示されているんだけど動くことは動く。ちゃんとブレークポイントも認識している。

 実行ファイル自体が作られるのはコードが置かれているフォルダの中ではなく、ユーザーフォルダの下にCMakeBuildsというフォルダができていてそこの中にある。フォルダ名はCMakeのオプションをいじることで変更できるらしい。

 次はmnistの方。データのダウンロードにPythonを使っているので環境が必要だと思う。特にやることは変わらずフォルダを作ってコードを書いてコンパイルという流れだけど、こっちはDebugモードだとregister_moduleをやろうとしたところでエラーが出る。既知のバグで、報告はされているそうなのでいずれ直るのか。とりあえずReleaseモードでビルドすると普通に動く。

 f:id:tokumini:20181226145443p:plain

 ちゃんと学習中にGPUがたくさん使われているので問題なさそう。

 Debugモードを使えないのは少し厳しいかもしれないが、とりあえずWindowsでもReleaseモードで動くことは確認できたので、開発自体はLinuxでやってもいいしなんとでもなりそう。

問題

 と思っていたんだけどここで重大なことに気づく。学習が進んでも損失とか正答率が全然改善されていない。

f:id:tokumini:20181226181852p:plain

 損失のグラフがとんでもないことになっている。nanになることもあった。検索してみたら2日前にGitHubissueが立てられていた。このissueで気になるところは

  • OSがLinuxWindows特有の問題ではないのか
  • nanになる直前でaccuracyが97~98%になったとある。手元ではaccuracyも全然だったので実は違う問題?
    ここは少しよくわかってなくて、testの方でもデータサイズの分母が60000と書かれているんだけどMNISTのテストデータは10000データではなかったか。コードが何をしているのか読み取れていないので間違っているのか判断ができない。損失が爆発したあとの正解が1135枚でおおよそ10000の1/10なのでなんとなくテストデータは10000枚っぽい気がするが……。そう考えると同じ現象が起こっている。
  • CUDAを使わなくても同じことが発生したらしい。
  • そもそもcuDNNが使われていない、遅い?

 c++ SGD and python SGD don't matchという別のissueもあり、まだ発展途上のAPIなのかなぁと。

AtCoder Grand Contest 029 C - Lexicographic constraints

問題

 N(\le 2 \times 10^5)個の未知の文字列S_1, \dots, S_Nについて、これらが辞書順に並んでおりS_iの長さはA_iであるとわかっているとき、文字列に含まれる文字の種類数として最小の値を求めよ。

解法

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

  • A_{i - 1} \lt A_iのとき
    0で埋めていく。

  • A_{i - 1} \ge A_iのとき
    A_{i} + 1以降の文字を消してA_{i}番目の文字を一つ大きい文字にして必要なら以降上の桁へ繰り上げていく。

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

反省

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

 実装面については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 参加記

結果

f:id:tokumini:20181210194521p:plain

本番まで

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

f:id:tokumini:20181211225029p:plain

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

本番

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

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

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

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

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

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

終わりに

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

AtCoder Regular Contest 101 D - Median of Medians

問題

 長さNの数列aについて(l, r)(1 \le l \le r \le N)で切り取られる部分列a_l, a_{l + 1}, \dots, a_rの中央値をm_{l,r}とする。全ての(l,r)についてm_{l,r}を並べた数列mについて中央値を求めよ。

解法

 解説そのまま。

 長さがMである数列bにおける中央値は「bの中にそれより大きいものが\left\lceil \frac{M}{2} \right\rceil個ある整数の中で最大のもの」である。つまりbの中にある数xより大きい整数が何個あるか求められれば二分探索できる。

 mの中にx以上の整数が何個入るか? という問題を考えるとaの各要素について必要な情報はx以上であるかどうかだけ。よってaの各要素をx以上なら1、そうでないなら-1と変換した数列bを考える。これの累積和を取った数列をSとして、S_{l} \le S_{r}である数を求めればよい。これは2(\frac{N(N + 1)}{2}  - (転倒数))であり、転倒数はO(N\log{N})で求まるので間に合う。

反省

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

 とりあえず作っておいた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

問題

 長さがNであり、各要素が1から10までの整数である数列a_0, a_1, \dots, a_{N - 1}について、連続する部分列で和がX, Y, Zとなるものがこの順で連続しているときXYZを含むとする。XYZを含むものが何通りか求めよ。

解法

 ほぼ解説の通り。

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

 これは数字を1 \to "1",2\to "10",3 \to "100", 4 \to "1000"と符号化し、直前の数列とはこれを並べたものとして表現することで状態数を減らすことができる。直前の数列の和は符号化後の数字の長さとなるため、状態数はO(2^{X + Y + Z})となる。あとはこれをN個分、各数字が1から10まで回していくだけなので全体の計算量はO(10N2^{X + Y + Z})

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

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

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

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

反省

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

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

 解説はぱっと見では何を言っているのかわからないし、実装もどうするのかよくわからなかったけれど、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乗根

問題

 \sqrt{N}の上k桁がa_1 a_2 \dots a_kとなるような最小の正整数Nを求めよ。

解法

 解説そのまま。

 10進法でa_1 a_2 \dots a_kと表記されるものをAとする。\sqrt{N}の上k桁がAとなっていることはある整数tが存在しA^2 \times 10^{2t} \le N \lt (A + 1)^2 \times 10^{2t}と同値。

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

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

反省

 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 - 部門分け

問題

 N人の社員をいくつかの部門に分けることを考える。社員ijの間には信頼度w_{i,j}が定まっており、部門分けのスコアはKを定数として \displaystyle (部門の数)\times K - (異なる部門に属する2人の間の信頼度の総和)

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

解法

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

 {\displaystyle dp[S] = dp[S - T] + K + (S-TとTの間の信頼度の総和)}

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

 このDPの計算量はO(3^n)となるため間に合う。

反省

 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

問題

 文字列S(|S| \le 2 \times 10^5)が与えられるので、それを空でない文字列A, B, Cを用いてABCAC (文字列を連結したもの)と分割する方法が何通りあるかを求めよ。

解法

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

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

反省

 2時間10分(1WA)でAC。1時間ほど考えてわからなかったのでとりあえず嘘っぽい部分点解法を出して諦めた。部分点解法は2回目のAが出てくる位置、及びAの長さをループし、さらに文字列比較でその長さ分だけかかるので、O(|S|^3)になっているのではないかという気がするが、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 - 鯛焼き

問題

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

解法

 行列式を計算して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;
}