ICPC 国内予選 2018 参加記

昨日、ACM-ICPC 国際大学対抗プログラミングコンテストの国内予選 が行われました。自分が所属する北海道大学からは 4 チームが参加し、3 チームが 4 完・1 チームが 3 完しました。このうち 2 チームはアジア地区に行けそうで、弊学サークル全体のレベルの高まりを感じています。

チーム情報

今年も four-t として参加しました。メンバーは構文解析のプロ・ rsk0315 ( @rsk0315_h4x ) と幾何のプロ・ TAB ( @_____TAB_____ ) と数え上げが解けたり解けなかったりする趣味・自分 (tsutaj) の 3 人で、結成 2 年目です*1 。お茶汲み要員にならないようにがんばりました。

本番前

去年 Practice 1 位だったし*2 、今年も目指すか！例の数字をライブラリとして印刷して Practice も常勝！！！

・・・と思っていたけど、開いてみたら最後の問題が 500 円玉貯金 (2015 年国内予選 D) で草。まあこういう系統はかなり解いてきたし自分の担当分野でもあるので肩慣らしに解く。なんやかんやで今年も Practice 1 位になれました。

その後順位表のリセットが 2 回くらいあったけどその都度即座に提出して 1 位を防衛した (謎) (結果的にサブミットの練習になりまくった)

本番

本番の序盤の戦略は、TAB 君・えび君が A を読みつつ印刷クエリを投げ、自分は印刷されたものを眺めながら解けそうな人に問題を投げるという感じ。紙を届ける頃には A が終わっていたので (4:54)、実装ゲーっぽい B をえび君に、ちょっとした数学っぽい C を TAB 君に、そして自分は数え上げっぽい D をやることに。

D は見た目がアレなので (？) C を TAB 君と一緒に考えてみると、少し数学をして探索範囲を小さくすればよいことに気づく (割とすぐに気づいた)。 TAB 君と自分とで相談してみて方針が良さそうだったので TAB 君に実装してもらう。すぐ通してもらった (21:10) (ありがとう)

F は幾何で G が構文解析っぽいので、ここらへんで F を TAB 君に・G をえび君に投げて、解くべきかどうか判定してもらうことに。G はなんか無理そうで F は頑張れば行けそうな感じだったので、F を TAB 君に考えてもらう。

B はなんかつらそうにしていたので先に D を詰める。よく見るとサンプルの最後のケースが最悪ケースだが場合の数が少ないし、そもそも全チームの勝敗数が同じなら全チーム 勝 敗しているはずなので、枝刈り全探索で良さそうなことに気づく。

ここで F を考えていた TAB 君が解法を思いついたらしいので、D と F を並行して実装していく。やがて D が書き終わったので実行するも、やはりサンプルの最後の実行にはそれなりに時間がかかる。「D は書けたけどテストケースの実行にそれなりに時間かかりそうだし、F の実装してる間に並行して D を実行させるか〜」とか言ってたんだけど、最適化オプションつけたら爆速で終わって草。並行してやる必要ないやんけ！そんなこんなで D を通す (53:12)

B は書けたらしいが提出すると WA が返ってきたので、えび君がソースコードを印刷してバグを探す段階に入っていた。また F は途中まで書けたがその後の実装方針を詰めなければならないらしい。自分は他の問題を眺めるもすぐ解けそうなものはない。ここで取れる戦略としては色々あったと思うけど、自分は順位表と残りの問題の感触からまず B を優先すべきと判断し、F を引き続き TAB 君に考察してもらいながら、自分とえび君で B のソースコードを読むことに。

B のソースコードの問題点はしばらくしたら見つかった。PC を使っていた TAB 君に交代してもらって B を直して提出するもまたもや WA が返ってくる。操作中の配列を visualize しても挙動は間違ってなさそうなので、悶々とするなどした。

こういうときは「実装方針を変えれば良い」ということを去年のアジア地区で身をもって知っていた*3 ため、B の楽な実装方針を考えてみる。すると今まで考えていた場合分けが不要な実装方針を思いついたので、それを自分が書くことにした。

問題文を読みながら、入力を受け取ってここはこう処理して〜と書いてるうちに、実は誤読しているのでは？ということにここでようやく気づく。どうやら縦に折るときは紙の下から何番目の線で折るかが指定されるらしい (今までの実装は上から何番目かで考えていた)。ということでそこを直して提出すると、やっと通る！！！ (2:13:31, 2 penalties)

次にどの問題を優先すべきかを考えてみる。順位表を見ると F が全然解かれていないし、F の解法を説明されても完全な理解ができない (申し訳ない・・・) ので、E をやることに。この判断は大反省です (後述)

E は残り 15 分でそれっぽいものは思いついたので書くも、そこで時間切れ。よくよく考えたら桁落ちを考えていない解法だったためどちらにしろダメでした。

B で割と詰まったけど、ACD の早解きが効いて 39 位で終了。今年もアジア地区に行けそうで嬉しいです。

反省

序盤の立ち回りはアレが正解だったと思う。事実、開始 1 時間時点では 1 桁順位だったらしい (あんまり見てないけど)

問題はその後で、まず B を助けに行くのはおそらく間違っていなかったと思う。ただし助け方にもいろいろあって、今回は既にあるものを直すか新しく書きなおすかがあったと思うけど、結果論にはなるが新しく書きなおしたほうがもしかしたらよかったのかもしれない。新しく書きなおそうとしてみて思ったけど、複数人が「問題文を読む」だけでなく「実際に実装する」と、読むだけでは気づかなかった欠陥を発見できるので、詰まったらとりあえず別の人が書いてみるというのは有効だと思う (ただし 1 から書きなおすほうがタイムロスが大きい場合も当然あるので、既にあるものを直してどうにかなるならそれに越したことはない)。

B を助けるタイミングおよびその速度は、いろいろ改善の余地があるけどあれは仕方ないと思う。自分は他の人のソースコードを見るのがそれほど苦に感じないし、どちらかというとバグ直しが得意な方ではあるけど、あれよりも速くバグ直しができるようになるのかはよくわからない。

チームの指令塔的役割として最大のミスはやはり 4 完後の立ち回りだったと思う。F は解法がある程度見えているにも関わらず、順位表の感触から E に行ってしまって申し訳ない気持ち・・・。これは完全に自分のミスです。F をもう少し詰めていればもう 1 問解けていたのかもしれないです。結果的に F がうまくいってもいかなくても反省すべき。

さいごに

やっぱりチーム戦は奥が深くて楽しいですね。ずっとやっていたいけど今年と来年しかできないの悲しいなあ・・・ (早生まれだし来年があるだけでも幸運なんだけどね)

もっと強くなって横浜でも存分に戦いたいです！！！

*1:去年の様子はこちら → ICPC 国内予選 2017 参加記 - hogecoder

*2:例の数字を暗記していたため

*3:当時のガチ反省記 → ACM-ICPC 2017 Asia Tsukuba Regional Contest 反省記 (コンテスト部分のみ) - hogecoder

競技プログラミングで青になるまでにやったこと

リクエストを受けたので、最近流行りの「○○色になるまでにやったこと」記事を書きたいと思います。

自分の現在の位置について少し話すと、AtCoder 青上位・ Codeforces 青中位・CSAcademy 青中位・ TopCoder 青下位くらいです。全身青いです。近いうちに青卒業できるように頑張っているところです。なので「青色になったので書いている」わけではないのですが、青を目指している人々にとって参考になる記事になっていれば幸いです。

水色 → 青

これは Twitter などでもよく言われていることなのですが、 AtCoder の ABC / ARC の D がコンスタントに通せる ようになると青が見えてくると感じています。問題セットにもよるので一概には言えませんが、 C 問題は呼吸、 D 問題は最低でも 20 分以内には片付けたいところです。なので、コンスタントに通すにはどのような力が必要かを知りたい気持ちになってきます。

適当に過去問を眺めた範囲だと、よく使われているアルゴリズムは以下で紹介するものたちかなあと思っています。

• 二分探索、尺取り法
• 最短路アルゴリズム (ダイクストラ、ベルマンフォード、ワーシャルフロイド)
• 全域木アルゴリズム (プリム、クラスカル)
• 動的計画法
• ゲーム系 (2 人で行うゲームであって、メモ化が可能・もしくは小さいケースを試すと定数時間に帰着できるものが多い)

競技プログラミング関連の書籍で、最初の方に扱うトピックが多いなあと感じる方も多いと思います。実際その通りです。個人差は勿論あると思いますが、 基本的なアルゴリズムをいつも適切に適用できる ということは意外にもそれほど簡単ではなく、この力を十分に養うことができればおそらく青になれるでしょう。

また、上の箇条書きでは挙げていませんが、 ad-hoc な考察が必要になることが多々あります。つまり、特別なアルゴリズムを知っているかどうかの知識問題ではなく、考察問題がよく出るということです。ですので、出題された問題に対して適切な考察をできるだけ早くする能力も必要かなあ、と思っています。

トラブルシューティング的な何か

青になりたいけど、なかなか前に進めない・・・という方は多いと思います。そこでちょっとしたトラブル―シューティング的な何かを書くことにしました。もし「当てはまってるなあ」と思うことがあれば、弱点を克服していきましょう。

実装が簡潔でない

「なんか実装がひどいことになったなあ」となる経験は誰しも一度はしたことがあると思います。 ICPC で出るような重実装の問題とかだとどうしてもそのような実装になってしまい仕方ないみたいなパターンもあるにはあるのですが、たいていは「実装方針が悪い」だけで、本来ならばもっと簡潔に書ける場合が多いです。

ではどのように簡潔に書けるようにするかというと、他の人のソースコードを読みましょう。上位陣は無駄がなく簡潔なコードを書く方ばかりですので、順位表の上のほうのソースコードを意識的に見るようにすると良いと思います。まあ当たり前なんですが変数名が意味不明とか spacing がなんか嫌とか出てくるのはもう仕方ありませんが、見ないよりはマシですしたくさん読んでいるといつかは読みやすいものが見つかるのでたいてい大丈夫です。 (個人的な話をすると、 tourist のコードが結構読みやすいのでコンテストが終わったらこっそり見るようにはしています。)

考察・実装に時間がかかる

「自力で解けたが考察に時間がかかった、実装に時間がかかった」、よくあることですね。自分も毎日これをしていて人生が終了しています。

これをどう解決するかですが、おそらく 数をこなすしかありません。数をこなすとそれだけ考察の引き出しが増えるので、無駄な考察を経由する確率は低くなっていくと思います。実装に関しても同じで、「こういう処理をやりたいときはこう書く！」というものが自分の中で確立されると迷うことなく書けるようになると思います。

ちなみに、自分は青になるまでに ABC を C まで、 ARC を B まで全部埋めました。それから青になってから ABC の D も全部埋めました。効率の良い方ならもっと少ない練習量でも青水準の技能が身につくかもしれません。

考察ができない

そもそも解説に書いてあった考察ができていなかった、というケースも結構あると思います。

これについては、どのような思考プロセスを踏むとそのような考察になるのかをよく考えて、自分のものにする 必要があります。解説を見ながらよくわからないまま通した問題は後で見返した時に十中八九解けなくなっているので、取り組むのであれば時間がかかってもちゃんと考えながらやったほうが良いと思います。

また、「この考察って他にどういう問題で使えるかな？」「問題設定をこう変えても・こう作ってもうまくいくかな？」と、脳内で類題を作ってみる のもオススメです。わからなかった問題で得た知見を他で応用する癖があると、解ける問題の幅が広がると思います。

誤読をする

問題文を読みましょう。 (雑すぎるだろ)

まとめ

いろいろ書きましたが、つまり何が言いたいかというと、青になるために特別なアルゴリズムはあまり必要ないということです。もちろん知っているに越したことはないのですが、それよりも考察力を磨いたり、与えられた問題に対して適切に素早くコードを書く、ある種の瞬発力のほうが求められていると思います。

コレ以上書くと、黄色になりました記事のネタが切れるので、このへんにしておきます。何か聞きたいことがありましたら Twitter でいつでもリプライを飛ばしてください。

Google Code Jam 2018 Round1B: Rounding Error

問題概要

原文 → Google Code Jam

長さ の数列 (この数列の 番目の要素を とする) と、整数 が与えられる。 は より大きく、数列の要素の総和は 未満である。

新たな数列 を作ることを考える (この数列の長さを とし、 番目の要素を とする)。 は長さが 以上であって、 を満たし、 でなければならない。

数列 について、その数列のスコアを と定義する。あり得る数列を全て考慮したときの、スコアの最大値を求めよ。

解説

総和を大きくしたいので、できるだけ切り上げがたくさん起こるようにしたいです。

すでに切り上げが発生する要素に対して票を追加するのは無駄ですので、切り上げが発生していない要素に対して効果的に票を追加していきましょう。少ない追加票数で切り上げが起こる要素を優先したいので、 (現在の票数) が を超えないものの中で最大値をとるような要素に対して票を貪欲に追加することが最善であり、この操作は状態を priority_queue で管理することで可能です。

新たな要素に票をいれることが最善である場合もあることに注意する必要があります (この部分の条件文間違えて 6WA しました・・・)

ソースコード

実装は割と楽です。誤差絶対回避するマンなので round 関数を自前で作るなどしました。

#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int N, L;
struct Elem {
    int value;
    bool operator<(const Elem &e) const {
        int moa = value * 100 % N;
        int mob = e.value * 100 % N;

        if(2 * moa >= N) moa -= N;
        if(2 * mob >= N) mob -= N;
        return moa < mob;
    }
};

int round_user(int A, int B) {
    int div = A / B, mod = A % B;
    if(mod * 2 >= B) div++;
    return div;
}

int main() {
    int T; scanf("%d", &T);
    for(int z=1; z<=T; z++) {
        scanf("%d%d", &N, &L);

        priority_queue<Elem> que;
        int ans = 0, rest = N;
        for(int i=0; i<L; i++) {
            int A; scanf("%d", &A);
            rest -= A;
            que.push(Elem{A});
        }

        while(rest--) {
            Elem cur = que.top(); que.pop();
            // 新たな要素に票をいれたほうが得
            if(cur < Elem{0}) {
                que.push(cur);
                que.push(Elem{1});
            }
            else {
                que.push(Elem{cur.value + 1});
            }
        }

        while(que.size()) {
            int v = que.top().value; que.pop();
            ans += round_user(v * 100, N);
        }
        printf("Case #%d: %d\n", z, ans);
    }
    return 0;
}