ながめも

競技プログラミングについて

AtCoderで青色になるまでにやったこと

AtCoder Beginner Contest 197(Sponsored by Panasonic)にて、AtCoder青色になりました。

競技プログラミング界隈の風習にならい、色変記事を書きます。

naga on Twitter: "初参加から2年半、やっと青コーダーになりました!!!!!!!!… "

f:id:coonevo:20210328014259p:plain

水色の記事はこちら

coonevo.hatenablog.com

自己紹介

21卒の大学院生で、来る4月からエンジニア職として働き始めます。専攻は生物で、研究で必要になり勉強していたところプログラミング自体にハマって今に至る、という感じです。

最近はマラソン型コンテストにお熱で、HTTF2021予選で64位になったり、ハル研究所プログラミングコンテストで18位入賞したり、AHC001で108位になったりしました。トップには全く敵わないものの、個人的には楽しんで取り組んでいます。

精進

AtCoder Problemsのスクショがわかりやすい気がします。 令和ABC-Eは割と埋めていて、Fに手がついていません。緑diffまでは埋まっていますが、水diffのめんどくさそうなのは放置しています。青diffもたまに解説ACする、という気まぐれ精進が見て取れますね。 2020年後期からほとんど精進ができていないのは、マラソンにハマり始めたり修論で忙しかったりしたためです。修論の追い込み期間はコンテストに出るのをやめていました。

それでもレートが少しずつではあるものの伸びているのは、コンテストにはかかさず参加するという習慣を維持できたのが大きかったのではないかと思っています。コンテストで結果を出す力は、コンテスト(orバチャ)でしか養われないと思うので。

f:id:coonevo:20210328002212p:plain f:id:coonevo:20210328001950p:plain f:id:coonevo:20210328001945p:plain f:id:coonevo:20210328001940p:plain

コンテスト

上述のように、AtCoderのコンテストにはほとんどかかさず参加していました。土曜の夜は何よりもコンテストを優先していました。その結果、コンテスト参加回数は122回(全体でランキングで119位)になっていました。何も考えずにとりあえずコンテストに参加するのは、モチベーションを切らさない意味でも大切だったと思います。

f:id:coonevo:20210328003522p:plain

勉強していたこと

高校数学も競プロに関係するような範囲は苦手で、大学数学もほとんど手がついていなかったため、競プロに必要なことは競プロで学んでいます。特に、場合の数確率、整数の範囲は、段々成長しているのかなと思っています。場合の数、整数ともにマスターオブシリーズがおすすめです。苦手で困っている人は、最初の数ページだけでも読んでみると捉え方が変わるんじゃないかと思います。

勉強したことで好きな考え方は、決めうち二分探索、拡張ダイクストラ(グラフを拡張したダイクストラ)、主客転倒です。最近は形式的べき級数の考え方に魅了されていましたが、役に立てるほど身についていないので、いつかマスターしたいです。

  • DP

    • LIS
    • 耳DP
    • 数え上げDP
    • 木DP
    • 全方位木DP
  • 二分探索

    • 決めうち二分探索
    • 単調性を見つけるのがうまくなった
  • 貪欲

    • 区間スケジューリング問題
    • 解法の一部に含まれる貪欲要素に気を配れるようになった(DPのときとか)
  • 数え上げ

    • 主客転倒
    • 包除原理
    • 期待値の線形性(というかだいたい数え上げだと思って解いてる)
    • マスターオブ場合の数を読んだのがよかった
  • データ構造

    • BIT
    • セグ木
    • 遅延伝播セグ木
  • 整数関連

  • 文字列

    • Suffix Array(使ったことない)
    • Z-algorithm(使ったことない)
    • manachar(使ったことない)
  • ゲーム

    • Nim(XORが大事)
    • 真似するやつ
    • 過半数が大事
    • min-max法?
  • グラフ

  • フロー

    • 最大流
    • 最小費用流(使ったことない)
    • 二部グラフのマッチング(使ったことない)
  • その他テクニック

    • 座標圧縮
    • 鳩の巣原理
    • 拡張ダイクストラ
    • 真ん中を固定する
    • 2変数を1変数に変えるやつ
    • 計算量が調和級数になるやつ
    • 操作回数が実は多くない
    • 半分全列挙
    • マンハッタン距離は45°回転
    • 添字ガチャ
    • set, multisetガチャガチャ

紙に考察を書くこと

コンテスト中、紙にどの程度メモしますか?

touristの精進配信をみたときに、彼らが紙には何もメモせず、画面を睨みつけながら考察しているのが印象的でした。

私は、競プロを始めたばかりの頃、メモをしないで考察するということが理解できませんでした。暗算も苦手、すべて書かないと理解した気にならない、という癖があったのではないかと思います。レッドコーダーは、簡単な問題は紙に書かないということを知って、驚いたと同時に、自分もできるのかな?と挑戦しました。最初は確かに苦しいのですが、段々と頭の中だけで動かせるものが増えていきました。今となっては、メモをすると無駄な考察が増えるばかりだなと思うことも増えました。

この紙に書かずに考察する能力は、早解きに必須だと思いますが、精進の量を増やす上でも役に立ちました。頭の中に問題をセットして、歩きながら解くということも可能になり、いつでも精進ができるようになったことで、問題を解かなければならないというプレッシャーも減りました。

2x105の数列を頭に浮かべながら生活するのも悪くないです。

レーティングを気にすること

レーティングを気にする人は多いと思います。色変記事みたいなのがあるように、400刻みには何の意味もないのに色を気にする人は多いです。

結論からいうと、レーティングは気にしても上がらないので、考えないようにしていました。

こう考えるきっかけになったのは、コドフォでした。コドフォはAtCoderに比べるとレートの変動が激しいため、レートは溶けるときは溶けるという、当たり前のことを教えてくれました。

レートが溶けるのを気にしているとコンテスト中問題以外にメモリを奪われるので、無視するのが賢明だと最近は思い込んでいます。実際ここ数ヶ月はレートの浮き沈みが激しいですが、実力が上がればいつかは戻るので、気にしていません。今後も水色に落ちたりするとは思いますが、長い目で見て実力が向上していれば問題ないという気持ちでいます。

ラソンの影響

ラソンにハマってから、実装力が格段に上がりました。マラソンは令和ABC-B,Cレベルの問題を自作して解くという流れで進むので、アルゴ型にもいい影響があったのではないかと思っています。計算量を意識して作問しなければならないので、アルゴの問題でも受け身にならずに考察を進める力がついたような気もします。何より、アルゴの競争に疲れていたとき、マラソンで自分との戦いに挑戦した結果、悩みが馬鹿らしいものだということに気づけました。みんなもやろう、マラソン。楽しいよ。

最後に

最後まで読んでいただきありがとうございました。競プロで必要になったことはその場で学び直してなんとか這い上がった人間なので、そういう悩みを抱えている人に少しでも役に立っていたらいいなと思います。

まだ伸び代はあると思っているので、黄色になるまでは続けたいと思っています。黄色になりたい理由は、マラソンでできることを増やしたい、ただそれだけです。

ラソンに興味を持った人は、以下の記事などもどうぞ。最近は入門記事も増えているので、気軽に参加してみましょう!

coonevo.hatenablog.com

マラソンマッチで気をつけるべきこと

今までHTTF、ハル研プロコン、AHC、などのマラソン競技プログラミングコンテストに参加してきました。初参加から一年以上が経ったでしょうか。個人的には普段のアルゴと呼ばれる分野のコンテストよりマラソンの方が向いている(相対的な順位がよい)と感じており、比較的力を入れてきました。

本記事では、マラソンに取り組むときに考えていることを自分の振り返りも兼ねてまとめます。

短期型では制限時間以内に実装できる範囲の中で得点の期待値が高そうなものを選ぶことが重要になりますが、今回は長期型、2週間ほどのコンテストにおける戦略にフォーカスします。

有名問題との類似性

まず問題を読むわけですが、その問題が、有名問題と似ているか考えます。例えばハル研プロコンでは、経路最適化問題が出題されましたが、上位陣の解法をみると所謂TSPの知見が多く利用されています。AHC001では、長方形の詰め込み最適化を求められましたが、これも長方形詰め込み問題と呼ばれる情報科学で有名な問題と似ていることがわかります。もちろんそのままの形式で出ることはあり得ませんが、知見が活きる可能性が高いです。そもそも出題者側には情報科学のバックグラウンドがあることは容易に想像できるため、教科書的な有名問題をもじったようなものは出題されやすいと思います。某講演でも、コンテスト期間中に論文を読みながら勉強するという話が出ていましたが、そのくらい巨人の肩に乗ることは重要だということだと思います。私自身学生時代の専門は生物学で、知見が不足している部分はありますが、情報科学に対するアンテナも常に張っておくべきだと感じています。

最も簡単な解

次に、最も簡単な解を書きます。経路最適化問題なら、直線で結ぶだけ、長方形配置なら、正方形を置くだけなど、とにかく正の得点が得られそうなものを書きます。この点数から上げていきましょう。ここで最も意識すべきことは、コードの再利用性と、拡張性です。先日の技育祭でchokudaiさんがマラソン実装の実演をしていましたが、そこでも強調されていました。最も簡単な解を得るからと言って、コードを雑に書くとすぐに後悔します。例えば長方形の配置をするなら、端の2点を入れたらセットできるメソッドを作ったり、長方形を管理する構造体も持つべきでしょう。こうすることで、余計な思考リソースを取られないようになります。向き合っている問題の中で、最も基本的な構造は何か考え、それにアクセスする回数が多そうなら、なるべくアクセスしやすいように書くのがコツです。

テキトーに書くと、改善する気がなくなります。触りにくいと、触らなくなります。最後には、触りたくても触れなくなります。私も何度も失敗して学びました。綺麗に書くと、愛着が湧きます。改善したくなります。長期型マラソンで最も大切なのはやめないことです。PDCAを高速に回すことです。2週間付き合っていくコードなので、スタートから未来を見据えて書いていきましょう。

単純な貪欲

最も基本的な解が構成できたら、山登り法や焼きなまし法を考える前に、単純な貪欲を考えます。貪欲が最も重要だと言っても過言ではないです。貪欲が弱いなら、後述する山登り法や焼きなましがうまくいくとは考えにくいです。マラソンマッチは制限時間内に全てのパターンを列挙できない問題から良さそうな一部の状態を探し当てる宝探しなのですから、闇雲に探しても見つかるわけがありません。数え上げお姉さんの二の舞になります。ある程度よいと思われるところに降りてから、探し始めましょう。

ハル研プロコンならダイクストラ法で距離を算出したり、AHC001なら目標面積目一杯、ギリギリまで広げるアルゴリズムを考えます。これだけでも十分よさそうな解が得られていそうなことに気づくでしょう。ただ、決定的アルゴリズムでは探しきれていない状態がたくさんあります。そこで、山登り法の出番です。

山登り法

山登り法は、状態にランダムな変異を入れて良くなったらそちらに進む方法です。ランダムな変異の取り方も無限にあるので、考えます。考える前にテキトーなところで手を打ってとりあえず実装するのも手です。それをベンチマークにして改善していきましょう。よく、ここで選んだ解法に固執してマラソンマッチ戦略の局所最適解に落ちてしまう人がいますが(私のことです)、無限にアイデアを試しても怒られることはないわけですから、遠慮せず解を壊しましょう。間違ってもここでパラメータガチャに走ってはいけません。パラメータガチャをするのは最後でも間に合います。稀にパラメータガチャで結果がめちゃくちゃ変わることもあるので、ある程度試す価値はありますが、固執すると時間だけが過ぎていきます。気をつけましょう。

山登り法の問題点は、局所最適解に落ちやすいことです。別にそこまでよくないのに居心地がいいから穴から出てきてくれなくなります。もっといい世界があるのに。まるでマラソン開始2日目でパラメータガチャに走る私のようです。局所最適解に落ちているかどうか判断する方法としては、実行時間を長くして、さらに解が改善するかどうかを見るというのがあります。5秒では見つからないけど、500秒で見つかるよりよい解があるなら、局所最適解に落ちてる可能性があります。救ってあげるにはどうしたらいいでしょうか。私はよく、突然変異を大きくしています。解の一部を壊して、局所最適解から逃してあげましょう。山登りなので、いい状態が見つかればそちらに向かってくれます。どういう変異を追加するべきかは、ビジュアライザをよく観察して考えます。「ここで改善できそうなのにいつまでも動かない」と思ったら改善のチャンスです。

その他

焼きなましは、局所最適解に落ちにくくなります、たぶん。焼きなましでスコアを伸ばしたことがないので言及を避けます。

以上、反省会でした。 これはあくまで個人的なメモなので、間違っていると思われる記述があったら教えていただきたいです。長期型マラソンでの注意点を意識し、楽しいマラソンライフを!

AtCoder Heuristic Contest 001 AHC001に参加しました

AHC001に参加しました。

結果は、システムテスト前最終118位、489億6千万点でした。簡単にですが、採用したアルゴリズムに関して記します。

アルゴリズム

  1. 各企業の初期位置に1x1の正方形を割り当てる(初期化)
  2. 各企業に長方形を割り当てる。(貪欲)
  3. ランダムに領域を移動し、ランダム要素を追加した貪欲を加え、解がよくなるなら採用する(山登り)
  4. ランダムの中である確率で、1x1の正方形にリセットする摂動を入れる(kick)

初期化

1x1の正方形を割り当てます

貪欲な長方形

まず、x, yともに両方向に同じ距離ずつ広げる正方形を割り当て、その後x, yそれぞれに関して乱数を用いてランダムに伸ばす方向を設定し割り当てる。面積は、目標を超えないように、また他の長方形と交差しないように貪欲に割り当てる。

ランダム山登り

ランダムに長方形を選び、3 ~ 200だけ移動させる。方向もランダム。これを20回繰り返す。

kick

20%の確率で、長方形をリセットする。状態を壊して局所解に落ちないようにするため。

パラメータ

パラメータは勘で選んだ。本当は検証するべき。いくつか試して、解の上昇が最もよさそうなのを採用した。

実装

貪欲の実装は、二分探索で行ったが、交差判定でO(N)かかるので、全体でO(NlogH)かかる。logがついて遅い。高速化するには、Dynamic AABB Treeというものを用いるといいらしいです。

何が最も改善に効いたか

  • 貪欲時にランダム要素を含ませたこと
  • kick(長方形リセット)

貪欲は決定的なアルゴリズムになってしまいがちなので、その中にもランダム要素を生やすことで、局所解から脱出しやすくなると思います。また、kickも同様で、長方形の辺の比が偏ってる場合他を邪魔する可能性があるので、高確率でリセットを行うようにしました。

改善したい点

  • Dynamic AABB Treeで交差判定を高速化する
  • パラメータを勘で設定しない

コード

提出へのリンク

2015年度東大理系数学第4問(3) 解説

(1), (2)は他の方の解説に譲るとして、(3)を考えます。

(2)までの結果をまとめると、


p_1 = 1,  p_2 = 1\\
p_{n+1} + p_{n-1} = 3p_{n} \\

ということでした。つまり、ある項はその前後の項を足して3で割った数であるということです。

これと、フィボナッチ数列の奇数番目が等しいことを証明せよというのが今回の問題です。

簡単に言えば、以下の図が書ければ終わりです。

f:id:coonevo:20210305041237j:plain

あとはこの図を用いながら帰納法で示せるかと思います。

多くの解説が数式でゴリ押していますが、漸化式でわざわざ n-1を使っているあたり、問題作成者はある項とその前後の関係が〜という思想があったんだろうと感じました。

(実は本番に解いているのですが、(1)の証明ができなくて(2)のみを解いて終わりにした記憶があります。。。)

HHKB プログラミングコンテスト 2020 D - Squares

D - Squares

問題へのリンク

解説

  • X(答え)

重ならないという現象の数え上げは難しいので、重なる(X1)を数えて全体から引く X = X0 - X1 X0 = (N-A+1)2 * (N-B+1)2

  • X1(重なる)

重なるという現象は、AとBの満たす区間がxでもyでも重なるときで対称性から、 xで重なるときの場合の数をX2とすれば、 X1 = X22 である

  • X2(一次元の重なり)

これは、重ならない(X3)の方が扱いやすいので、全体(X2_0)から引くことにする X2 = X2_0 - X3 X2_0 = (N-A+1) * (N-B+1) - X3(一次元で重ならない)

Aが左にあるか右にあるかで場合わけした場合、それらの場合の数は全く同じになるので Aが左で固定して考え、後で2倍する Aが左のとき、Aの場所が決定すれば、Bの場合の数は決まる。 1 + 2 + ... + N-A-B+1 が答えである。 これは、(N-A-B+1) * (N-A-B+2) / 2なので、X3はこの2倍で X3 = (N-A-B+1) * (N-A-B+2)

実装

void solve(){
    ll N, A, B;
    cin >> N >> A >> B;
    if(N < A + B){
        cout << 0 << endl;
        return;
    }
    mint X3 = mint(N-A-B+1) * mint(N-A-B+2);
    mint X2_0 = mint(N-A+1) * mint(N-B+1);
    mint X2 = X2_0 - X3;
    mint X1 = X2 * X2;
    mint X0 = mint(N-A+1) * mint(N-A+1) * mint(N-B+1) * mint(N-B+1);
    mint X = X0 - X1;
    cout << X << endl;
}

パナソニックプログラミングコンテスト(AtCoder Beginner Contest 186)E - Throne

E - Throne

問題へのリンク

 S + m \times K \equiv 0 \pmod Nを満たす最小の整数 mを求めよ。

拡張ユークリッドの互除法による逆元計算

まず、与式を m \equiv -S \times K^{-1} \pmod Nと変形することで K^{-1} \pmod Nが求まれば、問題を解くことができるとわかります。

ここで、 \pmod Nにおける Kの逆元の存在条件は、 N Kが互いに素であることです。

NとKが互いに素のとき

 N Kが互いに素のとき、 Kの逆元 K^{-1} \pmod Nは、拡張ユークリッドの互除法(extGCD)によって求まります。

拡張ユークリッドの互除法による逆元の求め方

 aK + bN = 1を満たす整数 (a, b)をextGCDによって求め、この式を \pmod Nの式に変形すると、 aK = 1 \pmod Nとなることから、 K^{-1} = aつまり、aが Kの逆元になっています。

NとKが互いに素でないとき

 N Kが互いに素ではない場合、 Kの逆元 K^{-1} \pmod Nは存在しません。では、今回の問題を解くことはできないのでしょうか。サンプルをみればわかる通り、そういうわけではありません。

 N Kが互いに素でないなら、互いに素にしたくなります。 N Kを、 g = gcd(N, K)で割った結果をそれぞれ N^{\prime}, K^{\prime}とおくと、 N^{\prime} K^{\prime}は互いに素です。

これら N^{\prime} K^{\prime}をextGCDにかけることで、 K^{\prime -1} \pmod {N^{\prime}}を求めることができました。

与式に戻り N,K,Sをそれぞれ N^{\prime}, K^{\prime}, \frac{S}{g}に置き換え、

 \frac{S}{g} + m \times K^{\prime} \equiv 0 \pmod {N^{\prime}}

とすれば、 \frac{S}{g}が整数、すなわち S gの倍数である場合に、先ほどextGCDによって求めた K^{\prime -1} \pmod {N^{\prime}}を用いて mを求めることができます。

 S gの倍数ではない場合、解はありません。

実装

提出へのリンク

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x2, y2;
    long long d = extGCD(b, a%b, x2, y2);
    x = y2;
    y = x2 - (a / b) * y2;
    return d;
}
long long mod_inv(long long a, long long m){
    ll x, y;
    ll d = extGCD(a, m, x, y);
    if(d != 1)return -1;
    if(x < 0)x += m; 
    return x;
}
long long safe_mod(long long a, long long m){
    return (a%m+m)%m;
}
void solve(){
    ll N, S, K;
    cin >> N >> S >> K;
    ll g = gcd(N, K);
    ll inv = mod_inv(K/g, N/g);
    if(S % g != 0){
        cout << -1 << endl;
    }
    else{
        ll ans = S/g * (-inv);
        ans = safe_mod(ans, N/g);
        cout << ans << endl;
    }
}

中国剰余定理

 S + m \times K \equiv 0 \pmod N

という式から、以下のような連立合同式を考えます。

{\displaystyle 
\begin{eqnarray}
  \left\{
    \begin{array}{l}
      x \equiv 0 \pmod N \\
     x \equiv S \pmod K
    \end{array}
  \right.
\end{eqnarray}
}

中国剰余定理によって、この連立方程式を解きます。(解がない場合もあります。その場合は、今回は-1を出力して終わりです)。

このとき、 N Kの最小公倍数を lcmとすると、

 x \geq Sの場合、  m = \frac{x-S}{K}

 x \lt Sの場合、  m = \frac{x+lcm-S}{K}

となります。

中国剰余定理で求まる xは、周期 lcmであり、その間に唯一のものであるから、当然今回の解に不適切なものも出てくる( S未満など)ので、その場合は、一個先の解を使えばよい( lcmを足しているのはそのためである)。

実装

提出へのリンク

Codeforces Round #703 (Div. 2) D - Max Median

codeforces.com

問題

You are a given an array 𝑎 of length 𝑛. Find a subarray 𝑎[𝑙..𝑟] with length at least 𝑘 with the largest median. Then, output the maximum median you can get.

解説

まず「中央値がxにできるか」という判定問題をO(N)で解くことができれば、決めうち二分探索によってこの問題をO(NlogN)で解くことができます。

ここで、判定する条件を緩和し、「中央値をx以上にできるか」とします。数列aの値をx以上である場合、1, そうでない場合-1とすれば、数列の中央値がx以上になるかは、その数列の総和で判定することができるとわかります。具体的には、総和が0より大きいなら、中央値がx以上になります。

判定条件の緩和によって、数列が決まったとき「中央値をx以上にできるか」という判定問題をO(N)で解くことができました。一方で、今回の問題では長さK以上の場合を聞かれているので少し困ります。

実は今回は、累積和による連続する数列の値の和を求める計算を考えれば、取る数列の右端を決めたとき、その右端からK以上離れた累積和の最小値が和を最大化するので、その情報を前から更新しながら持てばよいとわかります。

以上のような方針で、この問題をO(NlogN)で解くことができました。

中央値の判定問題は、以上のような「値の二値化」+「二分探索における判定条件の緩和」が絡む場合があるようです。割と上位陣が高速に説いていたので典型ということなのでしょう。

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i,N)cin >> a[i];

    auto check = [&](int x) -> bool{
        vector<int> v(N);
        rep(i,N){
            v[i] = (a[i] >= x) ? 1: -1;
        }
        vector<int> c(N+1, 0);
        rep(i,N){
            c[i+1] = c[i] + v[i];
        }
        int minn = 0;
        for(int i = K; i <= N; i++){
            chmin(minn, c[i-K]);
            if(c[i]-minn > 0)return true;
        }
        return false;
    };

    int ok = 0, ng = *max_element(all(a)) + 1;
    while(ng - ok > 1){
        int mid = (ok + ng) / 2;
        (check(mid) ? ok: ng) = mid;
    }
    cout << ok << endl;
}