hogecoder

tsutaj 競技プログラミングの記録

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

目標とか

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

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

水色 → 青

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

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

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

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

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

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

実装が簡潔でない

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

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

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

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

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

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

考察ができない

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

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

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

誤読をする

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

まとめ

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

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

Google Code Jam 2018 Round1B: Rounding Error

その他コンテスト

問題概要

原文 → Google Code Jam

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

新たな数列 A を作ることを考える (この数列の長さを M とし、 i 番目の要素を a_i とする)。 A は長さが L 以上であって、 a_i \geq c_i (1 \leq i \leq L) を満たし、 \sum_{i=1}^{M} a_i = N でなければならない。

数列 A について、その数列のスコアを P = \sum_{i=1}^{M} \textrm{round} \left( \frac{a_i \times 100}{N} \right) と定義する。あり得る数列を全て考慮したときの、スコアの最大値を求めよ。

解説

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

すでに切り上げが発生する要素に対して票を追加するのは無駄ですので、切り上げが発生していない要素に対して効果的に票を追加していきましょう。少ない追加票数で切り上げが起こる要素を優先したいので、 (現在の票数) \times 100 \mod N が \frac{N}{2} を超えないものの中で最大値をとるような要素に対して票を貪欲に追加することが最善であり、この操作は状態を 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;
}

RUPC 2018 参加記

勉強会参加記

立命館大学競技プログラミング合宿 2018 (通称 RUPC 2018) に参加しました。去年に引き続き 2 回目の参加です。いやあ濃密な三日間だったなあ・・・

以下時系列順に振り返るいつもの

Day 0 (前日)

飛行機が遅延しまくる。11:10 離陸予定の飛行機が 15 時に飛んだ (は？) おかげで観光できず。大幅遅延は事前 (搭乗前日) に知らされていたとはいえ、残念な気持ちになる。

宿についてすぐに ARC があったので参加したけど構築が一生解けなくて人生終了した。こう振り返るとなんか虚無イベントしか起こってないような・・・。

Day 1

深夜バス組が南草津でボドゲを朝からやるらしいので、京都に普通に泊まってた自分も早起きして参加した。CODE THANKS FESTIVAL 前のボドゲ会にも参加してた人々が多くて、再会できてよかった。ギャンブラーギャンブルをやるとらてあ氏が無限に勝つのですごいと思いました (小並感)

コンテスト

立命館大学に移動して、コンテストのチームを乱択する。自分はうくさん ( @ukuku09 ) と、 wheson さん ( @wheson ) と組むことになりました。

最初の方針としては wheson さんが A を、自分が B を、うくさんが C を読むことになっていて、B を読んだのですが、国語と数学が壊滅的なため題意が一生わからなかった (後でうくさんに投げてしまった)。自分が題意理解フェーズしている間に wheson さんが A を通してくれた。

C はうくさんから問題文を聞いて map に入れるだけ解法はすぐ思い浮かんで、最悪ケースで普通に二乗オーダーになるのでやばそうだなあと思ったけど、投げたら通ってウケた。長さ最大で回文みたいになっている数列が来たらやばそうではある。そしていまだに B がわからない。

wheson さんとうくさんが B の解読に努めて、自分はとりあえず後ろを読むことに。D は区間 DP みたいな気持ちになるけどわからない。なんか E は全部張るだけでよさそうなので書いたら通る (この問題、最初有向グラフだと思っていた・・・)

F は若干面倒な桁 DP っぽいのでとりあえず飛ばす。G は最初見たとき並列二分探索かと思ったけどそれすらいらなくて、単にクエリを時系列順にソートして状態を更新していけばよい。セグ木でいい感じに書けそうだったので書く。若干バグったけど AC。

ここで全員で B と格闘するもまだ通らない。つらすぎでは？ (ここで 1 時間弱 AC がない虚無を過ごす)

F に戻ってきた。パターンが含まれていない文字列を数えて全体から引くと良さそうだと気づく。早速書くけどコーナーに引っかかって 1WA しつつ AC (自分はパターンの何文字目まで一致したかを状態として持ったけど、下 3 桁持ったほうがコーナー気にする必要なくて圧倒的に楽ですね)

あと F を書いてる途中で D の解法が浮かんだ。区画 merge の順番が関係なくて、最後にどうなっているかだけ気にすれば良いため、普通に左から DP すればよい、ということをうくさんに伝えて書いてもらって AC。

そしてさらに B がやっと解決する。出力の順番罠やんけ！

結果的に全完した (奇跡) 後ろの問題全部解けたので気持ちよかった。

懇親会

ひとがおおくてすごいなあと思った。去年よりも 30 人増えてますもんね。

去年は会話した人を記事に列挙できるくらいの人数だったけどもう列挙できないくらいお話しました。たのしかったです。自分とお話してくれたすべてのひとにありがとう。

Day2

なんか会場着いたらチノちゃんとティッピー載せた成人男性がいるけど

コンテスト

この日は事前にチームが決まっていて、 うしさん ( @ei1333 ) と treeone さん ( @treeone79 ) と組みました。

コンテスト開始 1 時間前が集合時間なんですが華麗に遅刻 (30 分遅れ) (ごめん)

うしさんはコンテスト開始 30 秒前くらいに到着、パソコンを開いたら FA が奪われていたらしい。さすがのうしさんもパソコンの起動時間には勝てなかったらしい。

B 問題担当ワイ、WA を出す (は？) もなんとか AC。A 問題と C 問題もチームメイトによって気が付かない間に片付けられていく。

D 見た一同、これ不可能では？？となる。あとで気づいてたんですが問題解釈間違ってたね (かなしいね)

F はうしプロと treeone プロが通してくれた。 I は制約的に bit DP で、点集合を全て覆うような円の最小半径が欲しい気持ちになるので適当にググったら tubo さんの記事を見つける。前でチーム戦をしている tubo さんに感謝しつつ貼ってメモ化再帰を書いたら TLE する (えぇ・・・) いやオーダー的には大丈夫だよなあと思ってループで書き直したら AC した。メモ化再帰が世界一苦手。

H はうしさんが「あぁこれは Suffix Array でいけそうだなぁ破滅だなぁ」とかなんとか言いながら通してた。プロすぎる。このへんからうしさんが床コーディングをはじめる。

G は一般マッチングが欲しい気持ちになって、これまたググったら出てきたのでうしさんが貼って提出。 N \leq 800 の O(N^{3}) だけど難なく通って草。

相変わらず D は破滅なので J とか E とかをやるも破滅する。後半は全員で破滅虚無人生終了コーディングしてた。つらい。

あとで気づいたけど E の悪魔的ケース気づいてなかったね。

懇親会

焼き肉！！！なんかやたら火力が強くて、定数倍高速化を極めた焼き肉とか言ってた。

食べて飲んだあとは近くの温泉に入って疲れを癒していました。やざてんさんのかばん無事でよかった。

Day 3

コンテスト

泣く子も黙る †admin† でした。コンテスト開始 2 時間前から会場入りしていたんですが割とちょうどよい感じで準備が終わって、チーム決めたり解説編集したりしてました。

割と典型を集めたセットになっていて、全完はでるだろうとは思っていたけど、おわってみれば 19 チームが全完していて、これは想像していたよりもはるかに多い数でした。次回はもっと難易度上げるか！ｗ 皆さん解いてくれてありがとうございました。

その後

その後は立命のキャンパス内にある超いい感じの食堂？に行ったり、南草津駅で虚無をしたり、再びカラオケ屋でボドゲをしたり、某 treeone の通知欄を破壊したり、京都でご飯を食べたり、某 treeone に通知欄を破壊されたりしました。南草津着いた後はずっと olphe さん・TIke さん・フェリンさんと遊んでました。正直超たのしかったです、ありがとうございました。

まとめ

いや立命合宿は楽しいかな〜やっぱｗ チーム戦も楽しめるし作問もできるし (聞いてないｗ)

来年もまた参加したいです・・・！！！