CODE THANKS FESTIVAL 2014 B日程 G: 石取りゲーム

久しぶりに解説記事。またまたゲームの問題。

問題概要

原文 → G: 石取りゲーム - code thanks festival 2014 B日程 | AtCoder

個の石が積まれた山があり、人のプレイヤーが交互に石を何個か取っていき、最後の石を取ったプレイヤーが勝ちとなるゲームを行う。1手で取れる石の個数は、ゲーム開始時に先手が取るときはの範囲、それ以降は (前のプレイヤーが取った石の個数) の範囲である。が与えられるので、両者が最善に行動した時の勝者を出力せよ。

解説

まず、solve(i, j)なる関数を考えます。これは、山に i 個石があり、1 〜 j 個の範囲で石が取れる時の勝者を bool 値で返します。

この問題で重要なことは、i と j が決まれば勝者が決まるということです。solve 関数同士の関係をみていきます。

• 取れる石の個数の最大値が残りの個数以上である場合、全部取れるため必ず勝てる
• 取れる個数を全て試して、その中でも一つでも false が返ってくれば勝てる
• 全て試してもヒットしなければ、勝てるパターンが無いため負け

ということが言えます。2つ目の条件でなぜ false なのかというと、ここで参照しているのは前のターンの出来事であり、先攻と後攻の扱いが逆転しているからです。したがってもう少しシンプルに書くと

• i <= j ならば true
• i > j のとき、1から j の範囲まで solve を試し、どこか1つでも false ならば true
• false が1回も返ってこなければ false

と判定できます。もちろん、メモ化が必須です。

ソースコード

int n, p;
int dp[510][510];

// 勝敗判定
bool solve(int rest, int range) {
    // メモ化 (すでに書いてあったらそれを返す)
    int &res = dp[rest][range];
    if(res != -1) return res;

    // range が rest を覆えるならば勝てる
    if(rest <= range) return res = true;

    bool ok = false;
    // 以下は range が rest を覆えない時の話
    // 範囲の中に一つでも false
    // (つまり前のターンで後手必勝) があるなら true
    // 取る石は 1 個以上 range 以下
    repq(i,1,range) {
        // 石は i 個なくなり、範囲は i+1 になる
        if(!solve(rest-i, i+1)) ok = true;
    }
    return res = ok;
}

signed main() {
    cin >> n >> p;
    memset(dp, -1, sizeof(dp));
    bool ok = solve(n, p);
    cout << (ok ? "first" : "second") << endl;
    return 0;
}

前にこのブログで紹介したゲームの問題の中にも、同じ方針で解けそうなものがありますね。ゲームの問題も奥が深いですね。

※追記: 前に紹介した問題たちは制約が大きいのでそもそもメモ化できないですね。同じような問題ですがこの解法は使えないです。難しいなあ・・・

DDCC2016 本戦 参加記

DISCO presents ディスカバリーチャンネル コードコンテスト 2016 本戦に参加しました。どこよりも早く、を目指して参加記書いてみます。

-N日目 (予選)

セキュリティミニキャンプ in 北海道(過去記事参照) の1日目の夜にDDCCの予選があったので、ホテルからコンテストに参加した。

A問題はすぐ解けた。B問題は日本語が難しかったけどAC。Cは制約をくぐりぬける方法が分からず、結局2完・・・。このときボーダーラインを把握していなかったので絶対通ってないだろうなあと思っていた。

あとあと調べて、自分の順位でも本戦の可能性があることを知った。結局、161位で通過してた。うれしい。でも前回のDDPCを見るにこのままだと本戦で玉砕されるので頑張らないとなあという気持ちになった。

0日目 (本戦前日)

本州に住んでいないので前日移動必須。東京到着が遅くなりそうだったので、空港でラーメンとビールを食べてから飛行機へ。なんか天気予報では雪が降るとか言われてて、飛行機飛ぶのかどうかちょっと怖かったけど無事飛んでよかった。22時くらいにはホテルについてまったりしていた。

1日目 (本戦当日！)

23時半くらいに就寝を試みるも寝れず、睡眠が断続的になる。でも当日は5時に起きた。はやすぎ。前回のDDPC解いたりとかあがいていた。

少し早めに会場につくものの電源争奪戦に敗れる。パソコン2台もってきてよかった。Tシャツとシールをもらって「これがオンサイトか・・・」という気持ちになりテンションが上がる。

オープニングビデオがDDCC開会の合図。自分は北海道から来たのに「北は東北からお越しいただき～」みたいなアナウンスが入り笑ってしまった。開会式終わったらへんからめっちゃ緊張してきてやばかった (緊張のあまり手を震わせながらツイートしていた)。あと隣がやたらインタビューされてて大変そうだった。

そしていよいよ本戦スタート！

• 1問目はEPS考慮したら逆にバグったりしてつらかった(たぶん自分のライブラリに問題がある？)けどAC。
• 2問目は3つ目のケースがどうもうまくいかず唸ってたら部分点解法出すの忘れていた。結局満点取れなかったしつらさしかない・・・。
• 3問目は見たけどやってない。4,5問目は見てすらいない。こうして私の初オンサイトコンテストは散ったのだった・・・(オンサイトの洗礼)

幾何っぽい問題と文字列で攻められたら途端に点数が全く取れなくなるのはダメですね。分野によって理解度にムラがありまくるので、もっと精進していきたい・・・。

コンテストが終わって昼食フェーズ(懇親会)に入る。フォロワーに何人か会えてとてもテンションが上がり、オンサイト最高という気持ちが最高潮に達した。他の大学の競技プログラミング事情とか、競プロサークル等に所属せず趣味でやっている人の話とかいろいろ聞けて面白かった。

特別講演で厚切りジェイソン氏のお話を45分間ほど聞いた。米国と日本の会社の体質の違いとか、厚切りジェイソン氏本人の経験などなど貴重な話をたくさん聞けて良かった。リンゴの話が一番なるほどなあとなって、今だけでなく未来も見据えたうえでベストな答えは何なんだろうということを常に頭に入れて動かないとなと考えさせられた。

表彰式後に、懇親会パート2が始まった。ここでもフォロワーの何人かとお話しできてとても良い時間を過ごせた。来年のICPCの話とかもしてて、来年は国内予選抜けてアジア地区でまたいろんな人に会いたいなあ・・・とか思ってた。

総括

今回が初オンサイトだった私は、問題が解けるかどうかももちろん不安だったけど、競プロerの輪の中に入れるかどうかが結構不安だった。でもそれは意外と何とかなってとても楽しい時間を過ごせたし、何より今回で競技プログラミングに対するモチベーションがだいぶ上がったので行けて本当によかったなあと思う。またオンサイトの機会があればぜひ行きたいし、行けるようにもっと頑張りたい。

こんなとこかな。次のオンサイトはいつだろう・・・。

競プロをやりはじめてから半年が経ちました

競技プログラミングを初めて、今日でちょうど半年です。(私が初めて使用したオンラインジャッジであるAtCoderの初AC日を、競プロ初日としています)

「競技プログラミングはじめたいけど、なにからやればいいのかな・・・」とか、「この大会の準備期間短いけど今から頑張ったら間に合うかな・・・」とか、その辺の疑問にお答えできたらいいなあと思い記事を書くことにしました！特に初心者のかたは参考にしてください(プロはこわいから見なくてもいいですよ ＞＜)

競プロ初心者がやるべきこと

入出力やSTL・簡単なアルゴリズムを勉強する

まず、プログラムが書ける状態までもっていかないと何も始まりません。まずは、図書館等で基本的なプログラミングの知識をつけましょう。標準入出力、for、while、if等使えるようになれば十分です。ポインタとかクラスとかは競技プログラミングではそんなに意識しなくてよいです(でもライブラリ作るときに必要になるかもしれないので勉強するに越したことはないです)

自分はそのへんどうだったかというと、競プロ始める前はCしか知らなかったためC++の記法を勉強するときはちょっと大変でした。とはいえ、毎日のようにプログラム書いてたらそのうち覚えるので頑張りましょう。ネットで検索したら初心者向けのスライドが転がってるので、そういうのも参考になりますよ。

アルゴリズムに関しては「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」(通称: TLE本)や「プログラミングコンテストチャレンジブック」(通称: 蟻本)が非常に参考になります。最初に読むならTLE本ですかね、蟻本は初級編からけっこう難しいので・・・。TLE本がわかってきたら蟻本を読む、という流れが良いと思います。

オンラインジャッジで修行

初めのうちはコンテストに出るよりも、出題形式や提出方法に慣れるために、またアルゴリズムを学ぶために、問題を解きまくるのが良いです。例えばAtCoderの場合なら、AtCoder Beginner ContestのA・B問題が簡単なのでまずはそこから埋めていきましょう。で、だんだん慣れてきたらCとかDとかに挑戦して・・・という感じですかね。自分のレベルに応じて問題を選んでいってくださいね。

出題形式はコンテスト出る前に把握したほうが良いです。特にTopCoderがちょっと特殊で、main関数に処理を書くのではなくクラスのメンバ関数に処理を書くことになります。一度やっておかないとコンパイルエラー頻発でコンテスト中悲しい思いをするので、事前にやっておくことをおすすめします。

コンテストに参加する

ある程度経験を積んだらコンテストに参加してみましょう。私はコンテスト出たいマンなのでやたら参加してますが(5/19に初めて5/28にはもうコンテスト出てました。せっかちすぎる)、自分のペースで参加しましょう。というのも、コンテスト終了後に復習しないと出た意味がほとんどなくなるので、復習が可能なレベルで出る必要があります。

コンテストはTopCoder、Codeforces、AtCoder等で行われています。AtCoderは日本語で行ってくれますが、ほかは英語ですね。最近Google翻訳が強くなったらしいので、英語に抵抗のある方も是非参加してみては・・・？

ライブラリを作る

上位を狙うなら必須です。上位行ったことない私が言うのもなんですが・・・。

ライブラリとは、「このアルゴリズム使いたいぞ！」となったときにすぐに使えるように、予め用意しておくものです。グラフ理論とか幾何でよく使いますね。

で、これを作ることによって解答速度が速くなって良いのは当たり前なんですが、それ以上に「そのアルゴリズムを自分の中で咀嚼できる」のが大きいと自分は思っています。意味を理解しつつライブラリを作っていくと、自分の中で考えが整理できてとても良いので、ちゃんと理解するという意味でもライブラリ作ったほうが良いです。

自分の話

いろいろ書きましたが、実際お前はどんな感じでやってきたねん、ということで振り返ってみます。

大学の競技プログラミングサークルに初めて見学に行った(5/19)。この日から競プロはじめました。AtCoderの問題を使ってバーチャルコンテストをしていたので、AtCoderはじめました。当時Cしか書けず文字列の問題で詰みまくっていたのでC++を勉強するとぞと心に誓う。その時はICPC出ないでおこうかなと思ってたけどなんだかんだで出ることにした。

ICPC国内予選に参加した(6/24)。競プロ歴まだ1ヶ月くらい。自分のチームは、他のメンバーも同じくらいの経験値だったけど3完した。正直これは運が良すぎただけ。だってまだC++に慣れてなさすぎて、setにある要素が入っているかどうかってなんの関数使えば分かるっけ？みたいなレベルだったので・・・。グラフや幾何、DPは全く歯が立たなかったので、これから頑張っていこうと思った。

ICPC後はTopCoderとかCodeforcesとか、やたらいろんなものに手を出した。Twitterのフォロワーが頑張ってるのを見ると触発されて自分も出ちゃうんだよねー。Twitterにいるプロがモチベーションの源でした。

夏休みからライブラリを整備し始めた。AOJにはverify時に大変お世話になりました。特に幾何のライブラリが潤って、ライブラリ使うだけ問題は対処できるようになった。しかし経験が足りない。

あとは、夏休み中に蟻本の初級中級はだいたい読んだ。でもまだフローがわからない、むずい。上級は未だに読めてないなあ、あかん。

9月10月、こどふぇすワンチャンあるかなと思って予選参加するも通らず。まあ、当たり前ですね。来年に向けて1年間精進するぞと思った。

11月、全く狙ってなかったけど DISCO presents ディスカバリーチャンネル コードコンテスト 2016 予選突破してしまった。正直行ってB3補正のおかげで通ったようなもんだけど、オンサイトのコンテストに行けるというのはやっぱり嬉しいですね。本戦が楽しみです・・・。

本戦とかがかかったコンテストで勝つには、最低でも半年は必要な気がしますね。相当センスある人だったらもう少し短くても行けるかもしれないけど、経験が物を言うところがやっぱり大きいですからね・・・。

というわけで、ざっくり言うとこんな感じで取り組んでました。もっといろんなコンテストで結果出せるようになりたいですね。

目標とか

さて、競プロ歴1年を迎える前に達成しておきたいことをまとめておきますかねー。

• レートあげたい

AtCoder、Codeforces、TopCoder全部そうなんだけど、青色になりたい。もう少しがんばれば到達しそうな雰囲気はあるから、このまま頑張っていきたい。

• ライブラリ充実させたい

ジャンルによってライブラリの充実度が違いすぎるので、どの分野も充実させたい。あとライブラリのバグ発見したい。

• 蟻本読み進めたい

もう難しいところしか残ってないし、なかなか読み進めるのが大変だけど、なんとか乗り越えたい。

こんなところですかね。次の半年間も実りあるものにしたいですね。精進します。