AtCoderRegularContest095 参加ログ

結果

　C,D,Eの3完で112位。後述するがE問題はほぼ不正のような解き方をしている。高順位となったが実力ではない。

　今回の結果によって青コーダーになれてしまったが、今後も精進を重ねていかなければいきたい。

C問題

　配列Aを違う配列BにコピーしておいてBをソートし、各A[i]に対してB[N / 2]かB[N / 2 - 1]を出力していけばいいだろうというところまで考えてコードを書き始め、条件分岐はサンプルに合うようにした。こういうところを最後まで考え切ってから実装し始めるか、サンプルに頼るかは悩むところ。なんとかWAなく4分50秒でAC。

D問題

　知識として、nに対してコンビネーションが大きくなるのはだいたいn/2個選ぶときであるというのは知っていたが、nに最大のものを選んでいいということに気づくのがちょっと遅れた。それさえわかってしまえば、と思って2分探索で出したがWA。別に10の5乗くらいなら全部舐めてしまえばいいなと気づいて21分41秒でAC。もうちょっとスマートに解いていきたい。

E問題

E: 必要条件がんばって書いて投げたら1ケースだけWAだったので、assertでHを二分探索してREとWAの切り替わりからHを特定して、そのケースだけNOを出力（最悪）

— はむこ (@hamko_intel) 2018年4月14日

　上の人と同じことをした。

　各操作において、行・列についてどの文字が何個含まれるようなものがあるかということは変わらない。よってそれをmapで取っておき、H,Wの偶奇に合わせてペアがうまく作れるか、そして真ん中が回文になるかという条件を考えた。上の通りこれは必要条件にすぎないのでダメだろうと思いつつ提出したらWAが1個だけだった。assertで範囲を絞りつつ、一応はなんで間違っているのかを考えていたが、最終的にはWAのケースを特定できてしまったのでそこだけ"NO"を出力するようにしてAC。6WAで74分17秒。まぁひどい解き方ですね。

　しかし他の人の提出を見ても乱択？ っぽいのとか焼きなましだったりとか、わりと想定とは違う解法がびゅんびゅん飛んでいるように思える。だからといってassert二分探索の罪が軽くなるわけではないが、まぁやっぱり制約が小さいといろいろ起きるのかなとも。

総括

　何はともあれ青コーダーになったのはなったのだ。これからはちゃんと青を安定させられるように頑張っていきたい。

将棋ウォーズで二段になったので採用している序盤作戦について書いてみた

ウォーズ二段になりました✌ pic.twitter.com/cHmysbJoUD

— sako@海底 (@kaitei_shogi) 2018年2月6日

　先日将棋ウォーズで二段になりました。将棋を始めたきっかけは電王戦FINALなので、将棋歴は約3年ということになりますね。ちょうど区切りも良いということで、今回は二段になったタイミングで採用していた序盤作戦についてまとめてみたいと思います。

　局面図もいくらか載せてみますが、手順とかは正確ではないことをご了承ください。

対居飛車

　相居飛車は基本的に横歩取り、角換わりを目指します。相手の変化によっては雁木や、その他力戦という感じになります。

1.角換わり

　角換わりは基本的に先手でも後手でも腰掛銀で４八金２九飛車の形を目指します。もちろん駒組の段階でも仕掛けを考えはしますが、大抵は図のように自陣を組んでから相手の形に応じて考えることになります。

　一番気分として楽なのは相手が５二金、８二飛車の形で４四歩と突いてくれている形(下図)で、これなら４五歩から仕掛けて良いんじゃないかなぁという感じです。形勢としては別に差はないとは思いますが、先攻できるならまぁ不満なしです。

　一番嫌なのは同型(下図)になることで、そうなるともう仕掛けがわからないので先手でも千日手やむなしの姿勢で、多少待機気味に玉を動かしたりして相手に隙ができるのを待つしかなくなります。しかし意外と千日手にはならないもので、こっちがバランス崩したり相手が崩したりしてなんだかんだ決着はつくものです。多分あまり僕の勝率は高くないと思います……。

　相手が早繰銀ならば腰掛けるのを急いで６五歩で相手の銀を追っ払う形(下図)を目指します。しかしこれ棒銀に切り替えられたりしたときにちゃんと受かるのかは自信がありません。

2. 横歩取り

　横歩取りは先手なら勇気流、後手なら斎藤流を目指します。といっても特に研究しているわけではないので、形とか狙い筋だけをちょっと真似している程度ですね。

　当然、勇気流は相手にやられることもあって、その時には飛車をぶつける作戦(下図)をやっています。これはプロで前例があったやつで、初出がどの対局かは知りませんが僕が記憶しているのは去年の羽生-村山戦ですね。一度だけ40手くらいこの前例をなぞりあう展開になったことがあり、その時は僕が先に手順を忘れていて負けにしたので、特に記憶に残っていますね。

　後手では斎藤流(下図)を目指します。斎藤流は神崎蘭子さんの将棋グリモワールを読んで知ったもので、まだちゃんと変化とかを全部覚えているわけではないんですが相手よりは多少知識はあって有利かなぁというくらいです。

　横歩取りの後手を持っていて気になるのはときどき８七歩と受けるのが早い(下図)人がいることですね。これは一応２四飛と回れば先手は歩で謝るしかなくて多少指しやすいと思っているんですが、まぁめちゃくちゃ有利というわけでもありませんか。

3.対雁木

　最近はプロの影響なのか、相手が角道を止めてくる居飛車力戦みたいな形がちょっと増えた気がします。しかしこれは叡王戦本戦の丸山-小林戦のように船囲い+早繰銀というような形にすれば互角以上の形勢で先攻できる(下図)ことが多いので特に不満はないという感じですかね。

　これは銀を２六と４六のどっちにあがるべきなのかなぁとかちょっと迷いますが、うーんまぁよくわかりません。

対振り飛車

　対振り飛車では対抗形が苦手なので相振り飛車を目指すようにしています。特に向飛車に振って相居飛車の左右反転した局面としてとらえていきたいところです。手数の関係で相振りにしにくい先手の時だけはちょっと対抗形も指すように変えつつあるタイミングで二段になりました。

4.対四間飛車

　先手だと3手目に２六歩と突いてしまうのが相振りを目指すうえでネックとなります。特に最近は雁木が増えたこともあって、角と左銀だけ動かされると雁木か四間飛車か判別できないことが多いく、困りどころです。雁木には居飛車を、四間飛車には相振りをやりたいのですが、どちらでも対応できるようにしても下図くらいが限界なので最近は諦めて対抗形をやるようにしています。２五歩まで指してしまうと相振りにはしづらい気がしているのですが、２六歩は許容しているのに一貫性がないかもしれません。

　とりあえず最近の対四間飛車先手番では対抗形、急戦を目指します。穴熊はさっぱり得意ではないので急戦で頑張ります。よくやるのは下図のような形で、飛車角銀桂でなんとか攻めていきたいところですが、やっぱり自玉が薄くて大変なことが多いですね。

　後手だとほぼ相振りにします。これは８四歩の一手を省略できることが多いからです(下図)。しかし雁木に警戒しつつの駒組となるので、厳密には相手に上手くやられると不利な展開になる気がしています。

　具体的には相手に囲いよりも攻めを重視されると嫌で、下の局面は５五銀が見えてても受からないような気がします。しかし個人的な印象としてはそこまでこうやられる頻度は高くなく、四間飛車を指すような人はあまりこういうことはしない性格なのかな……？ とか思います。

5.対三間飛車

　あまり三間飛車には当たらない気がしているんですが、結構やられて嫌な作戦ではあります。大抵は対四間飛車と同じように先手なら対抗形、後手では相振りを目指します。しかし後手で対四間飛車と同じように相振りを目指すと時々いきなり突っかけらて、そこでなんとなく７二飛車とぶつけるのが何度か経験した局面です(下図)。

　別に飛車交換する一手ではないと思いますが、今までのところは交換になることが多い感じですかね。こうなれば互いに飛車を持ち合っての戦いになるのでまぁ対抗形よりは好みの将棋になります。

6.対中飛車

　対中飛車でも相手の態度が早いなら相振り、そうでなかったら対抗形という感じになっています。対抗形になるのは大抵相手の後手ゴキゲン中飛車なので主に超速で対応します。対中飛車の相振りはツノ銀雁木のような形にしていきます(下図)。他のよくわからない相振りよりは隙がない感じに組めることが多く、これはこれで一局になっているという気がします。

7.その他振り飛車

　角交換振り飛車は対抗形にすることが多いのですが苦手な戦型ですね。

　向飛車も逆棒銀の筋をそのまま食らって負けるということを何度かやらかしている気がします。

　この辺のちょっと遭遇頻度が低い振り飛車は苦手で、対抗形の指し方、考え方が根本的に身についていないという気がします。

終わりに

　特に相居飛車ではプロが指す戦型を真似をするというのが僕の好みとなっています。対抗形はよくわからなくて変な相振りに逃げたりしていますが、三段を目指すとしたら対抗形をきちんと見つめ直す機会が必要なのだろうなぁと感じているところです。

　三段になれる気はさっぱりしないのですが、初段になったときも二段になれる気は全くしなかったなぁということを思い出すとそういうものなのかもしれません。

AtCoder Beginner Contest 079 参加ログ

結果

　0WA、56:02で全完の374位だった。C,D問題でしっかり時間かかってしまうのでまだまだ実力不足だ。

A問題

　stringで受けて判定するだけ。まぁしかし2分かかった。

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

int main()
{
    string s;
    cin >> s;
    if (s[1] != s[2]) {
        cout << "No" << endl;
    } else {
        if (s[0] == s[1] || s[2] == s[3]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

B問題

　なんか無駄に再帰を書いて、時間がかかるのでメモ化するという遠回りをした。普通にforループで良かったじゃん……。4分くらいかかった。

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

vector<long long> memo;

long long ans(int n) {
    if (n == 0) {
        return 2;
    }
    if (n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    return memo[n] = ans(n - 1) + ans(n - 2);
}

int main()
{
    int N;
    cin >> N;
    memo.resize(N + 1);
    for (int i = 0; i <= N; i++) {
        memo[i] = -1;
    }
    cout << ans(N) << endl;
}

C問題

　わざわざdfsなる関数を書いて全探索しにいく。8通りくらいならif文全列挙でいいっていうの、気が付かないんだよなぁ。dfs書くのに手間取って13分くらいかかった。

#include <bits/stdc++.h>
using namespace std;
string ans;
int a[4];

void dfs(int pos, string str, int sum) {
    if (pos == 4) {
        if (sum == 7) {
            ans = str;
        }
        return;
    }
    dfs(pos + 1, str + '+', sum + a[pos]);
    dfs(pos + 1, str + '-', sum - a[pos]);
};

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < 4; i++) {
        a[i] = s[i] - '0';
    }
    dfs(1, "", a[0]);

    for (int i = 0; i < 3; ++i) {
        cout << s[i] << ans[i];
    }
    cout << s[3] << "=7" << endl;
}

D問題

　ダイクストラ法っぽくやっていくことしか頭に浮かばなくて、しかし普通とは逆向き？ なのでかなり手こずる。35分以上かかってしまった。Nが小さいからワーシャルフロイドで一瞬なのになぁ。ただアルゴリズムを知っているだけで適切なタイミングで使えていない。もっと修行を積まないと。

　終わった番号を詰めていくvectorのendも使ってないので不要だろうし、ダイクストラ法っぽいものとして見たとしても出来がいいコードではない。最近まともに競技プログラミングやっていなかった分がそのまま表れているという感じ。電王トーナメントも終わったので、ちょっとは頑張っていきたい。

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<int> > c(10, vector<int>(10, 0)), a(H, vector<int>(W, 0));
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> c[i][j];
        }
    }
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            cin >> a[h][w];
        }
    }

    vector<int> min_cost(10, INT_MAX);
    vector<int> start, end;
    min_cost[1] = 0;
    for (int i = 0; i <= 9; i++) {
        if (i != 1) { 
            start.push_back(i);
        }
        min_cost[i] = c[i][1];
    }
    while (end.size() != 9) {
        int min_index = -1, min_value = INT_MAX;
        for (int i : start) {
            if (min_cost[i] < min_value) {
                min_value = min_cost[i];
                min_index = i;
            }
        }

        start.erase(find(start.begin(), start.end(), min_index));
        end.push_back(min_index);
        for (int i : start) {
            min_cost[i] = min(min_cost[i], min_cost[min_index] + c[i][min_index]);
        }
    }

    long long ans = 0;
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            if (a[h][w] == -1) {
                continue;
            }
            ans += min_cost[a[h][w]];
        }
    }
    cout << ans << endl;
}

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

　自分用メモ

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

　ここではニューラルネットワークは除いて、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; // １回の更新で、最大何点まで各パラメータを動かすか
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等の解説でよく見る感じでは
と計算しているのが多い気がする(内分を取っている？)。今回の勾配の二乗に(1 - kRmsPropDecy)をかけるかどうかというのは別に本質的な違いではない(展開してみると結局全体に(1 - kRmsPropDecay)かかるかどうかというだけな気がする)ようにも思えるけど、一番最初の更新でちょうどgが打ち消されるのがわかりやすいので技巧のようにするのが良さそうか。

　いやでも数式的な意味としてはかける方がそれっぽい気がする。最初の一回だけは特別扱いした方が良さそう？ 指数移動平均でググるととか書いてある。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個を選ぶと 個が黒くなるはずで、それで解ける。

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

#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)

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を取るためには自分で間違っているケースを考える必要があったが、最初に正方形のように辺が張っている状態を考えて

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分遅れでのスタートでした。

こんてすとはじまってるよ！！！

— chokudai(高橋 直大) (@chokudai) 2017年1月15日

C問題 『Factors of Factorial』

最初約数の個数を求めるのはじゃなくてだと思い込んでしまったのでだから素数は37まで容易すればいいかな〜と気軽に考えていたけど、サンプル合わないところでやっと気づいた。どうしようか悩んだけど、結局ググッて997までの素数をコピペしてきて凌ぐことに。その際にが大きい素数になった時のこと考えてではにするみたいな意味不明な処理を消し忘れていて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。理由は同士の掛け算によるオーバーフローなんだけど、このときには気づかず「一番大きいギャップにあたったら一度一番右までテレポートしなきゃいけないんだ」とかわけのわからない考察を始めてしまい、めちゃくちゃ時間かかってしまった&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で考えるなら最終的な[N]]などが答えになっているはずで、どういうものか全然思いつかなかったんだけど、なるほどこうするものか。2次元的なDPを解いた量が圧倒的に少なすぎて発想が出てこないな。の大きさ制限からなんとなく察し取れたりするものなんだろうか。

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回 　そこから何個の単調増加数列が取れるかを後ろからメモしていけばいいんだろうなと考えました。ただちょっと問題なのは、計算量をとくに見積もったわけではなくたぶん大丈夫だろうみたいな感じで方針を立ててしまっているので、ちゃんとこれがになってることとか与えられるの大きさがどうとか考えられるようにならなくてはいけませんね。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分くらいかかって、そこで時間切れになりました。