AtCoder ABC136の振り返り

ABC136に参加したので，復習がてら振り返ります．

A問題

普通にをしました．負になる場合だけ気をつけました．こういう簡単な時にさらっと三項演算子使えるようになりたいです．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int A, B, C; cin >> A >> B >> C;

    if (A - B > C) cout << 0 << endl;
    else cout << C - A + B << endl;

    return 0;
}

B問題

一度文字列になおせばsize()の判定でいけるじゃん！と思いましたが，C++で数字から文字列に直す方法を知らなかったので（調べればよかったですが），数字のまま処理しました．1から10倍していって，奇数回目の分だけ数えました．

文字列に直す場合，to_string()なる便利なものがあるみたいです．常識かもしれませんが．．．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <sstream>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;

    int cnt = 0, i = 1, j = 1;
    bool flag = true;

    while (1) {
        i *= 10;
        if (i <= N) {
            if (flag) cnt += i - j;
        } else {
            if (flag) {
                cnt += N - j + 1;
            }
            break;
        }
        j = i;
        flag = !flag;
    }

    cout << cnt << endl;
}

C問題

最初は，のときにから１をひく方針でいきましたが，それだと1332とかが無理になるので，少し悩みました．

最初からみていく場合，１引ける場合は引いておいて損はない（引く操作が最適？？）ので，その方針でいけました．回答は後ろからみていってました．確かに後ろからだと1332みたいな状況でもいけますね．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

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

    a[0] -= 1;
    for (int i = 1; i < N - 1; i++) {
        if (a[i] - a[i+1] > 1 || (a[i] - a[i+1] == 1 && a[i] - a[i-1] <= 0)) {
            cout << "No" << endl;
            return 0;
        } else if (a[i] - a[i+1] <= 1 && a[i] - a[i-1] > 0){
            a[i] -= 1;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

D問題

今回は本番中に初めてD問題が解けました！といっても時間ギリギリですが．．．

子供の人数に比べて移動回数が十分に大きいので，RLのようにRとLが切り替わるところに左右の子供がたまっていくことはすぐにわかりました．切り替わりの位置との相対距離の偶奇によってRLのどっちにいるのか判断できることも割とさくっと気づきました．が，実装力が足りず，実装にとても時間がかかりました．

RからLに切り替わる位置を覚えておいて，前から順番に子供のいる位置を決めていきましたが，もっといい実装の仕方があると思います．解説のように(R, 3), (L, 5)...みたいに保持するやり方を試しに実装したいですが，時間がある時&気が向いたらやりたいです．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

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

    vector<int> ans(int(s.size()));

    vector<int> ch;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == 'L' && s[i-1] == 'R') ch.push_back(i);
    }

    int tmp = 0, i = 0;
    while (i != ch.size()) {
        while (tmp != s.size()) {
            if (s[tmp] == 'R' && tmp < ch[i]) {
                if ((ch[i] - tmp) % 2 == 0) ans[ch[i]]++;
                else ans[ch[i]-1]++;
            } else if (s[tmp] == 'L' && tmp >= ch[i]){
                if ((tmp - ch[i]) % 2 == 0) ans[ch[i]]++;
                else ans[ch[i]-1]++;
            } else {
                i++;
                break;
            }
            tmp++;
        }
        if (tmp == int(s.size())) break;
    }


    for (int i = 0; i < s.size(); i++) {
        cout << ans[i];
        if (i != int(s.size())-1) cout << " ";
    }
    cout << endl;
    return 0;
}

AtCoder Educational DP Contest：O問題（bit DP）

DPコンテストのO問題に引っかかったので，まとめます．

方針

男女N人ずつのマッチングですが、例えば男性iを昇順に固定した場合、女性N人の順列を試せば全通り考えられます。しかし，O(N!)の時間がかかり間に合わないです。一般に，順列などO(N!)をO(2^N)に落とすテクニックとしてbit DPなるものがあるようなのでそれを使っていきます。

bit DP

N個の要素の順列で条件に合うものを数え上げたりするときに、順列全ての情報を保持する必要がなく，どの要素をつかっているかを保持したので十分だという場合に使えるみたいです。どの要素を使っているかは，N個の要素の部分集合として表せ，bit列を用いることで割と簡単に表現できます。

考え方

例えば，３人の男女のマッチングで３組のペアが何通りできるかを考えます。このとき，どの女性がマッチングに参加しているかをbit列で101のように表現することにします。男は昇順に固定されていることを考えると，この例でいえば女１と女３と，男１，男２のマッチングを考えることになります。また，bit列で表される女M人がマッチングに参加した場合に，M組みのペアがdp[bit]通り考えられるとします．

３人全員がマッチングに参加するとき，bit列は111になります．漸化式を立てたいので、ペアを１組固定することで２人でのマッチングとの関係を考えます。ペアを１つ固定する上で，男は昇順に固定されているので当然男３になりますが、女は３人のうち１人を選ぶことになります。

仮に女１が選ぶとしましょう。このとき女１以外の参加者のbit列は011になります。男３と女１が実際にペアになれるとき、女１を除いた２人のマッチングにこのペアを追加するだけで３人のマッチングが完成することから，男３と女１がペアになる３人のマッチングはdp[011]通りあることになります（女２と女３での２組のマッチングが全くない場合は男３と女１がペアになっても０通りですが，dp[011]=0が成り立っているので問題ないです）。

女１が選ばれたのに男３と女１がペアになれない場合、女２と女３がペアになれたところで３人のマッチングは不可能なので０通りです。

これらをマッチングに参加している女性すべてでやっていくと，以下の漸化式が立てられます。このとき男iと女jがペアになれるとき１，なれないとき０になる関数としてを定義します。

これを一般化すると，bit列において１の数をi個としたとき（参加している女・男の人数はbit列の１の数に対応），参加しているすべての女と男iについて上記のことをやっていけばよいわけです。

この漸化式を使って動的計画法で実装します。bitは１０進数でまで１ずつ足していけばすべてのbit列を網羅できます。

このとき、

• 1 << i：右からi+1番目の桁だけ１をたてる
• bit xor (1 << i)：bitのi+1番目の桁を反転させる

ということに注意すると

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

#define MOD 1000000007LL

ll dp[1<<25];
int a[21][21];

int main() {
  int N; cin >> N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> a[i][j];
    }
  }
  dp[0] = 1;
  for (int bit = 0; bit < (1<<N); bit++) {
    int pos = __builtin_popcount(bit) - 1;
    
    for (int i = 0; i < N; i++) {
      if ((bit & (1<<i)) && a[pos][i]) {
        dp[bit] += dp[bit ^ (1<<i)];
        dp[bit] %= MOD;
      }
    }
  }
  cout << dp[(1<<N) - 1] << endl;
  return 0;
}

みたいになります。

まとめ

見返してて、自己満な解説になってしまった感がありますが、とりあえずこれでいいや．．．同じようなレベルの人の少しでも参考になれば嬉しいです。

巡回セールスマン問題とかいろいろな場面でbit DPが使えるみたいです。

AtCoder Educational DP Contest：J問題

AtCoderをやっていて、Educational DP ContestのJ問題に詰まったので復習がてら自分なりにまとめて見ます。数学的に厳密なものではないのでご了承ください。

文字の定義

• ：１個の寿司が乗っている皿がi個、２個の寿司が乗っている皿がj個、３個の寿司が乗っている皿がk個ある状態
• ：(i, j, k)の状態からすべて食べる場合の試行回数の期待値
• ：皿の数
• ：寿司が乗っている皿の数

めんどうなので，ある状態からすべて寿司を食べるまでに必要な試行回数の期待値のことを、ある状態の期待値と表現します。

考え方

寿司を１個食べるための試行回数の期待値を使って帰納的にときます。
状態(i, j, k)を考えると、

という漸化式が成り立ちます。これを元に、右辺をそれぞれ求めれば動的計画法で解けそうです。

右辺第１項の計算

(i, j, k)からの遷移先には(i-1, j, k), (i+1, j-1, k), (i, j+1, k-1)の３つがあります。食べる皿は等確率で選ぶので、(i, j, k)の遷移先のうち、それぞれの状態である確率はとなります。よって(i, j, k)から１個寿司を食べていける状態の期待値は

となります。

右辺第２項の計算

となります。（１個の寿司を食べるためにn回かかるということは、n-1回はすべて寿司が乗っていない皿を選び続けなければならない）

一般にqが１未満の時、が成り立つので、(i, j, k)から１個寿司を食べるための試行回数の期待値はとなります。これが漸化式の右辺第二項になります。

漸化式

以上を踏まえると漸化式は

となります。あとはこれを使って動的計画法で解けると思います。私はメモ化再帰で書きました。直感的にメモ化再帰がわかりやすいものと、ループ回す方がわかりやすいものがありませんか．．．？この問題はループ回すやり方の直感的なイメージが湧かなかったのでメモ化再帰をつかいました。

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

#define INF 1000000009LL

double dp[305][305][305];//dp[i][j][k]:１個の寿司がi個，２個の寿司がj個，３個の寿司がk個あるときすべて食べ終わるまでの試行回数の期待値
int N;

double dfs(int i, int j, int k) {
    if (dp[i][j][k] > -1) return dp[i][j][k];

    double res = 1.0 * N / (i + j + k);
    if (i > 0) res += 1.0 * i / (i + j + k) * dfs(i-1, j, k);
    if (j > 0) res += 1.0 * j / (i + j + k) * dfs(i+1, j-1, k);
    if (k > 0) res += 1.0 * k / (i + j + k) * dfs(i, j+1, k-1);

    return dp[i][j][k] = res;
}

int main() {
    cin >> N;
    int one = 0, two = 0, three = 0;
    for (int i = 0; i < N; i++) {
        int a; cin >> a;
        if (a == 1) one++;
        else if (a == 2) two++;
        else three++;
    }

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            for (int k = 0; k <= N; k++) {
                dp[i][j][k] = -1;
            }
        }
    }

    dp[0][0][0] = 0;
    cout << fixed;
    cout << setprecision(10) << dfs(one, two, three) << endl;

    return 0;
}

まとめ

Educational DP Contestをアルファベット順に解いていますが、J問題で大きくつまずきました。中級者以上の方はこの問題はさくっと解けてしまうんでしょうか．．．地道に典型的な問題や考え方を身につけていきたいです。

AtCoder ABC135の振り返り

復習のためにABC135の振り返りをしたいと思います。

A問題

方針、感想

AとBのちょうど真ん中にすればよいことは直感的にわかったので、偶奇で場合分けしてさくっといきました。

#include <iostream>

using namespace std;
typedef long long ll;

int main() {
    int a, b; cin >> a >> b;
    if ((a + b) % 2 == 0) {
        cout << (a + b) / 2 << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

B問題

方針、感想

Nがかなり小さかったので、全通り愚直に調べました。入れ替えた配列について、新しい配列を用意するのかとかうまいやり方がわからなくて、かなり汚い書き方になってしまいました．．．全通り調べて、昇順の確認でO(N^3)かかる？？ので、入れ替えのたびに配列をコピーするとO(N^4)になる？？とか色々考えた結果こうなりました。解答は、配列の（インデックス+1）と中身が違うものの個数を調べるやり方でした。たしかにそうですね．．．こういう基本的な問題はもっとさくっと行きたいです。

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

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

    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            for (int k = 0; k < N-1; k++) {
                int tmp = k;
                int tmp1 = k + 1;
                if (tmp == i) {
                    tmp = j;
                } else if (tmp == j) {
                    tmp = i;
                }

                if (tmp1 == i) tmp1 = j;
                else if (tmp1 == j) tmp1 = i;

                if (v[tmp] > v[tmp1]) break;
                if (k == N - 2) {
                    cout << "YES" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}

C問題

方針、解答

１番目の街の怪獣は１番目の勇者しか倒せないことは割とすぐわかったので、そのまま芋づる式に決まっていくのかなと思って実装しました。厳密な証明はわからなかったのですが、まぁそうだろうということで提出したらACでした。

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

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

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (a[i] > b[i]) ans += b[i];
        else {
            ans += a[i];
            if (b[i] - a[i] > a[i+1]) {
                ans += a[i+1];
                a[i+1] = 0;
            } else {
                ans += b[i] - a[i];
                a[i+1] = a[i+1] - (b[i] - a[i]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

D問題

方針、感想

解けませんでした．．．最小の場合と最大の場合の間でーとか最初に思いましたが、間に固定されてる数字があるし、そもそも桁が大きすぎてlong longにも入らない？？し諦めました。

そのあと、各桁ごとにmodを計算できることに気づいて、あら？これは動的計画法を使うのかな？？と思った時には残り１０分くらいになってました。まぁもう少し早く気づいてもダメだったと思いますが．．．以下、解説を見てからの振り返りです。

１桁ずつ見ていったとき、それ以前の桁までのmod13の値がわかればよいので、dp[100005][13]でループ回してボトムアップに埋めていけば良いのかな．．．とかいう方針で考えていったらいいんですかね？？

桁を上から見ていくか、下から見ていくかでmod 13の計算方法が違って
１の位から見ていく場合、例えば12345を考えると、

ここで300とかのmod 13は
とかに分解できるので、桁をずらすごとに100とか1000とかのmod 13を用意しておくと計算できそうです。

一番上の位から見ていく場合は

みたいな感じで分解してmod 13をとると、今の桁の10倍と次の桁を足してmod 13をとっていくと、最終的に全体のmod 13が計算できることがわかります。

書いて見たコードは後者のほうです。

#include <iostream>
#include <string>

#define MOD 1000000007LL

using namespace std;
typedef long long ll;

ll dp[100005][13];
int main() {
    string s; cin >> s;

    dp[0][0] = 1;
    for (int i = 0; i < s.size(); i++) {
        int c;
        if (s[i] != '?') c = s[i] - '0';
        else c = -1;
        for (int k = 0; k < 13; k++) {
            for (int j = 0; j < 10; j++) {
                if (c != -1 && c != j) continue;
                dp[i+1][(k * 10 + j) % 13] += dp[i][k];
                dp[i+1][(k * 10 + j) % 13] %= MOD;
            }
        }
    }

    cout << dp[int(s.size())][5] << endl;
    return 0;
}

まとめ

まだまだD問題も解けないので、とりあえずD問題までを固めたいです。DPなどの典型的な問題は確実に解けるようにしたい．．．

2019年NAIST受験記（情報科学専攻）

本日NAISTの合格発表があり、無事合格しておりましたので受験のまとめを書いていきたいと思います。すでにM1で秋入学という少し特殊な状況ではありますが、基本的な流れは同じなのでお役に立てれば幸いです。なお2019年度の秋入学入試ですので、募集要項・配点・Q&Aなどは公式ページなどで最新の情報を参照してください。

受験の経緯

私はすでに１年前に自大学の大学院の院試を受験しており、入学も決まっていました。それなのにどうして今頃NAISTを受験したのかと言うと、D進するなら早くからやりたい研究をしたいと思ったからです。詳しい経緯は割愛します。

概要

NAISTの入試は以下の採点要素があります。

• 小論文
• TOEIC、TOEFLなどの成績
• 学部の成績
• 数学（面接）
• 面接

今年度の入試から配点が公開されており、書類（学部の成績など）５０点、英語３０点、数学３０点、面接（小論文含む）９０点になっています。学部の成績と面接でほぼほぼ決まってしまいそうな勢いです。また、NAISTの特徴として数学の試験が面接形式で行われます。詳しくは入試本番のところで触れますが、計算力などよりも論理的に問題が解けているかなどを重視しているようです。

準備（英語編）

自大学の入試でTOEICを受験していて、790点だったので受け直す必要もないかと思いそのまま提出しました。ちなみに入試に関するQ&A | 情報科学領域 | NAIST 国立大学法人奈良先端科学技術大学院大学によると、NAISTの日本語受験者の平均は６７０点だそうです。
が、９００点を超えるような受験者もいるようで、中央値はもっと低いのではないかと思います。だいたい６００点台あれば足を引っ張ることはないのではないでしょうか。

準備（数学編）

数学は面接形式で行われます。線形代数２問、解析２問が与えられ、それぞれ１問ずつ選んで解説しながらホワイトボードに解いていきます。範囲も今年度から？教科書が公開されています。

選抜方法等について : 情報科学研究科 | NAIST 奈良先端科学技術大学院大学

私は解析の方だけ購入して、線形はネットに落ちていた目次だけみました。が、マセマシリーズなどの一般的な大学生向けの教材で十分カバーできるのでわざわざ買う必要はなかったと思います。もし解析の教科書が欲しいと言う方がいれば、メッセージをいただければメルカリ等で格安でお売りします。

数学も自大学の院試である程度勉強していましたので、学部時代に使った教科書を使って演習を中心にさらっとなぞるくらいで終わらせました。もし１から勉強される方は、マセマシリーズの評判が良いようです。本屋で見ましたが、講義形式でたしかにわかりやすいと思います。

NAISTのホームページで問題例が公開されていますが、基礎的な問題のようなので、地道にマセマシリーズの線形と微積の演習問題を身につけていけば十分だと思います。

準備（小論文）

小論文は以下の２つの課題について記述するようです。

• これまでの修学内容（卒業研究）について
• 本学において取り組みたい研究分野・課題について

２つの課題のどちらをどれだけ書くかは指定されていませんが、私はこれまでの修学内容を４分の１くらい書きました。その中に、NAISTを受験する動機を書きましたが、課題の範囲外だと思うので、結論の部分で少し触れるくらいにすればよかったと思っています。

取り組みたい研究分野・課題については

• 動機
• 背景，社会的・学術的意義
• 先行研究
• 課題
• アプローチ

の構成で書きました。とりあえずサーベイしたり、オープンキャンパスに行ったり、教授が書かれた書籍を読んだりして課題やアプローチを考えました。具体的なアプローチは思いついていなかったので、方向性だけ書きました（こんな課題があってこんなアプローチも研究されているけどまだまだ十分に議論されてないし、そういう方向で研究していきたいみたいな感じ）。

書き終わって、志望研究室の博士の方に添削をしていただきました。本当にありがとうございます（最後のアプローチの節は添削で指摘していただいて追加しました）。

何から始めれば良いの！って方は、研究室のホームページから発表された論文を読み漁ることから始めると良いと思います。小論文を一般公開するのはまだ少し怖いので、メッセージをいただければお見せします。

小論文に沿って面接をするので、理解していない内容を背伸びして書くよりも、理解できる範囲で最善を尽くして分野への興味、動機をアピールした方が良いと思います。

入試当日

宿泊

入試前日はゲストハウスせんたんに宿泊したかったのですが、受験票を受け取った時点で満室だったのでビジネスホテルに泊まりました。

私は学園前駅という駅周辺で探しました。NAIST周辺で交通アクセスを考えるとここらへんがベストだと思います。NAISTまでバスで３０分くらいです。２つくらい一応リンクを貼っておきます。

www.superhotel.co.jp

www.toyoko-inn.com

２つとも学園前駅から電車で１０分かからないくらいのところです。大阪メトロの中央線から生駒駅で乗り換えしていけます（田舎者なので乗り換えナビに従いました）。

（追記）別の機会に利用したんですが，オークホステル奈良がNAIST圏内で最安ではないかと思います。
oakhostel.com
私が泊まった時はドミトリー（２段ベットがいっぱいある部屋）で一泊２０００円でした。ただ、同じ部屋でたくさんの人が過ごしているし、外国人もたくさん利用しているので，試験前日でゆっくりしたい人は東横とかにしたほうがいいです。近鉄奈良駅のすぐ側なので、立地的には前述のホテルと大差はありません。とにかく安く済ませたいひとにはおすすめです。

受験まで

私は１３時からだったんですが、１１時頃ついたので図書館で暇をつぶしました。面接では３分程度で小論文の内容をプレゼンしないといけないので、その練習をひたすらしていました。図書館で待機している受験生はあまり多くなく、雰囲気もいい感じだったのでよかったと思います。

１２時４０分から受付を開始して、受験控え室にいきます。オープンキャンパスで説明会があった場所でした。１３時がくると順にアンケート、面接に進んでいきます。私は最後だったので１時間２０分くらい待ちました。待機している間は、電子機器は使用不可ですが紙媒体のものならば自由にみて構わないようでしたので、線形の教科書をぼーっと眺めていました。

アンケートは、専願か併願か、どこでNAISTをしったかなどの簡単なもので、面接時に面接官が参照できるようでした。

数学

アンケートの後、問題閲覧室にいって問題を１０分間見ます。白紙の計算用紙も使用できました。幸い線形も解析も基本的な問題があったので、ほっとしながら一通りときました。

解いた問題は

• 

（１）固有値、固有ベクトルを求めよ。

（２）対角化せよ。

（３）を求めよ。

• ただし

（１）とおいて置換せよ。

（２）積分値を求めよ。

でした。変換行列？は直交行列にしないのかな？と思いましたが固有ベクトルをそのまま使うように指示されていました。

その後、面接室に進んで２人の面接官に説明しながら解いていきます。解き終わったときに、おしいねぇ〜と言われました。結構自信があったので、説明不足とかで減点があるのかもしれないです。

面接

数学が終わると別室で面接があります。まずアンケートの内容について確認され、小論文についてプレゼンするように言われます。かなり練習したおかげか、つまることなくスラスラ言うことができました。その後色々質問されますが、

• 卒業研究について入力と出力の確認
• 卒業研究の新規性・工夫した点
• 修士修了後のキャリアプラン
• どうしてこのタイミングでNAISTを受験したか
• 卒業研究ではプログラムを何行くらい書いたか

くらいでした。どれも回答を用意していた質問だったので答えられましたが、面接官の反応は良くもなく悪くもなくでした。NAISTでしたい研究についてまったく質問がなかったので、そんなにひどい内容だったのかと落ち込みました笑

まとめ

面接におびえていましたが、深くつっこまれる質問はなく拍子抜けした感じでした。NAISTの募集要項では

基礎学力、研究に対する意欲、潜在的な研究能力を総合的に評価します

とあります。基礎学力や潜在的な研究能力は数学、英語、小論文で見ると思うので、面接ではなぜわざわざNAISTにいきたいのか、研究分野についてどれだけ興味をもっているのかが大きな評価基準になっているような気がします。

小論文でもやる気を表現できますが、面接でそれについて深く答えられないと、あぁこいつはどっかの論文かなにかから引っ張ってきただけで興味をもって調べてはないんだな、みたいになると思います。それが一番最悪の事態だと思うので、面接の対策も兼ねて小論文をしっかり書くことをおすすめします。

質問等がある方は気軽に連絡をいただければと思います！この記事がNAISTを受験する方の助けになれば幸いです。