t8m8-mem8

競プロとか、学んだことを書いていきます。

チェスで勝てるようになるために

この記事はNCC Advent Calendar 2015の18日目の記事です。

競プロの話ばっかりなので今回はチェスについて書こうと思います。

僕の場合、チェスは基本的にオンラインのみで対局しています。
将棋はやらないの?とよく聞かれますが、将棋はほとんど指していません。逆に日本では、将棋は指すけれどチェスはしないという人の方が多いのかなーと思っています。
チェスを真面目にやってる人からしたら僕はまだまだ初心者なので、趣味としてちょくちょくやっている素人からルールは知っているけれど勝てない or ルールを全く知らない初心者へ向けた記事になります(この一文はマサカリから身を守る一般的なテクです)。

ルール

ルールは難しくないですが、書いていると長くなりそうなのでwikipediaに譲ります。
チェスのルール - Wikipedia

チェスのオンライン対局サイト

チェスをするには対局をする相手がいないといけません。
身近にチェスをしてくれる友達がいれば良いですが、なかなかそういう人はいないでしょう。
そこで、チェスの対局や練習をするためのサイトを紹介します。

lichessというサイトがおすすめです。
僕はほとんどこのサイトでしかチェスをしていません。
レート戦をすると、1500からのレートが付きます。僕のレートはmax1800くらいです。
いろいろと機能が豊富で、特に対局後にその試合の棋譜解析することができるのが良いです。
棋譜解析をすると自分と相手の悪手やその代替案を示してくれるので勉強になります。

あと、GitHubScalaのコードがあがってるので眺めてみるとおもしろいかもしれないです。
ornicar/lila · GitHub

他のサイトだとChess.comが良いらしいです。
僕の勝手なイメージだと、熱心にやっている人たちはこちらにも手を出している気がします。

チェスをやったことがない人はこれ以降を読む前に是非一度これらのサイトで対局をしてみると良いと思います。
初めのうちはだいたい勝てないと思いますが、頭を使って自由に対局してみましょう。

対局中に意識すると良いこと

チェスには、戦況がどちらに傾いているかを判断する指針として、マテリアルアドバンテージ(ピースの得点による評価)とポジショナルアドバンテージ(位置による評価)があります。
ピース(駒)の価値はポーンを1点としたときに、ビショップとナイトを3点、ルークを5点、クイーンを9点として計算することが多いです。
マテリアルアドバンテージは合計得点が多いほうが有利という考え方で、これは直感的にわかりやすいです。
ポジショナルアドバンテージは位置による評価ですが、中心をいかに占めているか、ピースの効きがどれだけ広いか、など評価の仕方は人によっていろいろなようです。

マテリアルアドバンテージを得ることに意識がいきがちですが、実力が拮抗しているほどこれは難しいです。
なので序盤は特に、ポジショナルアドバンテージをいかにして得るかを考えると良いと思います。
わかりやすい例だと、ピースの価値が同じもの同士の交換をポーンの形が崩れるように行うというのが挙げられます。ポーンの形が崩れている状態とは、ポーンが同じファイル(縦の列)に並ぶ、キングを守りづらい形になる、中央(dファイル,eファイル)から外れる、などの状態です。

他にも考えるべきことはいろいろあります。数をこなして知見を積んでいきましょう。

オープニングを知ろう

オープニングとはいわゆる定跡のことです。
オープニングを知ることが強くなるのにはとても有効であることは言うまでもありません(あまりやったことがない人がいきなり覚えようとするのには賛否両論ありそうですが)。
多くのオープニングを知っているのに越したことはないのでしょうが、数が多すぎて全部覚えようとするのは大変です。
なので、得意なオープニングを2~3つくらい覚えて使い続けるのが良いと思います。

覚えるオープニングの選び方

何度か試してみて自分の好きなもの・合ったものを選ぶというのが無難だと思います。
はじめは適当に選んでとりあえず使い続けてみるというのが良いでしょう。
僕は名前がかっこいいものとかあんまり見ない珍しいものとかを選んで使い続けていました。
ただ覚えるのではなく、どうしてそのオープニングが良いとされているのかを考えながら使ってみると、どれも結構理にかなっていることがわかっておもしろいです(だからオープニングとして広まっているわけですが)。

List of chess openings - Wikipedia, the free encyclopedia

僕のよく使うオープニング

最近は以下の2つばっかりです。
シシリアンディフェンスは相手がe4にポーンを突いてこないときは使えないので、そういうときは相手に合わせて別のオープニングを使います。

  • Polish Opening(Sokolsky Opening)
  • Sicilian Defence: Najdorf Variation

おわり

結局のところ、強くなるにはよく考えながら数をこなすということを避けては通れません。
誰か一緒にチェスしましょう。

CODE FESTIVAL 2015 FINAL 参加記

11/14と11/15にCODE FESTIVALに参加してきた。
今更だけど書く。終わってから2週間経ってないし、THANKS FESTIVALもまだだしセーフセーフ。

recruit-jinji.jp

予選突破まで

去年

競プロを始めたのとほぼ同時に飛び込んだJAG合宿でトイレ5個さんがCODE FESTIVALの話をしていた。謎コンというワードも聞こえてくる。なんのこっちゃ、という感じだった。
とりあえず予選に参加する。突破できずに、CODE THANKS FESTIVALへの参加。
THANKS FESTIVALが楽しくて「来年は絶対本選出場する」と意気込む。

今年

kenkooooさんの非公式予選突破練習会に2回とも参加した。
1回目は去年の予選問題を解いて、2回目は「予選BのD問題はDPに違いない!」ということだったのでDPの問題をいろいろ解いてた。
知り合いも増えて楽しかった。

予選を突破。1つの目標だったので嬉しい。
練習会のおかげで予選突破できた!(と言うと練習会の株が上がるだろうか)

Day 1

新宿と新宿西口を間違える→ry0u_ydくんとの待ち合わせに遅れる。
六本木駅に着く→会場まで歩く→迷子になる。
遅刻連絡をしようとする→スマホの充電が切れる。
これはひどい

なんとか会場に到着、めっちゃ人がいる。これが全部競プロerだと思うとテンションが上がった。

本選が始まる。問題の内容は他の人たちが良い記事を書いているので省略。僕はStarrySkyTreeをバグらせて死んでた。

本選終了後は、けんしょーさんのトークライブを聞きに行く。結構共感できることが多かった。
その後、秋葉さんのトークライブを聞きに行く。Euler Tour Techniqueの説明がスッと頭に入ってきてわかりやすかった。
エキシビジョンマッチを観戦する。僕はyosupotさんの画面をずっと見ていた。みさわさんが紹介していた本は読んでみようと思う。

ホテルに着く。数人で飲みに行く。こういう機会しか競プロerの人たちと飲みに行くことはできないので良かった。楽しくてすぐ時間が過ぎてしまった。

Day 2

寝坊した。

電車で会場へ。10時に到着してEasyに参加。Easyは全完できた。
chokudaiさんのライトニングトークを聞きにいく。真面目っぽい話をしている。

チーム戦が始まる。チームの人たちとグラフの種類数えたり、問題の解法を教えてもらったりしておもしろかった。難しい問題をさくっと通していく人たちやばい。早くこの人たちに追いつきたい。

まとめ

超楽しかった。是非来年も参加したい。

皆さんお疲れ様でした。

El Capitan に Sublime Text 3 を入れ直したからまとめた

El CapitanをクリーンインストールしたのでSublime Textを今まで使ってた状態に戻す。
せっかくなのでやったことをまとめる。
VSCode? Atom? 聞こえない聞こえない。

Sublime Text 3をインストール

今まではhomebrew-caskでいれていたけれど、homebrew-caskは今後使うのを止めることにしたので

Sublime Text - Download

から普通に落としてきた。

Package Controlをいれる

Installation - Package Control

ここに書いてある通りにいれる。

プラグインを追加

とりあえず以下のものを入れた。
下の3つはあんまり使ってないかも。

Vimライクにする

以下のプラグインを入れる。

Preferences.sublime-settingsに以下を追加

{
    // vim mode
    "vintage_ctrl_keys": true,
    "vintage_use_clipboard": true,
}

【Sublime Text】愛好家必読!Vim化しよう - 悲しいけど、オレ素人プログラマなのよね

この記事とかを参考にキーバインドを設定する。
ただし、jを2回押しでinsertを抜ける設定は上の記事通りに記述すると、抜けた直後の入力が1回キャンセルされてしまう。
以下のように書くといい感じに動く。

{
    "keys": ["j", "j"],
    "command": "_enter_normal_mode",
    "args": {"mode": "mode_insert"},
    "context": [
        {"key": "vi_insert_mode_aware"}
    ]
},

かっこよくする

結局エディタなんて見た目が一番大事なんだよ!!!
ということで、僕のお気に入りを紹介する。
最終的にはこんな感じになる。

f:id:t8m8:20151122021032p:plain

テーマを変更する

Preferences.sublime-settingsに以下を追加。

{
    // Seti_UI
    "theme": "Seti_orig.sublime-theme",
    "Seti_ClosedFolder_same": true,
    "Seti_SB_bright": true,
    "Seti_blue_tab_label": true,
    "Seti_no_bar_undertabs": true,
    "Seti_rainbow": true,
    "Seti_sb_small_padding": true,
    "Seti_sb_tree_small": true,
    "Seti_tabs_med": true,
}

カラースキームを変更する

Preferences.sublime-settingsに以下を追加。

{
    // Mirodark
    "color_scheme": "Packages/Mirodark Color Scheme/MirodarkHighContrast.tmTheme",
}

フォントを変更する

Preferences.sublime-settingsに以下を追加。

{
    // Migu 1M
    "font_face": "Migu 1M",
}

アイコンを変更する

好きなアイコンを探してくる。

Dribbble - Sublime Text icon replacement for Flatland Theme by Ernest Ojeh

僕は毎回このアイコンを落としてくる。
アプリケーションフォルダのSublime Text 3を右クリック→「情報を見る」をクリック
落としてきたicnsファイルを今のアイコンの上にドラッグして起動しなおすと変更できる。

f:id:t8m8:20151122015547p:plain

できた。

ターミナルから起動できるようにする

El Capitanからは

$ sudo ln -s /Applications/Sublime\ Text.app/Contents/SharedSupport/bin/subl /usr/local/bin/subl

を叩くと

$ subl {filename}

でファイルをsublimeで開くことができるようになる。
リンクを貼る先が変わったのはRootlessの影響なんだろうか。


最終的な設定ファイル

Preferences.sublime-settingsはこれまでの内容に基本設定をいくつか追加してこんな感じになった。

{
    // vim mode
    "vintage_ctrl_keys": true,
    "vintage_use_clipboard": true,

    // Seti_UI
    "theme": "Seti_orig.sublime-theme",
    "Seti_ClosedFolder_same": true,
    "Seti_SB_bright": true,
    "Seti_blue_tab_label": true,
    "Seti_no_bar_undertabs": true,
    "Seti_rainbow": true,
    "Seti_sb_small_padding": true,
    "Seti_sb_tree_small": true,
    "Seti_tabs_med": true,

    // Mirodark
    "color_scheme": "Packages/Mirodark Color Scheme/MirodarkHighContrast.tmTheme",

    // Migu 1M
    "font_face": "Migu 1M",

    "font_size": 11,
    "highlight_line": true,
    "scroll_past_end": true,
    "overlay_scroll_bars": "enabled",
    "trim_trailing_white_space_on_save": true,
    "caret_style": "phase",
    "default_encoding": "UTF-8",
    "trim_automatic_white_space": false,
    "file_exclude_patterns":
    [
        "*.pyc",
        "*.pyo",
        "*.exe",
        "*.dll",
        "*.obj",
        "*.o",
        "*.a",
        "*.lib",
        "*.so",
        "*.dylib",
        "*.ncb",
        "*.sdf",
        "*.suo",
        "*.pdb",
        "*.idb",
        ".DS_Store",
        "*.class",
        "*.psd",
        "*.db"
    ]
}

Default (OSX).sublime-keymapはこんな感じ。

[
{
    "keys": ["g", "t"],
    "command": "next_view",
    "context": [
        { "key": "setting.is_widget", "operand": false },
        { "key": "setting.command_mode" }
    ]
},
{
    "keys": ["g", "T"],
    "command": "prev_view",
    "context": [
        { "key": "setting.is_widget", "operand": false },
        { "key": "setting.command_mode" }
    ]
},
{
    "keys": ["j", "j"],
    "command": "_enter_normal_mode",
    "args": {"mode": "mode_insert"},
    "context": [
        {"key": "vi_insert_mode_aware"}
    ]
},
{
    "keys": ["ctrl+j"],
    "command": "exit_visual_mode",
    "context": [
        { "key": "setting.command_mode"},
        { "key": "num_selections", "operand": 1},
        { "key": "selection_empty", "operator": "equal", "operand": false, "match_all": false }
    ]
},
{
    "keys": ["tab"],
    "command": "move",
    "args": {"by": "characters", "forward": true },
    "context": [
        { "key": "following_text", "operator": "regex_contains", "operand": "^[)}'\"\\]]", "match_all": true },
        { "key": "auto_complete_visible", "operator": "equal", "operand": false }
    ]
},
{
    "keys": ["tab"],
    "command": "auto_complete",
    "context": [
        { "key": "auto_complete_visible", "operator": "equal", "operand": true }
    ]
},
{
    "keys" : ["shift+tab"],
    "command" : "hide_auto_complete",
    "context" : [
        { "key" : "auto_complete_visible", "operator": "equal", "operand": true }
    ]
}
]

他にも競プロ用のスニペットを登録したりとかしてる。

イカしてるプラグインとかあったら教えてください。
おわりー。

SRM 672 Div1 Easy: Procrastination

問題

Procrastination
社員が無限にいる会社がある。
社員其々に1つずつタスクが割り当てられており、始めは社員番号x番の社員にタスク番号x番が割り当てられている。社員番号は1から無限に続く。
h時間経過すると、社員番号がhより大きいhの倍数の社員は、社員番号が1つ大きい隣の社員とタスクを交換する(h=1のときは交換は行われないとする)。
hとnが与えられるので、h時間経過したときにn番のタスクが何番の社員が割り当てられているかを答えよ。

制約

 2 {\leq} n {\leq} 10^{10}

解法

2つの連続する素数の交換が行われないことを利用して探索範囲を絞り込むと良いらしい。
nより小さい素数とn以上の素数の間にある数が解候補なので、それらの数の因数を列挙していく。
因数を小さい順に見て、実際にシミュレーションすると最終的な解が得られる。

素数の間隔について調べてみたらこんな記事が出てきた。

tsujimotter.hatenablog.com

どうやら2つの連続する素数の間隔が600以下であることは証明されているらしい。
そもそも素数の間隔に上界があることを知らなかった。
この問題は区間を素数間にしないで適当な区間であたりをつけても通るっぽい。

public long findFinalAssignee(long n) {

    long lb = n-1, ub = n;

    while (!isPrime(lb)) lb--;
    while (!isPrime(ub)) ub++;

    TreeSet<Long> set = new TreeSet<Long>();

    for (long i=lb+1; i<=ub; i++) {
        for (long j=2; j*j<=i; j++) {
            if (i%j == 0) {
                set.add(j);
                set.add(i/j);
            }
        }
    }

    for (long h : set) {
        if (n%h == 0) {
            n++;
        } else if (n%h == 1) {
            n--;
        }
    }

    return n;
}

boolean isPrime(long n) {
    for (long i=2; i*i<=n; i++) {
        if (n%i == 0) return false;
    }
    return true;
}

SRM 477 Div1 Medium: PeopleYouMayKnow

問題

友人関係friendsと人の番号person1,person2が与えられる
friendsはN文字の文字列を値とするN要素配列で、i番目要素のj番目文字が'Y'のときはiとjが友人、'N'のときは友人でない。
あるAとBを決めた時に、AがBの友人であるときBはAの友人であるが、AとCが友人でCとBが友人のときにAとBが友人であるとは限らない。
AとBが友人のとき、AとBは1-friendsだと呼ぶ。また、 n{\geq}1においてAとCがn-friendsのときCとBが友人であるようなCが存在すれば、AとBは(n+1)-friendsである。AとBがn-friendのとき、AとBは(n+1)-friendsでもあるとする。
person1person2が3-friendsでないようにするためには最小で何人取り除けばよいかを求めよ。

制約

 2{\leq}|friends|{\leq}40

解法

最大フロー最小カット
person1,person2の両方と友人である人をまず取り除く。
その後、新しくフローネットワークを作ってsourceをperson1,sinkをperson2とした最大フローを求める。
はじめに取り除いた数と最大フローの和が求めるべき解になる。

public int maximalScore(String[] friends, int person1, int person2) {
    int n = friends.length;

    char[][] link = new char[n][];
    for (int i=0; i<n; i++) link[i] = friends[i].toCharArray();

    int cnt = 0;
    for (int i=0; i<n; i++) {
        if (link[i][person1] == 'Y' && link[i][person2] == 'Y') {
            cnt++;
            for (int j=0; j<n; j++) {
                link[i][j] = link[j][i] = 'N';
            }
        }
    }

    DirectedGraph g = new DirectedGraph(n);

    int[] level = new int[n];
    for (int i=0; i<n; i++) {
        if (i == person1) level[i] = 1;
        else if (link[person1][i] == 'Y') level[i] = 2;
        else if (link[person2][i] == 'Y') level[i] = 3;
        else if (i == person2) level[i] = 4;
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (link[i][j] == 'Y' && level[i] != 0 && level[j] != 0 && level[i] < level[j]) {
                g.addLink(i,j,1);
            }
        }
    }

    return requireMaxFlow(g,person1,person2) + cnt;
}

class DirectedGraph {

    public static final int INF = Integer.MAX_VALUE/2;

    public final int n;
    private ArrayList<ArrayList<int[]>> adjlist;

    public DirectedGraph(int n) {
        this.n = n;
        this.adjlist = new ArrayList<ArrayList<int[]>>();
        for (int i=0; i<n; i++) adjlist.add(new ArrayList<int[]>());
    }

    public void addLink(int from, int to) {
        addLink(from,to,0);
    }

    public void addLink(int from, int to, int c) {
        adjlist.get(from).add(new int[]{to,c});
    }

    public ArrayList<int[]> get(int v) {
        return adjlist.get(v);
    }

    public String toString() {
        StringBuilder res = new StringBuilder();
        for (int i=0; i<n; i++) {
            res.append(i).append(" ").append(Arrays.deepToString(adjlist.get(i).toArray())).append("\n");
        }
        return res.substring(0,res.length()-1);
    }
}


static int requireMaxFlow(DirectedGraph g, int source, int sink) {
    int n = g.n;
    int[] cnt = new int[n];

    for (int i=0; i<n; i++)
        for (int[] link : g.get(i))
            cnt[link[0]]++;

    int[][] rev = new int[n][];
    for (int i=0; i<n; i++) rev[i] = new int[cnt[i]];
    for (int i=n-1; i>=0; i--)
        for (int[] link : g.get(i))
            rev[link[0]][--cnt[link[0]]] = i;

    int[][] flow = new int[n][n];
    int[] level = new int[n];
    int[] path = new int[n];
    int res = 0;

    while (true) {
        Arrays.fill(level,-1);
        path[0] = source;
        int ptr = 1;
        level[source] = 0;

        for (int i=0; i<ptr; i++) {
            int cur = path[i];

            for (int[] link : g.get(cur)) {
                int next = link[0], cap = link[1];
                if (level[next] == -1 && cap - flow[cur][next] > 0) {
                    path[ptr++] = next;
                    level[next] = level[cur] + 1;
                }
            }

            for (int next : rev[cur]) {
                if (level[next] == -1 && -flow[cur][next] > 0) {
                    path[ptr++] = next;
                    level[next] = level[cur] + 1;
                }
            }
        }

        if (level[sink] == -1) break;
        int f = 0;
        while ((f = dfsMaxFlow(g,level,rev,flow,source,sink,Integer.MAX_VALUE/2)) > 0)
            res += f;
    }

    return res;
}

Code Festival 2015 予選A D: 壊れた電車

感想

バグらせまくってつらい。

問題

壊れた電車

解法

二分探索 + Greedy

左寄せまたは右寄せをして全部の車両をカバーできるか判定する。

static void solve() {
    int n = in.nextInt();
    int m = in.nextInt();
    int[] x = new int[m];
    int[] y = new int[m];

    for (int i=0; i<m; i++) {
        x[i] = in.nextInt();
        y[i] = n + 1 - x[i];
    }
    Arrays.sort(y);

    long lb = -1, ub = Long.MAX_VALUE;
    for (int i=0; i<100; i++) {
        long mid = (lb + ub)/2;
        if (f(mid,n,x) || f(mid,n,y)) ub = mid;
        else lb = mid;
    }

    out.println(ub);
}

static boolean f(long t, int n, int[] x) {
    long l = 0;
    for (int i=0; i<x.length; i++) {
        if (x[i] - l - 1 > t) return false;

        long d = x[i] - l - 1;

        if (l >= x[i]) l = x[i] + t;
        else l = Math.max(x[i] + t - d*2, x[i] + (t - d)/2);
    }
    return l >= n;
}

JAG Summer Camp 2015 参加記

JAGの夏合宿に参加してきた。

実は去年も参加していて、去年は競プロを始めたのとほぼ同時期に参加したので、解説を聞いても全く理解ができない惨事だったけど、今回は去年よりはマシだった(去年よりマシなだけで良い結果ではなかった)。

コンテストぎりぎりまで寝ていたので2日目、3日目の朝食の時間にはTLEした。4日目はチェックアウトをする必要があったので頑張って起きてレッドブルの力を借りた。

懇親会や、コンテスト外の時間では普段話せない人たちとお話ができてよかった。TCOオンサイトやcode festival練習会で会った人も何人かいて話しやすかった。

来年もまた参加したい。そしてそのときにはもっと難易度の高い問題を解けるようになっていたい...。

この記事を書きながらcodefes非公式練習会の参加記を書いてないことを思い出した。完全に時期を逃してしまった...。とても楽しかったので、ああいうイベントがまたあれば是非参加したい。

復習した問題はまた記事にして書いていく(つもり)。