yukicoder273でwriterを務めました

今回初めてyukicoderでコンテストを開催できました。testerの皆さん、参加者の皆さん、ありがとうございました。
難易度としては、ABCの点数で 300 - 300 - 400 - 400 - 500 - 600 くらいを想定していました。
全探索、データ構造、DPなど、色々な分野から出題することを意識していました。
丁寧に考察すると典型問題に帰着する、というタイプが多かったかなと思います。
全問題でA君とB君がバトルしていたり、問題名でしりとりしてみたりなど、少し遊び要素も入れてみました。
また機会があれば、次はもっと考察パートが多い問題の作成に挑戦してみたいなと思っています。

A. Array Battle

最近あまり見ない気がする順列全探索です。
最初は得点の最大値を求める問題でしたが、それだと実はソートだけで終わってしまうので、testerさんの提案でこの形になりました。
最大値を取るパターンが何通りか、ということなので、得点を全て配列に入れて最後にソートすればわかりやすいでしょうか。

B. Beyond C

おなじみの二分探索 or しゃくとり法の問題です。ただし桁数が大きいので誤差には注意してください。
例えば C++ では lower_bound という便利な関数が用意されていますが、小数を扱うと WA になることがあると思います。
可能であれば全て整数で処理する方が良いです。今回も問題文の通り、積が C を超えないという形で二分探索すれば大丈夫です。

C. Cigarette Distribution

数学的な考察が必要になるパズルのような問題です。B君がどう行動するかがわかれば解法が見えてくると思います。
和が一定の時に積を最大にするにはなるべく均等に割り振るのが良い、というのはたまに出てくるような気がします。
(ちなみに最初はアメの予定だったんですが、AtCoder に既に Candy Distribution という問題があったのでタバコに変更することに)

D. Display Elements

座標圧縮 + Fenwick tree の典型問題です。
注意点として、A君とB君の持っている数字全ての大小関係が必要なので、両方の数列をまとめて座標圧縮する必要があります。
A君が出すべき順番は直感通りかとは思いますが、証明も考えてみてください。(解説に書きました)

E. Extra Fee

最短距離以外にも情報を持つ、いわゆる拡張ダイクストラ法を用いる問題です。
ダイクストラ法はDPの一種だと考えれば、一般のDPと同じように情報を増やすことで実装できます。
とはいえ慣れていないと実装には結構手こずるかもしれません。
問題が完成した後にtesterさんが発見してくれたのですが、実は過去にかなり似ている問題があったようです。(yukicoder No.807)

F. Flip Game

巡回セールスマン問題 (TSP) の応用問題です。
TSPでは、各頂点について既に訪れたか否かの情報を二進数で管理する、いわゆる bitDP による実装が有名です。
今回は各マスについて三通りの状態があるので、三進数で管理すればよいことになります。
(余談ですが、つい最近Twitterで 3^N のDPの話をちらほら見かけて、偶然とはいえちょっとびっくりしてしまいました)

AtCoder青コーダーになりました

はじめまして、platinumと申します。
少し時間が空いてしまいましたが、10/10のHHKBコンテストで青コーダーになることができました。
今まで色変記事というものを書いたことはなかったのですが、皆さんの記事に刺激を受けて私も書いてみたいなと思いました。

簡単な自己紹介

早稲田大学で大学院生をしています。昨年の12月頃から競技プログラミングの世界に入り、AtCoderを始めました。
もともと独学でC++をある程度学習していたので、競プロでもC++を使っています。
普段は週6日、一日の半分以上を研究室で過ごしているので、あまり精進に時間をかけられていません。
ただ今年の4~6月頃は在宅研究をしていたので、そこでできた時間はかなり精進にあてました。今もその頃の精進に支えられている気がします。
ということで、皆さんとは少し違った内容になるかもしれませんが、特に「なかなか精進の時間が取れない！」という方に役立つような記事になっていればうれしいです。

精進について

青になるまでの精進記録はこちらです。(正確には青になってから少し経っています)

難易度別AC数

精進グラフ

AtCoderでの総AC数は427です。難易度が高い問題はあまり解けていません。黄diff以上の問題が解けなくても青diffに太刀打ちできれば十分青になれると思います。
他にはCodeforcesにたまに参加したり、yukicoderで活動したりしています。
まとまった時間が確保できていないこともあって、AC数や精進グラフの値は小さめかと思います。以下では具体的にどんなことをしていたのか書いていきます。

1. ABCの過去問を埋めていく

一番時間をかけているのはABCの過去問演習だと思います。最近はARCの頻度がかなり上がっていますが今まではABCが圧倒的に多かったので、傾向をつかむためにもABCの過去問ばかり解いていました。
本当は難易度をあまり気にせずに色々な問題に触れたいですがそこまで時間を取れないので、AtCoder Problemsで難易度を見て問題を選んでいます。今のレートとだいたい同じ～少し上くらいの問題を選んで、空き時間に少しずつ考察を進めたりしていました。少し難しめの問題を一問頭に入れておいて、移動時間で考えてみることもあります。
どうしてもわからない場合は解説を見ますが、それまでの考察とかけ離れていたりとか、理解できない部分があったりなどした場合はそのまま放置することが多いです。そういう問題はACせずにとっておいて、もう少し実力がついたらまた戻ってくればいいかなと思っています。

2. バーチャルコンテストに参加する

在宅研究の期間に、AtCoder Problemsで開催されているバーチャルコンテストに参加していました。もちろん個人的に過去問を解いてもいいのですが、皆で一緒に解いて終わったらTwitterで盛り上がればモチベーションも上がるのでおすすめです。
最近は全然チェックできていませんが、当時はあさかつ、よるかつ/くじかつというものがあり、特に夜の方はほぼ毎日参加していたと思います。時間を測って解くので本番での動きを確認できますし、速く正確にコードを書く練習として効果抜群です。

3. 作問をしてみる

実は自分で問題を作ってみることも実力向上に大いに役立ちます。例えば「このアルゴリズムやデータ構造を使った問題を作りたい」と思ったら、必然的にそのアルゴリズムやデータ構造について考察を重ねますから理解が深まります。作問を継続していけば、問題を作る側の心理もある程度わかってくるかもしれません。
自信が持てる問題ができたら、yukicoderに掲載してみるのも良いと思います。この時にtesterから指摘を受けることもあり、それもまた勉強になります。

これまでの学習について

上に書いたようにABCの過去問を中心に解いていたので、ABCにあまり登場しないアルゴリズムやデータ構造には弱かったりします。最近AtCoder Libraryがリリースされたのでいい機会だと思って勉強を始めましたが、それまでは
・セグ木/遅延セグ木は何ができるかは知っているがほとんど使ったことがない
・畳み込みは聞いたことはあるが中身は全然理解できていない
・最大流/最小費用流、強連結成分分解は名前しか知らない
・Two SATは初めて聞いた
くらいのレベルでした。正直青コーダーになった今もこれらに関してはあまり理解が進んでいません......。
これらの知識がなくてもABCでは十分に戦えると思います。ABCで頻出のアルゴリズムやデータ構造、典型問題などの精度を高めれば、あまり大きく崩れることはないと思います。継続して参加していればきっとたまに相性の良い回が訪れて、そこでレートが跳ね上がってくれるかもしれません。

最後に一番言いたいこと

あまり精進の時間が取れない中でも続けて来られたのは、ここまで切磋琢磨してきた仲間がいたこと、そしてコンテスト自体を楽しんでいたことが大きいです。Twitterで絡んでくれる皆さん、ありがとうございます。
レートが上がってくるとやはりどうしても本番で緊張してしまい、文字通り本来のパフォーマンスが出せないこともあると思います。ただそういう時こそ初心にかえってコンテスト自体を楽しんで、レートが一時的に下がっても実力がつけば長い目で見ればまた上がっていくだろう、くらいの気楽さで続けてきました。結果的にはそれが良かったのかなと思います。
これからはさらに厳しい道のりになると思いますが、この精神だけは忘れずに自分のペースで続けていこうと思っています。
長くなりましたが、ここまで読んでくださり本当にありがとうございました。