コンピュータ将棋における勾配降下法の最適化アルゴリズム

 自分用メモ

 勾配降下法を用いてパラメータを更新していくときに、どういった更新式を使えばいいのか気になってきたのでいくつかのソフトについて調べてみた。

 ここではニューラルネットワークは除いて、3駒関係や2駒関係の特徴量を使っているソフトに絞って調べた。ボナンザメソッドと自己対局からの学習とでは事情が違う可能性もあるが、とりあえずは気にしないことにした。

 まず更新式の基本についてはここにあることで学んだ。このページの「どのオプティマイザを使うべき?」のところでは、スパースなデータに対しては学習率を適応させていく手法が良いとあって、つまりはAdaGradとかその派生形のことだと思う。3駒関係等の学習はスパースなので、それらの中から選んでいくことになるんだろう。

やねうら王

2017年11月16日時点では

// ----------------------
//        更新式
// ----------------------

// AdaGrad。これが安定しているのでお勧め。
// #define ADA_GRAD_UPDATE

// 勾配の符号だけ見るSGD。省メモリで済むが精度は…。
// #define SGD_UPDATE

// RMSProp風のAdaGrad
// #define ADA_PROP_UPDATE

という記述がある。RMSProp風のAdaGradというのはよくわからないけど、とりあえずいろいろ試されたらしい雰囲気は見て取れる。AdaGradはどんどん更新量が小さくなっていってしまうのが気になるんだけど、それが一番安定しているのか。

技巧

learning.ccによるとRMSPropを使っているみたいだ。

// 学習率の設定(RMSpropの設定)
constexpr float kRmsPropStepRate = 5.0f; // 1回の更新で、最大何点まで各パラメータを動かすか
constexpr float kRmsPropDecay = 0.9975f; // どの程度過去の勾配を重視するか(大きいほど過去の勾配を重視)
constexpr float kRmsPropEpsilon = 1e-4f; // ゼロ除算を防止するために分母に加算される、非常に小さな数

とあるが、kRmsPropStepRateに対するコメントがよくわからない。単なる学習率ではない? 勾配が正規化されているのだろうか(そんなことしていいのか?)

2017/11/20 追記。僕が勘違いしていた。AdaGradやRMSPropの挙動を全然理解していなかった。

また気になるところとしては、勾配の二乗和の指数移動平均を取っていくところで

  // 更新幅の設定(RMSprop)
    a = a * kRmsPropDecay + (g * g);
    const PackedWeight eta = kRmsPropStepRate / (a + kRmsPropEpsilon).apply(std::sqrt);

となっているのだが、RMSProp等の解説でよく見る感じでは  a = a * kRmsPropDecay +  (g * g) * (1 - kRmsPropDecy)
と計算しているのが多い気がする(内分を取っている?)。今回の勾配の二乗に(1 - kRmsPropDecy)をかけるかどうかというのは別に本質的な違いではない(展開してみると結局全体に(1 - kRmsPropDecay)かかるかどうかというだけな気がする)ようにも思えるけど、一番最初の更新でちょうどgが打ち消されるのがわかりやすいので技巧のようにするのが良さそうか。

 いやでも数式的な意味としてはかける方がそれっぽい気がする。最初の一回だけは特別扱いした方が良さそう? 指数移動平均ググる t \ge 3とか書いてある。3なのはちょっとわからないけど、最初は特別視して良さそう(面倒か?)

Apery

learner.hppはあるけどlearner.cppはなくてよくわからない。learner.hppも別に学習用のクラスとかが定義されているわけじゃないし、何か別のファイルにあるのか公開されてないだけかな。

読み太

まだ電王トーナメントのソースは更新されてなくてWCSC27時点のコードだけどSGDとAdaGradが実装されているのは確認できた。読み太はどの程度やねうら王に近いのかがよくわかっていない。

shogi686

SDT5バージョンによるとAdaGradを使っているらしい。

その他

もうコンピュータ将棋からは引退されているけどAkiさんもAdaGradをすすめる記事を書いていた。ここの

線形モデルの学習に限った話。(特に、コンピュータ将棋の評価関数、進行度、実現確率とかでの経験に基づく話。)
非線形モデル(というかNN)の場合は挙動がそれほど素直じゃないので、指数移動平均を使うアルゴリズム(AdamとかRMSPropとか)の方が合っていると思う。

というのが気になる記述で、指数移動平均を使うかどうかっていうのはそこが問題だったのか。

疑問点など

 AdaGradは確かに挙動がわかりやすそうで扱いは楽に思える。しかし更新量がどんどん減少してしまうのがちょっと気になるっちゃ気になるところで、ある程度学習した重みに対して学習をしなおす場合、勾配の二乗和を前のものから取ってくるのと0から始めるのでも大きく結果が変わりそうなのがなんかしっくりこない。

 その点はRMSPropの方がまだいいかなぁという気もするんだけど、技巧しか採用していないというのがなんとも。逆に言えばあの技巧が採用しているんだからまったく合わない方法ではないんだろうけど。

 2駒と3駒の違いとか、自己対戦からの学習かそうでないかの違いなどが影響しているのだろうか。よくわからない。とんでもない高次元空間の関数を最適化しようとしているわけで、常識がどの程度通用するのかもわからない。

まとめ

 AdaGradでいいのでは。

コメントによる指摘(2017/11/19追記)

 darumaさんからAperyのボナメソ及びelmo絞り、nozomi、Squirrelについての情報も提供していただいたので下方のコメントも参照のこと。

CODE FESTIVAL 2017 予選B 参加ログ

結果

 A,B問題2完の741位。うーむC問題が解けないのはちょっと苦しいところか。精進が足りない。レート1535→1516(-19)

A問題

 後ろから8文字を削除するだけ。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string S;
    cin >> S;
    cout << S.substr(0, S.size() - 8) << endl;
}

B問題

 mapで各難易度について必要数と作成済数を記録していけば解けると思ったんだけど、先に必要な数を引いていくとREが出てしまった。mapだからデフォルトは0で、引いたらなにかおかしいことがあるのかな? ちょっとよくわからなかったけど先に足すようにすれば通った。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    vector<int> D(N);
    map<int, int> mp;
    for (int i = 0; i < N; ++i) {
        cin >> D[i];
        mp[D[i]]++;
    }
    int M;
    cin >> M;
    vector<int> T(N);
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
        if (mp[T[i]] == 0) {
            cout << "NO" << endl;
            return 0;
        }
        mp[T[i]]--;
    }
 
    cout << "YES" << endl;
}

C問題

 これが全然わからなかった。考察のとっかかりすらうまくつかめなくて、座っているだけの時間が多くなってしまった。明らかにN, Mが大きいので、まともな最短経路を求めてなんとかしていくわけではないだろうとは思った。そして、頂点の偶奇がちょっと怪しいかと思ってコードを投げてみたりもしたんだけど、片方だけ通すことすらできなかった。

 解説を読んだけど、まず2部グラフという用語の定義すらちゃんとわかってなかった。知識が圧倒的に足りない。

CODE FESTIVAL 2017 予選A 参加記

結果

A,B,C問題を解いて3完。C問題でかなり手間取ってしまったのが痛かった。時間があってもD問題を解けたがどうかはわからないが、しっかり考えてみたかった。

 一応CODE FESTIVALの方にエントリーはしてみているけど、まぁ無理だわな。

A問題

 substrで先頭4文字だけ取ってきて比較するだけ。今考えると4文字未満のときを考慮してなかったのでC++の仕様に救われたか。まぁ親切にも入力例3で3文字のケースがあるので、問題があってもWA出す前に気づけてはいたと思うけど。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string S;
    cin >> S;
    if (S.substr(0, 4) == "YAKI")
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B問題

 2回押すと元に戻るだけだから各ボタンについて押すか押さないかだけが重要。

 行ボタンのうちi個、列ボタンのうちj個を選ぶと  i \times M + (N - i) \times j - i \times j 個が黒くなるはずで、それで解ける。

 コードだと頭が悪くて列を先に押すのと行を先に押すので結果が変わると勘違いしている。何をやっているんだ。普通に二つとも同じ式じゃないか……。というか順番によって結果が変わると思ってしまうのがかなりセンス悪い気がする。頑張ろうな。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            if (i * M + (N - i) * j  - i * j== K
                    || j * N + (M - j) * i - i * j== K) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

C問題

 最初は

  • HとWが両方奇数のとき、奇数個の文字が1個、それ以外の文字は偶数個
  • そうでないとき全部の文字が偶数個

で解けると勘違いしてコードを書き始めてしまったんだけど、入力例2で失敗してちょっと困る。ここで小手先の回避方法として

  • HとWが両方2以上の時は4回以上表れている文字が最低1個は必要

という条件を付け足して、とりあえずサンプルだけ通るようにして提出してしまい、当然WA。

 しばらく考えてから、4個必要になる領域は角だけじゃないことに気づいて、HとWの偶奇によって偶偶 or 奇奇 or 偶奇(奇偶)で場合分けして書き直したが、まだ1個だけWAが出るようになった。

 どうしてもわからなかったのでそれぞれの場合分けに一個ずつassert(false)を仕込んでみたところ、奇奇のところでWAがREになったので、ここで変なことが起きていると判断した。今回はペナルティがなしということだってのでこういう邪悪なハックをやることに対する抵抗がちょっと小さかった。

 で、何が間違っていたかというと、4個以上出てくる文字が奇数になっている場合というのを考慮していなかった。たとえばaが5個出てきて、1個を中央に使って4個を対象的に使うとか、そういうことがありえるんだ。気づいたらすぐ直せてAC。結構大変だった。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0;
    int num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    if (H % 2 == 0 && W % 2 == 0) {
        if (odd_num == 0 && H * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else if (H % 2 == 1 && W % 2 == 1) {
        if (odd_num == 1 && (H - 1) * (W - 1) <= num4 * 4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else {
        //必ずHが奇数ということにする
        if (H % 2 == 0)
            swap(H, W);

        if (odd_num == 0 && (H - 1) * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

 場合分けが美しくないと思ったのでちょっと書き直してみた。まぁ本番でこれを書きにいくことはしないかなぁ。でもこれの方が解法をちゃんと理解した上でのコードっぽい気はする。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0, num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    //4個使う領域(たとえば右上)を求めるときの長さ
    int h = (H % 2 == 0 ? H / 2 : (H - 1) / 2);
    int w = (W % 2 == 0 ? W / 2 : (W - 1) / 2);

    if (odd_num == (H % 2 == 1 && W % 2 == 1)
            && h * w <= num4)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

D問題

 時間もなかったので、単純にRYGBの順で塗れるだけ塗ってみるとか、できるだけバランスよく塗ってみるとか、簡単な方法で貪欲にやっていくのを試してみたけどWA。間違ってるパターンをいろいろ出してみて眺めているうちに時間切れ。

 ある場所に対して同じ色を塗れない位置が角の利きに似ているので一瞬Rotated Bitboardみたいな考え方が頭をよぎったんだど、それを推し進めることができなかった。マンハッタン距離は45度回転させてみるというの、ちょっと気に留めておいていいパターンだと思う。

AtCoder Regular Contest 083 参加記

結果

 C問題とD問題の2完。C問題で4WA出しながら45分以上かかって無茶苦茶焦ったけれど、なんとか落ち着きを取り戻してD問題まで通せたのは良かった。

 Rating:1521→1535(+14)

f:id:tokumini:20170916235105p:plain

C問題

 最初は貪欲法とかでできるのかといろいろ考えていたけど、場合分けが難しすぎて断念。それぞれの入力値がそこまで大きくないので全探索で解けるだろうと判断したが、愚直な全探索ではまともに実行が終わらなかった。値を出力して観察すると、waterやsugarが同じものを何度も訪れているっぽいので訪問フラグを付けてみると高速になってACできた。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

long long A, B, C, D, E, F;
long long ans_water = 0, ans_sugar = 0;

//0で初期化するとwater = 0がそのまま残り1つだけWAとなる
double max_percentage = -1;
bool visit[3001][3001];

void DFS(long long water, long long sugar) {
    //F以下でないとダメ
    if (water + sugar > F)
        return;

    //溶け残ったらダメ
    if (water / 100 * E < sugar)
        return;

    //訪問フラグを確認
    if (visit[water][sugar])
        return;

    //作った砂糖水の濃度
    if (water != 0) { //0除算を避ける
        double tmp = 100.0 * sugar / (100.0 * water + sugar);

        if (tmp > max_percentage) {
            max_percentage = tmp;
            ans_water = water;
            ans_sugar = sugar;
        }
    }
    visit[water][sugar] = true;

    //操作1
    DFS(water + 100 * A, sugar);
    //操作2
    DFS(water + 100 * B, sugar);
    //操作3
    DFS(water, sugar + C);
    //操作4
    DFS(water, sugar + D);
}

int main()
{
    cin >> A >> B >> C >> D >> E >> F;

    DFS(0, 0);

    cout << ans_water + ans_sugar << " " << ans_sugar << endl;
}

D問題

 問題の把握をしてNの大きさからいって3重ループは大丈夫だろうというところでワーシャルフロイド法が思い浮かんだ。

 まず最初に与えられた2次元配列Aの和を保持しておいて、そこから要らないものを削除していけばいいだろうと発想。

 元の2次元配列Aを3重ループで開始点、経由点、終端点と迂回する順と比較していって、より短いものがあったら最短としておかしいので-1を出力して終わり、等しかったら直接行く道は削除できるのでその分を和から引く、という方針でやったところ、半分くらいがACとなったので大まかな方針としてはあっているんじゃないかと思った。

 サンプルは全部通ってしまうので残りのWAを取るためには自分で間違っているケースを考える必要があったが、最初に正方形のように辺が張っている状態を考えて

f:id:tokumini:20170916235922p:plain

4
0 1 1 2
1 0 2 1
1 2 0 1
2 1 1 0
というのを試してみると答えが4になるべきところを0にしていて、まさにこれが残りの間違いだった。これはたとえば1から4へ行くルートは2を経由するのと3を経由するので2パターンあり、その2回の両方で直接ルート分を引いてしまっていたので答えがおかしくなっているということだった。よってあるノードからあるノードへの辺をすでに削除しているかを2次元配列で保持していくことでACとなった。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

bool flag[301][301];

int main()
{
    int N;
    cin >> N;
    vector<vector<long long> > A(N, vector<long long>(N, 0));
    long long sum = 0;
    REP (i, N) {
        REP (j, N) {
            cin >> A[i][j];
            sum += A[i][j];
        }
    }
    //同じ辺を2回カウントしているので2で割る
    sum /= 2;

    REP (i, N) { //経由
        REP (j, N) { //開始
            for (int k = j + 1; k < N; ++k) { //終端
                if (i == j || i == k)
                    continue;
                if (A[j][i] + A[i][k] < A[j][k]) { //より短く行けたらおかしい
                    cout << -1 << endl;
                    return 0;
                }
                if (A[j][i] + A[i][k] == A[j][k]) { //同じコストでいけたら直接辺は削除できる
                    if (flag[j][k] == false) { //直接辺を削除するのは1回だけだからフラグを持つ
                        sum -= A[j][k];
                        flag[j][k] = true;
                    }
                }
            }
        }
    }
    cout << sum << endl;
}

E問題

 問題文を把握したくらいで時間切れ。700点問題とはいえちょっと解ける気はしなかった。

AtCoder Regular Contest 067 反省会

C,D問題を通しての2完で322位でした。 レートは1325から1308へ。完全に停滞している。

すっかり忘れててchokudaiさんのツイートを見てからの参加だったので11分遅れでのスタートでした。

C問題 『Factors of Factorial』

最初約数の個数を求めるのはN!じゃなくてNだと思い込んでしまったのでN \leq 1000だから素数は37まで容易すればいいかな〜と気軽に考えていたけど、サンプル合わないところでやっと気づいた。どうしようか悩んだけど、結局ググッて997までの素数をコピペしてきて凌ぐことに。その際にNが大きい素数になった時のこと考えてans \leq 1ではans = 2にするみたいな意味不明な処理を消し忘れていて1WA出してしまった。

#include <bits/stdc++.h>
using namespace std;
const int MOD = pow(10, 9) + 7;

int m[168] = {0};
int p[] = {2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71, 73 ,79 ,83 ,89 ,97 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173, 179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281, 283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409, 419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541, 547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659, 661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809, 811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941, 947 ,953 ,967 ,971 ,977 ,983 ,991 ,997
};

int main()
{
    int N;
    scanf("%d", &N);
    for (int j = N; j >= 2; j--) {
        N = j;
        for (int i = 0; i < 168; i++) {
            while (N % p[i] == 0) {
                m[i]++;
                N /= p[i];
            }
        }
    }
    long long ans = 1;
    for (int i = 0; i < 168; i++) {
        ans *= m[i] + 1;
        ans %= MOD;
    }
    printf("%lld\n", ans);
}

D問題 『Walk and Teleport』

普通に貪欲やるだけでは? と思って提出したらWA。理由は10^{9}同士の掛け算によるオーバーフローなんだけど、このときには気づかず「一番大きいギャップにあたったら一度一番右までテレポートしなきゃいけないんだ」とかわけのわからない考察を始めてしまい、めちゃくちゃ時間かかってしまった&3WA。変数をとりあえずlong longで取る癖をつけておいた方が(競プロ的には)いいんだろうなぁ。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, A, B;
    vector<int> X;
    scanf("%d%d%d", &N, &A, &B);
    X.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &X[i]);
    }
    long long ans = 0;
    for (int i = 1; i <= N - 1; i++) {
        ans += min((long long)A * (long long)(X[i + 1] - X[i]), (long long)B);
    }
    printf("%lld\n", ans);
}

E問題 『Grouping』

さっぱり方針がわからなかった。配点から見てそんなに難しくはないのかなと思ったけど、逆に典型題みたいな感じだと僕にはわからないと思ってほぼ諦めてしまった。

解説読んだら「DP[i][j] = i人以下のグループのみでj人使っている場合の数」というDPを考えるとのこと。DPで考えるなら最終的なDP[N[N]]などが答えになっているはずで、どういうものか全然思いつかなかったんだけど、なるほどこうするものか。2次元的なDPを解いた量が圧倒的に少なすぎて発想が出てこないな。Nの大きさ制限からなんとなく察し取れたりするものなんだろうか。

F問題 『Yakiniku Restaurants』

おそらく通すことはできないとわかってはいたけど、E問題よりもこっちのほうが考えてるふりができるので問題のページを開いて眺めていた。なにもわからなかった。

AtCoder Beginner Contest 038 反省会

 D問題が解けず300点の258位でした……。まだ解く速さを強く意識しようという段階でもない気はするので、点数を求めるという意味でせめてD問題の部分点は取りたかったですね。

以下各問感想

A問題『お茶』

消費時間 2分くらい  特になし

B問題『ディスプレイ』

消費時間 5分くらい+WA1回  両方のディスプレイを90度回転させたW1==W2の条件を落としていて一回WA出しました。なぜかどちらか1つだけ回すか、両方そのままかの3パターンしか考えていませんでした。残念。

C問題『単調増加』

消費時間 50分くらい+WA1回  そこから何個の単調増加数列が取れるかを後ろからメモしていけばいいんだろうなと考えました。ただちょっと問題なのは、計算量をとくに見積もったわけではなくたぶん大丈夫だろうみたいな感じで方針を立ててしまっているので、ちゃんとこれが{o(n)}になってることとか与えられる{n}の大きさがどうとか考えられるようにならなくてはいけませんね。WA出したのも、ansをlong longで宣言していなかったからで、そういった感覚の鈍さがそのまま現れています。
 解説動画だと尺取り法を使っていて、計算量の考え方がとてもわかりやすかったです。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    int n;
    long long int ans=0;
    scanf("%d",&n);
    vector<int> a(n),m(n);
    REP(i,n){
        scanf("%d",&a[i]);
        m[i]=1;
    }
    for(int i=n-1;i>=1;i--){
        if(a[i]>a[i-1]){
            m[i-1]+=m[i];
        }
        ans+=m[i];
    }
    ans+=m[0];
    printf("%lld\n",ans);
}

D問題『プレゼント』

 ある箱に何個の箱が入るかを上手くメモしていけば解けるんだろうと思いましたが、メモを更新していく順番が間違っているせいか更新の際の対象をうまく取れていないのか、部分点すら取れませんでした。サンプルは通るだけに原因がわかりにくくて直せませんでした。
 構造体のソートの仕方がちゃんとわかっておらず、まだおっかなびっくりで書いているので自在にやりたいことをコードに落とし込めません。というか整数2つの組ならpairとか使うべきなのか。慣れなきゃなぁ。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

struct box{
    int h,w;
    bool operator<( const box& right) const {
        return h == right.h ? w < right.w : h < right.h;
    }
};

int main()
{
    int n;
    scanf("%d",&n);
    vector<box> b(n);
    vector<int> m(n);
    REP(i,n){
        int w,h;
        scanf("%d %d",&w, &h);
        b[i].w = w;
        b[i].h = h;
        m[i]=1;
    }
    sort(b.begin(),b.end());

    for(int i=n-2;i>=0;i--){
        int tmp=0;
        for(int j=0;j<n;j++){
            if(b[j].h>b[i].h && b[j].w>b[i].w){
                tmp=max(tmp,m[j]);
            }
        }
        m[i]+=tmp;
    }

    printf("%d\n",m[0]);
}

AtCoder Regular Contest 054 反省会

A,B問題を通して200点の158位でした。安定の100位台後半です。今回はC問題を通せると30位に入れるような難易度だったようで、現実的に100位以内を目指すにはA,B問題を素早く解けるかどうかという勝負になっていたようです。

以下各問振り返り

A問題『動く歩道

消費時間 9分55秒
 SからDへ時計回りで向かう時間(rightのイメージでransと置いた)と、反時計回りで向かう時間(leftからlans)の小さい方を取ればいいと考えました。SとDの大小関係で場合分けするのは綺麗な解法ではないのかもしれませんが、安全ではある気がします。
 サンプルを通してみたらYよりXが大きい場合を考えていなかったことに気づいたので、慌てて追加したせいでさらに汚い感じになっています。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int l,x,y,s,d;
    float ans,rans,lans;
    scanf("%d %d %d %d %d",&l,&x,&y,&s,&d);
    if(s<=d){
        rans=(float)(d-s)/(x+y);
        lans=(float)(l-d+s)/(y-x);
    }else{
        rans=(float)(l-s+d)/(x+y);
        lans=(float)(s-d)/(y-x);
    }
    if(y<x){
        ans=rans;
    }else{
        ans=min(rans,lans);
    }
    printf("%f\n",ans);
}

B問題『ムーアの法則

消費時間 53分40秒
 最初は紙の上で微分してしまってあっさり求めようとしましたが、指数関数の微分を思い出せず失敗。その流れで探索をしようという発想になったので、自然と微分した値(の正負だけを見た)での2分探索となりました。解説放送では元の関数での3分探索をしていたので、微分のステップで誤差が出るのが怖いことを考えるとそっちのほうが安全なのかもしれません。
 答えるべきなのはf(x)なのに最初xを求めていて「合わないな〜」とずっと悩んでしまいました。さらには最後答えは合っていたのに、悩んだ過程でprintfで確認していた部分をコメントアウトし忘れていて3回WA出してしまいました。これがなければ130位台くらいには入れていたみたいなので残念です。

#include <bits/stdc++.h>
using namespace std;

double p;

double f(double x){
    double ans = x + p/pow(2.0,x/1.5);
    //printf("f(%lf)=%lf\n",x,ans);
    return ans;
}

double d(double x){
    double h = 0.00001;
    double ans = f(x+h)-f(x);
    //printf("d(%lf)=%lf\n",x,ans);
    return ans;
}

double solve(){
    double minus = 0, plus = 99999999999, mid, di;
    for(int i=0; i<100000; i++){
        mid = (minus + plus) / 2;
        di = d(mid);
        if(di>0){
            plus = mid;
        }else if(di<0){
            minus = mid;
        }else{
            return f(mid);
        }
        //printf("i=%d,mid=%lf\n",i,mid);
    }
    return f(mid);
}


int main()
{
    scanf("%lf",&p);
    double ans = solve();
    printf("%.10lf\n",ans);
}

C問題『鯛焼き』

 さらっと見た感じ、全く解法が思い浮かばず、時間も残り20分くらいしかなかったのでD問題の部分点があればそっちを取りに行くほうがいいのではないかと考えてC問題を解ききるのは諦めました。

D問題『バブルソート

 部分点あって一瞬喜んだんですが、50点ということは簡単なやつではなさそうだということで解けないんだろうなという気はしました。そもそも圧縮した数列を戻す操作を理解するのに15分くらいかかって、そこで時間切れになりました。

AtCoder Regular Contest 053 反省会

 A問題とB問題だけ通せて200点の177位でした。今回を除いて直近2回のAtCoder主催コンテストで順位が189、158なので、まぁこれくらいの位置が今の実力なんだろうとわかってきました。まだ10回ちょっとしか参加してないし、根本的に経験が足りてないなぁと思う次第です。

以下各問振り返り

A問題『ドミノ色塗り』

消費時間 2分26秒 何故か最初にansを0で初期化し、別々に足すという無駄な工程を経ています。思考の順番がそのまま現れていますね。

#include <bits/stdc++.h>

int main()
{
    int h,w;
    scanf("%d %d",&h,&w);
    int ans=0;
    ans+=(w-1)*h;
    ans+=(h-1)*w;
    printf("%d\n",ans);
}

B問題『回文分割』

消費時間 24分33秒 回文に分けるときには中央に来る文字(center)とその両側に足していく文字(add)を分けて考えるべきだと気づくまでに結構時間がかかってしまいました。一度WA出してから修正したので、答える部分の場合分けがprintしてreturnだったりansに正答を代入だったりでぐちゃぐちゃになってしまいました。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    string s;
    cin>>s;
    int n=s.size();
    int center=0,add=0;
    int c[26]={0};
    REP(i,n){
        c[s[i]-'a']++;
    }
    REP(i,26){
        if(c[i]%2==0){
            add+=c[i]/2;
        }else{
            center++;
            c[i]--;
            add+=c[i]/2;
        }
    }


    //printf("add=%d center=%d\n",add,center);
    int ans;

    if(add==0){
        printf("1\n");
        return 0;
    }else if(center==0){
        printf("%d\n",n);
        return 0;
    }else{
        if(add/center==0) {
            ans=1;
        }else{
            ans=1+2*(add/center);
        }
    }
    printf("%d\n",ans);
}

C問題『魔法使い高橋君』

消費時間 1時間3分1秒 最初は全探索→簡略化の流れでいくのかなと思っていろいろ考えていたのですが、そもそも全探索もn!とか大変なことになるのではと気づき、二分探索でできないかなと考えました。最大気温がX℃以下であるかどうかをうまく判定できていないのでその時点でどうしようもないですね。
結局、2つの要素を持つ配列を片方の要素について技術的にソートできないのが足を引っ張っています。と、思ったのですが、上手くベクトルに入れていけば良かったのですね。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
int n;
long long int sum=0;
long long temp=0;
vector<int> a, b, c, flag;

long long int ok=1000000000,ng=-99999999999999,mid=0;

bool isOK(int x){
    if(sum>x) return false;
    
    int rest=n;
    int frest=n;
    int div=1;
    while(div){
        REP(i,n){
            if(flag[i]==1){
                continue;
            }else{
                if(c[i]<=0 && a[i]+temp<=x){
                    temp+=c[i];
                    flag[i]=1;
                    rest--;
                }
            }
        }
        if(rest==0) return true;
        div = frest - rest;
        frest = rest;
    }
    return false;
}

long long int solve(int x){
    while(ok-ng>1){
        printf("ok=%lld ng=%lld x=%d\n",ok,ng,x);
        printf("isOK=%d\n",isOK(x));
        if(isOK(x)){
            ok=x;
            mid=(ok+ng)/2;
        }else{
            ng=x;
            mid=(ok+ng)/2;
        }
    }
    return ok;
}

int main()
{
    scanf("%d",&n);
    REP(i,n){
        int ain,bin,cin;
        scanf("%d %d",&ain, &bin);
        a.push_back(ain);
        b.push_back(bin);
        c.push_back(ain-bin);
        sum+=c[i];
        flag.push_back(0);
    }
    printf("sum=%lld\n",sum);
    int ans=solve(mid);
    printf("%d\n",ans);

}

D問題『2つの山札』

問題文すら読んでませんし解説をみる感じだとまだ全然わかりそうにないです……。

AtCoder Beginner Contest 037

 今回は少し簡単だったような気もするのですが、D問題を通せず300点で189位でした。

A問題 饅頭

消費時間 2分6秒
微妙に問題文に惑わされたり。最近はcin、coutを使わないようにしています。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    printf("%d\n",c/min(a,b));
}

B問題 編集

消費時間 5分45秒
愚直にやってしまう。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    vector<int> a(n);
    REP(i,n){
        a[i]=0;
    }
    REP(i,q){
        int l,r,t;
        scanf("%d %d %d",&l,&r,&t);
        for(int j=l-1;j<=r-1;j++){
            a[j]=t;
        }
    }
    REP(i,n){
        printf("%d\n",a[i]);
    }
}

C問題 総和

消費時間 7分34秒
これ絶対なんか工夫しないとダメだと思ったのにとりあえずで2重ループ書いたら通って驚きました。
解説放送見た感じだと、しゃくとり法の簡単なやつとか、うまく足される回数を考えてまとめちゃうという方法があるのですね。
一応最初の方針でダメだったら上で挙げた後者の方法でやろうと思っていましたが、うまく考えられる気はしませんでした。
累積和というのすごい発想に思えるのですが、しゃくとり法が使えそうなときは同時に頭に浮かんでいいものなんでしょうね。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> a(n);
    REP(i,n){
        scanf("%d",&a[i]);
    }

    long long int ans=0;
    REP(i,n-k+1){
        for(int j=i;j<i+k;j++){
            ans+=a[j];
        }
    }
    printf("%lld\n",ans);
}

D問題 経路

消費時間 1時間44分35秒
たぶん答えは合っているんじゃないかと思うんですが、TLEになります。
わざわざクラス定義しているの絶対に無駄だし、各マスごとに周り4マスを見て大きかったらそれをリストに入れておくというのもどう考えても遅いんでしょうが、他になにも浮かびませんでした。 まず再帰関数をまともに書けないのが論外だし、さらには単純に一度調べたものはメモして保持しておくという自然な発想が欲しかったですね。
方向を求める配列を用意して4回ループさせるとかそういう細かいテクニックもできたらよい(けどすぐには難しいかもしれない)。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
const int mod = 1000000000+7;
int h,w;

class p{
    public:
    int x,y;
};

int get(vector<int> a,int x,int y){
    return a[y*(w+2)+x];
}

int main()
{
    scanf("%d %d",&h,&w);
    vector<int> a((h+2)*(w+2));
    REP(i,h+2){
        if(i==0||i==h+1){
            REP(j,w+2){
                a[i*(w+2)+j]=0;
            }
        }else{
            REP(j,w+2){
                if(j==0||j==w+1){
                    a[i*(w+2)+j]=0;
                }else{
                    scanf("%d",&a[i*(w+2)+j]);
                }
            }
        }
    }

    int ans=0;
    REP(i,h){
        REP(j,w){
            ans++;
            vector<p> list;
            p now;
            now.x=j+1; now.y=i+1;
            list.push_back(now);
            while(list.size()!=0){
                int s = list.size()-1;
                int x = list[s].x, y=list[s].y;
                int no = get(a,x,y);
                list.pop_back();
                if(get(a,x-1,y)>no){
                    p to;
                    to.x=x-1; to.y=y;
                    list.push_back(to);
                    ans++;
                }
                if(get(a,x+1,y)>no){
                    p to;
                    to.x=x+1; to.y=y;
                    list.push_back(to);
                    ans++;
                }
                if(get(a,x,y-1)>no){
                    p to;
                    to.x=x; to.y=y-1;
                    list.push_back(to);
                    ans++;
                }
                if(get(a,x,y+1)>no){
                    p to;
                    to.x=x; to.y=y+1;
                    list.push_back(to);
                    ans++;
                }
            }
        }
    }
    printf("%d\n",ans%mod);
}

第26回世界コンピュータ将棋選手権 雑感

今日はほぼ一日中えびふらいさんの放送を見ていました。

  • えびふらいさんのエンタメ化して人集めて計算代行してもらうってすごく面白い手法だしもっと打算的にやっていく人がいてもよさそう(でも狙われると逆に冷めるみたいな要素もあるんでしょうね) 善意で応援してる、協力してる感を演出するとは)
  • Aperyみたいな強力なライブラリが使えるの本当にすごいことだし強さの平均がめちゃ上がる。一方、ライブラリとして使うのと参考にして自分で書くの、開発者の心境としてどこに境目があるのだろうみたいなのが気になった。そういう意味ではQhapaqの澤井さん(澤田さんでしたっけ……?)がやってることが主流になったりならなかったりなのかもしれないなみたいな。
  • 1年あると環境激変するし、シードを多くすると結構力関係ひっくり返ってるとかありそう。でも多くの人に3日戦いぬけというのも厳しい話なのでしょうか(2次からの人も結局会場来てる人が多いみたいだけど)
  • というかやっぱり実力的にはもっと数多く戦わないと意味なさそうだしやはり交流会という感じ強い
  • 技術お披露目会でもあるらしいですね
  • 当たり前の話だけど開発者の皆さんとても優秀ですね。将棋ソフト作ってみたい気持ちもあるけどaperyとかやねうら王miniとかのソースコードをどういうところからなにをとっかかりに読んでいけばいいのかさっぱりわからず
  • そういう意味ではうさぴょんさんのページが一番素人の素人向けに書かれている感あるし、うさぴょんさん自信が2次予選に進めててすごいし、頑張って欲しい(そしてできれば超初心者向けに本を書いてほしい……っていうのは言いすぎですかね)
  • 大合神クジラちゃんのパワーで殴る感じ最高だったし、それを華麗に打ち破った技巧もすごく良い。
  • 僕も技術力ほしいしそれでいろいろ面白いことをしたいなという気持ちが更に強まりました