ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

Codeforces Round #510 参加記録

Dashboard - Codeforces Round #510 (Div. 2) - Codeforces

結果は4完…ですが、CとDが遅くて誤答ペナルティもかなり付いてるので順位は低めです(配点はA~Dで500-1000-1500-2000です)

f:id:betrue12:20180917214859p:plain

A~Dを振り返ります。

A. Benches

Problem - A - Codeforces

問題概要

 n 個の整数  a_{1}, ..., a_{n} が与えられる。この数列に「いずれかの要素の値を1増やす」操作を  m 回行い、操作後の  a_{i} の最大値を  k とする。

 k の取りうる値の最小値と最大値を求めよ。

制約

  •  1 \le n \le 100
  •  1 \le m \le 10000
  •  1 \le a_{i} \le 100

解法

最大値のほうが簡単です。操作前で最も大きな要素に  m を足すだけです。

最小値のほうは、なるべく平坦になるように要素を足していきたいです。ですが、元々の要素の最大値を下回ることはできません。 \lceil\frac{\sum a_{i} + m}{n}\rceil \max a_{i} のうち大きい方が答えです。

ACコード

B. Vitamins

問題概要

 n 個の要素について、そのコスト  c_{i} と、ABC をそれぞれ0個または1個含む文字列  s_{i} が与えられる。

ABC 全ての文字を1つ以上含むように要素をいくつか選ぶ時、その合計コストの最小値を求めよ。

制約

  •  1 \le n \le 1000
  •  1 \le c_{i} \le 100000
  •  s_{i} は1~3文字であり、 ABC をそれぞれ0個または1個含む

解法

私は要素を順に見ていくDPをしました。dp[i][S] を、「  i 番目の要素まで見て、既に取った文字の集合が  S であるときの最小コスト」とします。

 S は3つの要素を取った/取ってないの8通りであり、ABC それぞれをビットで管理すると0~7までの整数で表現できます。新しく要素を取った時の集合の遷移は、ビットのor演算を使って実装することができます。

他の方法もあります。高々8通りしかないパターンに1000個の要素があるため、無駄な要素が大量にあります。含む文字が同じ要素の中では、コストが最小のもの1つだけを考えれば十分です。そうすると高々8個の要素しか残らないので余裕で全探索できます。こっちのほうがスマートですね…

ACコード

C. Array Product

Problem - C - Codeforces

問題概要

長さ  n の数列  a_{1}, ..., a_{n} が与えられる。この数列に以下の操作を行う。

  1. 相異なるインデックス  i, j を選ぶ。  a_{j} a_{i} \times a_{j} で置き換え、 a_{i} を消去する。
  2. この操作は1度だけ行える。インデックス  i を選び、  a_{i} を消去する。

これらの操作を合計  n-1 回行うと要素が1つだけ残る。この要素を最大化するような操作手順を1つ示せ。

制約

  •  2 \le n \le 2\times 10^{5}
  •  -10^{9} \le a_{i} \le 10^{9}

解法

問題文の操作は、結局「0個以上の要素を消去し、残りの要素を全て掛け合わせる」という操作になります。複数の要素を消去する場合は、1の操作で消去したい要素を全て掛け合わせてから、最後に2の操作で消せばよいからです。

ということで、上記の操作で最終的な要素を最も大きくするにはどうすればよいか考えます。

  • 正の要素:残す。
  • 負の要素:偶数個なら積が正になるので残す。奇数個の場合、絶対値が最も小さいものを1つ消し、他を残す。
  • 0の要素:基本的には消す。

これが原則になりますが、このまま実装すると「全部0」や「負数1個+残り全部0」の時に全部消す扱いになってしまうので注意です。これらの場合は単に全部の要素をかけ合わせれば良くて、最後に残る要素の最大値は0です。

ACコード

本番コードがあまりにも汚かったので書き直しました…

D. Petya and Array

Problem - D - Codeforces

問題概要

長さ  n の数列  a_{1}, ..., a_{n} が与えられる。その連続部分列のうち、和が  t より小さくなるものの個数を求めよ。

制約

  •  1 \le n \le 200000
  •  |t| \le 2\times 10^{14}
  •  |a_{i}| \le 10^{9}

※絶対値表記になっている要素は、正・負・0の値を取り得る

解法

全要素が非負だとしゃくとり法が使えたりするのですが、負の要素がある場合はもう少し複雑な処理をしなくてはいけません。

まず、数列の区間和を累積和の差だと考えることがポイントです。 n 個の要素について、最初の0を含めて順次累積和を取ります。これらの累積和は以下のような要素間の仕切りに対応し、 (右の仕切りの値) - (左の仕切りの値) \lt t を満たす2つの仕切りの組が、そのまま条件を満たす区間に対応します。

f:id:betrue12:20180917212120p:plain

ということで、各仕切りについて「自分より左に存在する仕切りで、さきほどの条件を満たすものはいくつあるか?」という問題を考えます。仕切りを順番に見ていきながら数え上げることを考えると、

  • ある点に値を追加する
  • 範囲内の値の総和を求める

を順不同で行えるようなデータ構造、BITを使えば解けそうです。

ただし、今回の問題では累積和として取り得る値が非常に大きくなる可能性があります。この方法では累積和の値をBITのインデックスとして使います。長大なBITを作れればよいのですが、メモリも計算時間も足りません。ということで、座標圧縮を行います。

座標圧縮を行うと、値の種類は高々仕切りの個数である  n+1 種類しかないので、(0始まりであれば)  0, ..., n の範囲に収まります。これならBITを作って、現実的なメモリや時間で計算できそうです。

圧縮を行ってしまうと、「  (右の仕切りの値) - (左の仕切りの値) \lt t を満たす左の仕切りの値はどこまでか?」というのがすぐには分からなくなってしまいます。ですが、この条件を満たす/満たさないの境界は、圧縮前の座標を二分探索することで求めることができます。

f:id:betrue12:20180917214154p:plain

累積和が単調変化にならないようなケースで、区間和がある値以上/以下である区間の数え上げをBITで行う…というのはよく見る問題ですね。習得しておくとかなり役立つと思います。

ACコード

さいごに

今回はC問題でハマって多くの時間を使ってしまいました…考察が十分に整理できないままコードを書き上げてWAやREを量産してしまったので、反省です。

Codeforces Round #509 参加記録

Dashboard - Codeforces Round #509 (Div. 2) - Codeforces

いつもとは違い、(日本基準で)健康的な時間に開催されたこどふぉ。

結果はなんと全完!こどふぉでは全Division通して初めての全完です。TLEとかWAとかが怖い問題もいくつかあったので、運も良かったですね。

f:id:betrue12:20180917001948p:plain

大変ですが6問全部書きます。

A. Heist

Problem - A - Codeforces

問題概要

 n 個の整数  a_{1}, ..., a_{n} が与えられる。これはある長さの連続した整数列から、いくつかの要素を抜き取って並び替えたものである。「抜き取った個数」の最小値を求めよ。

制約

  •  1 \le n \le 1000
  •  1 \le a_{i} \le 10^{9} であり、これらは相異なる

解法

与えられた整数のうち、数字が飛んでいるところは必ず「抜き取られて」いるので、これらを数えます。具体的には a_{i} の最大値-最小値+1から  n を引けばよいです。

ACコード

B. Buying a TV Set

Problem - B - Codeforces

問題概要

整数  a, b, x, y が与えられる。正整数の組  (w, h) で、以下の満たすものの個数を求めよ。

  •  w \le a
  •  h \le b
  •  \frac{w}{h} = \frac{x}{y}

制約

  •  1 \le a, b, x, y \le 10^{18}

解法

まず、 x, y をこの2数の最大公約数で割って、既約にしておきます。条件には  x, y の比しか出てこないので、この操作をすることは問題ありません。

 x, y を既約にすると、 \frac{w}{h} = \frac{x}{y} を満たす正整数の組  (w, h) は 正整数  k を用いて  (kx, ky) と表せます。

あとは上限を超えない  k の取り方を数えれば良いので、割り算すれば求められます。

ACコード

C. Coffee Break

Problem - C - Codeforces

問題概要

 n 個の整数  a_{1}, ..., a_{n} が与えられ、それらは  m 以下である。これらの整数を下記の条件を満たすようにグループ分けするとき、そのグループ数の最小値を求めて、最小になるグループ分けの方法を1つ構成せよ。

  • グループ内の任意の2つの要素  b, c について、  |b-c| \lt d が成立する。

※問題文の読解がとてもつらくて、上記の文章は簡素化しすぎて原型を留めていません…

制約

  •  1 \le n \le 2\times 10^{5}
  •  n \le m \le 10^{9}
  •  1 \le d \le m
  •  1 \le a_{i} \le m でありこれらは相異なる

解法

要素をソートして、小さいものから順番にグループを割り当てていきます。

今まで作ったグループそれぞれについて、「そのグループで最後に追加した要素」を持っておきます。新しい要素を追加するとき、グループの最後の要素  c との間に  a_{i}-c \lt d の関係が成立していれば、そのグループに要素を加えることができます。

新しい要素を順に見ていって、どこかのグループにその要素を追加できるのであれば、そのグループに要素を追加します。どこにも追加できない場合、仕方がないので新しいグループを作ります。こうするとグループ数をできるだけ小さくすることができます。

要素を追加できるグループが複数あるとき、どこのグループに要素を追加するかは関係ありません。新しく見る要素はどんどん大きくなっていくので、もう既に  a_{i}-c \lt d が成立している要素  c たちは区別する必要がないからです。

なので、単に「最後に追加した要素が最も小さいグループ」をピックアップして、追加できるかどうか判定すればよいです。これは優先度付きキューなどに「最後に追加した要素の値とグループ番号のペア」を格納して小さい順に取り出していけば実装できます。

ACコード

D. Glider

Problem - D - Codeforces

問題概要

※問題ページに図があり、そちらを見たほうが分かりやすいです。

 xy 平面をグライダーが飛行する。 x 座標において  n 個の区間  [x_{i1}, x_{i2}] が存在し、それらの区間には上昇気流がある。これらの区間は交わらない。

初期位置の  y 座標を  h x 座標を好きに選んだ値として、グライダーを  x 軸の正の方向に飛ばす。グライダーは以下のように飛ぶ。

  • 上昇気流の区間内にグライダーが存在するとき、 y 座標は変化しない。
  • そうでないとき、 x 座標が1増加するたびに  y 座標が1減少する。

グライダーの  y 座標が0になるまでの  x 座標の移動距離の最大値を求めよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  1 \le h \le 10^{9}
  •  1 \le x_{i1} \lt x_{i2} \le 10^{9} であり、これらの区間は交わらない。また、昇順に与えられる。

解法

まず、グライダーの開始地点は上昇気流の区間の開始位置にするのがよいです。途中から始めると、そのすぐ後ろにある上昇気流の区間が無駄になります。

ある上昇気流の開始位置から飛び始めたとき、どこまで飛べるかを求めたいです。このとき、開始位置以降に存在する「上昇気流がない区間」を、どこまで着地せずに通過できるか?と考えるとよいです。上昇気流がない区間を飛んだ長さと同じだけ高度が下がっていくので、上昇気流がない区間の長さの合計が  h 未満であれば、着地せずに飛ぶことができます。

つまりグライダーの飛び方は以下のようになります。

  1. ある上昇気流区間の開始位置からスタートする。
  2. 上昇気流がない区間を、その長さの合計が  h 未満である限り通過する。
  3. その次の上昇気流区間を通過する。
  4. その次の上昇気流がない区間で、力尽きて着地する。

開始位置の上昇気流を左から右に全探索します。そうすると通過可能な「上昇気流がない区間」の右端も、左から右に移っていきます。このような性質が成り立つ場合は、しゃくとり法で効率的に計算することができます。

ACコード

E. Tree Reconstruction

Problem - E - Codeforces

問題概要

以下の条件を満たす  n 頂点の木を構築するか、それが不可能であることを判定せよ。

  •  n-1 本の辺それぞれについて、整数  a_{i}, b_{i} が与えられる。その辺で木を切断したとき、2つの部分木のうちで最大の頂点番号がそれぞれ  a_{i}, b_{i} となる。

制約

  •  2 \le n \le 1000
  •  1 \le a_{i} \lt b_{i} \le n

解法

まず、明らかに不可能になるケースがあり、それは  b_{i} \lt N となる辺が1つでも存在したときです。2つに分けた時、少なくとも片方には番号最大の頂点  N が含まれているはずです。

そうでない場合、最大でない頂点番号  v=1, ..., N-1 について、  a_{i} = v となる辺がいくつあるかを数えます。その数を元に、以下のように木を構築します。

  •  a_{i} = v である辺が1つであるとき、その頂点は頂点  N に直接接続する。
  •  a_{i} = v である辺が  k 個( k \ge 2 )あるとき、頂点  v と頂点  N の間に、頂点番号が  v より小さい頂点を  k-1 個挟む。
  •  a_{i} = v である辺が1つもない頂点は↑で間に挟むために使う。

「間に挟む」というのは、具体的には以下のようにします。 v より番号を小さい頂点を  k-1 個挟むと、その間の辺  k 本全てについて、部分木が条件を満たします。 v より番号が大きい頂点を挟んでしまうとNGです。

f:id:betrue12:20180917005940p:plain

この構成方法が不可能である場合は、多分どうやっても条件を満たす木が構築できないとは思うのですが…ちゃんと証明はしていません。この構成方法に限らず、より一般的な議論で「  a_{i} = vであるような辺が複数あるとき、間に挟める頂点があるか?」という考察を軸にして証明するのかなあ、とは思います。

ACコード

F. Ray in the tube

Problem - F - Codeforces

問題概要

※これも問題ページに図があるのでそれを見たほうが分かりやすいです。

横に伸びる管がある。管の伸びている方向を  x 座標軸とみなす。

管の下側と上側のいくつかの位置にセンサがある。これらは全て整数座標で表される。下側のセンサは  n 個で座標は  a_{1}, ..., a_{n} 、上側のセンサは  m 個で座標は  b_{1}, ..., b_{m} である。

管の下側と上側それぞれ整数座標点を1つ選び、下側の点から上側の点に向けてレーザーを撃つ。レーザーは管の中を反射して進み、いくつかのセンサに当たる。

レーザーが当たる座標点の最大数を求めよ。

制約

  •  1 \le n, m \le 10^{5}
  •  0 \le a_{i}, b_{i} \le 10^{9}

※実際には管の上側と下側の  y 座標が与えられているのですが、使わないので(!?)記載していません。

解法

これ、選ぶ座標点が有理数OKだとかなりキツくなりますが、整数座標限定なのでまだ解けます。

まず、レーザーを真上に撃つケースを考えます。この場合、上下で座標が同じ点にヒットし、延々とその間を反射し続けることになります。上下で座標が同じ点が存在すれば2、そうでない場合は1が最適です。

次に斜めに撃つケースを考えます。一番細かい間隔でレーザーを打てるのは、上下で座標が1ずれた点にレーザーを撃ったときです。

次に、座標が3ずれた点に撃ってみます。そうすると通る点は、1ずれたケースの下位互換になってしまいます。

f:id:betrue12:20180917012643p:plain

このように、他のケースの下位互換になるようなケースは考えなくて良いです。そうすると、3, 5, 7, ...は1の下位互換に、6, 10, 14, ...は2の下位互換に、といったようになり、結果的にずれ方が  2^{k} の場合だけを考えればよいことになります。ここまで絞れば、最大でも全部で  \log_2(10^{9}) くらいのケースを試せばよいので効率的です。

ずれ方が決まれば、あとは各要素について余りを求めて、対応するものを足し合わせます。例えばずれ方が2の場合は、4で割った余りが上と下で2異なるものが対応します。割る数が大きい場合は余りが取りうる値が大きくなるのでmap等を使うことになります。

※ちょっと問題の記述が足りないかな?と思うところはあって、「真上に撃てるのか?」もそうですが、センサの座標が相異なるのかどうか(上下左右含めてまったく同じ位置にセンサがあるのかどうか)も明記されていないように思います。実際、 a_{1} = 1, b_{1} = b_{2} = 1 という入力が許されるなら解は3になるはずですが、Editorialのコードだとこれは2を返します。ちょっともやっとする問題でした。

ACコード

さいごに

今回のレート上昇で薄橙になりました!

f:id:betrue12:20180917015037p:plain

一番上にちょっとだけ見えてる次の色が橙っぽいので、今の色は薄橙ですかね。皆さんはどう呼んでるんだろうか。

現行ルールだと、この色からDiv2単独開催もunratedになります。色落ちしない限りはDiv1で戦い続けることになるんですね…Div2単独も出ますけど。

AGC027 参加記録

結果は1完…速かったのでそこまでパフォーマンスは悪くないのですが、前回時点で黄色スレスレだったので色が落ちてしまいました。

f:id:betrue12:20180916041647p:plain

本番後に通したものも含めてA~Cを振り返ります。

A - Candy Distribution Again

A - Candy Distribution Again

解法

要求数が小さい子供から順番に配っていくと良いです。ぴったり配りきれない場合は最後の1人が満足できないので注意。

ACコード

B - Garbage Collector

B - Garbage Collector

解法

本番では「端から  i 個回収済みで原点にいるときの最小消費エネルギー」みたいなのでDPをずっと考えていましたが…どうやらそれでは最適でないケースがあるようです。

普通に解法を書くと公式解説とほぼ同じ流れになってしまうので、公式解説で省略されている内容を補足しつつ書いていきます。

移動エネルギーの求め方

まず、普通にゴミをいくつか拾う時の移動エネルギーを考えてみます。

f:id:betrue12:20180916100210p:plain

上図で、 x_{1} x_{3} のごみ全てを1回で回収することを考えます。所持ゴミが多いほどエネルギーが余計にかかるので、なるべく帰り道に拾ったほうがよいです。図のように拾っていくと、移動エネルギーの合計は  5x_{3} + 5x_{2} + 7x_{1} となります。

より一般的に書くと、各項にかかる係数は、

  • 一番右の  x の係数は、往路1と復路4の合計で5
  • 右から  i 番目( i \ge 2)の  x の係数は、 (i+1)^{2} から  i^{2} を引いたものになり、これを計算すると  2i+1 になる

となります。各係数が「そのゴミを何番目に拾うか」だけで決まり、その順番が遅いほど係数が大きくなっているのがポイントです。

往復回数決め打ち全探索

公式解説通り、往復回数を決め打ちして考えます。往復回数を  k とします。

このとき、 k 回の往復にゴミを割り当てることになりますが、どのような割り当てが最適でしょうか。

f:id:betrue12:20180916100813p:plain

この図のように、各要素に「ゴミを拾う順番」を割り当てます。 k 回往復するので、1番目に拾うゴミが  k 個、2番目に拾うゴミが  k 個…というのを割り当てることになりますが、これを右から順番に割り当てていくのが最適となります。

その理由は、直観的にはこう説明できます。前節で見たように、ゴミを拾う順番が遅いほど、そのゴミのための移動エネルギーの係数が大きくなります。より距離が長いほうのゴミに、より大きな係数を掛けてしまうと損です。そのため、遠いゴミほど係数を小さくしたい、つまり早い順番で拾いたい、と考えると上のようになります。

ちゃんと証明しようと思うと、最適でない並べ方と最適な並べ方の移動エネルギーの差分を計算して、不等式で評価して0以上であることを示すんじゃないかと思います。

累積和でまとめて計算

上記の割り当てのもとで、移動エネルギーの合計を計算していきましょう。このとき、拾う順番が同じ要素たちは、

  • 係数が同じ
  • 全て隣り合っている

という特徴があります。そのため、累積和を使ってまとめて計算することができます。

f:id:betrue12:20180916134223p:plain

累積和を事前に計算しておくと、拾う順番の最大値、つまり  \lceil \frac{N}{k} \rceil 回の計算で移動エネルギーを求めることができます。これは後で計算量の話の時に使います。

ゴミを拾う・捨てるエネルギー

後回しにしていましたが、ロボットは移動エネルギーの他に、ゴミを拾う・捨てるのにもエネルギーを消費します。

ゴミを拾う回数はゴミの個数と同じ  N なので、ゴミを捨てる回数(=往復回数)が  k であるとき、ゴミを捨てる・拾うエネルギーは  (N+k)X となります。

解法まとめ

以上で問題を解く材料が揃いました。

  1.  x_{i} の累積和を前計算しておく。
  2. 往復回数  k を決め打ち全探索する。
    1. 移動エネルギーは、累積和を使ってまとめて計算する。
    2. 拾う・捨てるエネルギーは  (N+k)X で計算できる。
  3. 全探索で一番小さかったものを答えとする。

これで解くことができます。往復回数決め打ちに気付くかどうか…ですね。

補足

計算量についてです。先程見たように、往復回数を  k とすると、その時の移動エネルギーは  \lceil \frac{N}{k} \rceil 回の計算で求められます。

ちょっと乱暴ですがceilを外して、 \sum_{k=1}^{N} \frac{N}{k} = N\sum_{k=1}^{N} \frac{1}{k} を考えます。この  \sum_{k=1}^{N} \frac{1}{k} という式は調和級数という名前が付いていて、だいたい  \log(N+1) くらいの値になります(積分で近似計算できます)。そのため、 \sum_{k=1}^{N} \frac{N}{k} = O(N\log N) であることから、移動エネルギーの計算量は全体で  O(N\log N) となります。累積和などそれ以外の計算は  O(N) なので、問題全体の計算量も  O(N\log N) です。

次にオーバーフローについて。すごく極端な例ですが、最も遠い、ほぼ  10^{9} の位置に  2\times10^{5} 個のゴミが密集していて、これを1回で回収することを考えます。そのとき、帰り道の距離はほぼ  10^{9} であり、持っているゴミの個数は  2\times10^{5} 個なので、 4\times10^{19} くらいになってlong longでもオーバーフローします。

これを検出して除外する方法ですが…1回1回の足し算の量がlong longの範囲を超えないようであれば、オーバーフローした時点で値が負になるのでそこで中断するという方法があります。符号付き整数で管理している場合のみ使える方法です。

「答えがlong long範囲外になっていないかどうか」も一応気にしないといけませんが、全要素を1個ずつ拾うケースだと移動エネルギー合計が個数×距離×5くらいで抑えられて、せいぜい 10^{16} くらいなので大丈夫です。まあこういう問題で答えがlong longの範囲外であることはそうそうないとは思いますが…

ACコード

C - ABland Yard

C - ABland Yard

公式解説の方法がだいぶ天才感あるので、まずはイメージしやすい頂点削除の解法を書いていきます。

解法1:頂点削除

「任意の文字列を作れる」ということは、「次にAにもBにも遷移できる」という状態を永遠に続けられることを意味します。

そのため、グラフ内に「次にAとBのどちらかにしか遷移できない」もしくは「どこにも遷移できない」という頂点が存在する場合、その頂点は「入ってはいけない頂点」ということになります。

f:id:betrue12:20180916114429p:plain

このような「入ってはいけない頂点」は、文字列を構成する上で使えないので、グラフから消してしまいます。そのとき、繋がっている辺もろとも消します。

そうすると辺を消したことで、他の頂点の遷移先が減ります。これにより他の頂点が「次にAとBのどちらかにしか遷移できない」という状態になってしまうと、その頂点も使えなくなります。こうして連鎖するように、頂点が消えていく可能性があります。

f:id:betrue12:20180916115137p:plain

上のグラフではその後、連鎖的に全ての頂点が消えてしまいます。そうなってしまった場合、答えはNoです。

一方、全部の頂点の削除判定を全て済ませてなお生き残った頂点がいる場合、それらの頂点は全て「次にAにもBにも遷移できる」頂点なので、その頂点を辿っていくことで任意の文字列を作ることができます。その場合、答えはYesです。

頂点の削除判定は、各頂点ごとに「A、Bに遷移する辺がそれぞれいくつあるか」を管理して、辺を消すごとに1引いていくと楽です。どちらかが0になったら削除します。

解法1:ACコード

解法2:AABB法

解法1で見てきたように、「任意の文字列を作れる」ということは、「次にAにもBにも遷移できる」という状態を永遠に続けられることを意味します。

仮に与えられたグラフで、「AABBAABBAABB…」という文字列を無限に続けられるとします。このとき、グラフが無向グラフなので、その経路内の任意の点はAにもBにも遷移できていることになります。この経路を前に進むか、後ろに戻るかで、異なるアルファベットに遷移できます。

※「端点は?」という話はありますが、一方が無限に続いているので、無限に遠いところ(具体的には、作りたい文字列の長さを超えるところ)からスタートすれば端点に届くことはありません。

f:id:betrue12:20180916121833p:plain

逆にこの文字列が作れないときに「任意の文字列を作れる」と言えないことは当たり前なので、「AABBAABB…」という文字列を無限に続けられるかどうかを考えれば、それが任意の文字列を作れることの必要十分条件になっています。

では、「AABBAABB…」という文字列を無限に続けられる条件を考えます。それぞれの「AABB」のうちの最初のAを「1つ目のA」と呼ぶことにします。頂点数は有限なので、この「AABBAABB...」を続けていくと、必ずどこかで「1つ目のA」が重複するはずです。なので、「1つ目のA」が重複している経路がない場合は「AABBAABB…」の無限経路が存在しないことになりますし、逆に重複していればその経路をぐるぐる回り続けることができます。

これで必要十分条件を「AABB...を繰り返す経路で、「1つ目のA」が重複しているものが存在する」まで落とし込めました。これを解くにあたって、「1つ目のA」と「2つ目のA」を分けて考えたくなります。そのため、AもBも1つ目と2つ目で分けて、頂点数を2倍にすることを考えます。

元のグラフは無向グラフでしたが、

  • 1つ目のAからは2つ目のAに
  • 2つ目のAからは1つ目のBに
  • 1つ目のBからは2つ目のBに
  • 2つ目のBからは1つ目のAに

だけ、それぞれ遷移するような有向グラフに変換します。この有向グラフにおいて閉路が存在すれば、それがAABB...を繰り返す経路で「1つ目のA」が重複しているものになります。

f:id:betrue12:20180916123714p:plain

このグラフで閉路が存在するかどうかを判定すれば、この問題が解けます。

解法2:ACコード

さいごに

大変な回でした…本番中はほぼ全ての時間をB問題のDPと戦うのに費やしていました。

次は黄色復帰を目指します!

ABC109 参加記録

2週間ARCとの併催で配点が恐ろしい感じでしたが、久しぶりにまともな配点のABCになりました。

結果は16分台全完で18位。けっこう速かったですね。ARCでもDが400だったらこのくらいの速度で解きたいです。

f:id:betrue12:20180908212243p:plain

A - ABC333

A - ABC333

解法

 A B のどちらかが偶数だったら  A \times B \times C は必ず偶数になります。また、 A B が両方とも奇数だったら  C = 1 とすることで積を奇数にできます。これを場合分けします。

ACコード

RubySubmission #3151145 - AtCoder Beginner Contest 109

B - Shiritori

B - Shiritori

解法

重複した文字列があるかの確認をして、  i 番目の末尾と  i+1 番目の先頭が一致しているかを  i=1, ..., N-1 について判定すればよいです。

ACコード

RubySubmission #3152443 - AtCoder Beginner Contest 109

C - Skip

C - Skip

解法

座標  X からのスタートだと考えにくいので、まず  x_{i} 全てから  X を引いて、座標0からのスタートだとしてしまいましょう。

そうすると到達可能な点は、座標0からスタートして任意回の  \pm D の移動で到達できる点、つまり  D の倍数です。つまり、(補正後の)  x_{i} 全てが  D の倍数であるという条件を満たすように、なるべく大きな  D を選べばよいです。これは  x_{i} の最大公約数になります。

ACコード

RubySubmission #3153468 - AtCoder Beginner Contest 109

D - Make Them Even

D - Make Them Even

解法

問題文だけ読むと分かりませんが、出力例を見ると構築問題であることが分かります。

全コインの合計が偶数だった場合は、全マスを偶数にするのが最適です。全コインの合計が奇数だった場合は、1マスを残してそれ以外を偶数にするのが最適です。このように作れないか考えます。

全マスを一筆書きできるような経路を考えます。そのような経路をずっと辿っていき、「マスのコイン数が奇数だったら次のマスに1個渡す」ということを繰り返していくと、全マスについての操作回数を1回以下にしつつ、最後に訪問するマス以外は全て偶数個コインにできるはずです。

場合によってはちょっと操作回数に無駄がありますが、操作回数は最小化しろと言われていないので、これで大丈夫です。一筆書きの経路は、例えば以下のようなものを作ると良いでしょう。

f:id:betrue12:20180908224134p:plain

ACコード

RubySubmission #3155067 - AtCoder Beginner Contest 109

さいごに

最近激しい回が続いていましたが、ちょっと和みましたね。

Educational Codeforces Round 50 参加記録

Dashboard - Educational Codeforces Round 50 (Rated for Div. 2) - Codeforces

結果は5完で72位!けっこう不安な問題が多かったのでシステス全部通って良かったです。

f:id:betrue12:20180908194632p:plain

A~Eを振り返ります。

A. Function Height

Problem - A - Codeforces

問題概要

底辺が2で高さが0以上の整数である三角形を  n 個作り、合計面積を  k にしたい。高さの最大値を最も小さくするように各三角形の高さを決めたとき、その値を求めよ。

制約

 1 \le n, k \le 10^{18}

解法

底辺が2なので高さの値がそのまま面積になります。 n 個の三角形にまんべんなく高さを振り分けて合計を  k にすると、その最大値は  \lceil\frac{k}{n}\rceil でありこれが最適です。

ACコード

B. Diagonal Walking v.2

Problem - B - Codeforces

問題概要

以下のクエリ  q 個に答えよ。

二次元平面があり、Mikhailは1回の操作で縦横斜めの近傍8マスいずれかに移動する。始点  (0, 0) 、終点  (n, m) 、操作回数  k が与えられ、始点から終点までちょうど  k 回で移動する経路のうち、斜め移動の回数が最大のものを選ぶ時、その回数を求めよ。(または、 k 回で到達できないことを判定せよ。)

制約

  •  1 \le q \le 10^{4}
  • 各クエリ  i について  1 \le n_{i}, m_{i}, k_{i} \le 10^{18}

解法

まず、到達できない条件を考えます。 k 回の操作で到達可能な  x, y 座標の最大値は  k であり、終点座標のどちらか1つでもこれを超えているとアウトです。

斜め移動を行った場合、  x, y 座標ともに偶奇が入れ替わることに着目します。可能であれば全操作で斜め移動をしたいですが、 (0, 0) から斜め移動  k 回だけを行った場合、終点座標は  n, m ともに  k と偶奇が一致している必要があります。

そうでない場合、例えば  k が偶数で  n が奇数だった場合は、全操作斜め移動というのは不可能であり、最低1回は  x 座標が変わらない移動をする必要があります。  y 座標についても同様です。

このような考察から以下のように答えを求め、実際の移動を構成することができます。

  1.  n, m の偶奇がどちらも  k とそれぞれ一致する場合、答えは  k。各操作での移動量は  x, y それぞれについて、和が  n, m と一致するように  +1 1 を並べればよい。
  2.  n k の偶奇が一致し、  m k の偶奇が一致しない場合、答えは  k-1。移動量は  x については1.と同様で、  y については1つだけ0を含み、残りは  +1 -1 を並べる。
  3. 2.と逆の場合、同様に答えは  k-1
  4.  n, m どちらも  k と答えが一致しない場合、答えは  k-2 x, y それぞれ移動量に1つずつ0を含む。移動量  (0, 0) は許されていないため、これらは別々の操作に配置されなければならない。残りは  +1 -1 を並べる。

最後の項目は、例えば以下のような移動量となります。  k=5, n=2, m=4 とした例です。

移動回数  x 移動量  y 移動量
1 +1 +1
2 +1 +1
3 +1 +1
4 0 +1
5 -1 0
合計 2 4

 k=1 n, m どちらも  k と偶奇が一致しないケースが怖くなりますが、そのようなケースは  (2, 2) より遠い点であればそもそも到達不可能として弾いていますし、  (n, m) = (0, 0) は制約上与えられないので、大丈夫です。

ACコード

C. Classy Numbers

Problem - C - Codeforces

問題概要

以下のクエリ  T 個に答えよ。

正整数  L, R が与えられる。  L 以上  R 以下の整数で、10進数表記したときに0でない数字の個数が3個以下であるものの個数を求めよ。

制約

  •  1 \le T \le 10^{4}
  • 各クエリ  i について  1 \le L_{i} \le R_{i} \le 10^{18}

解法

数値がやたら大きい、桁の値についての条件あり、ということで桁DPをやります。桁DPについては既に素晴らしい記事があるのでリンクを貼るだけに留めます。

桁DP入門 - pekempeyのブログ

今回の場合、「見ている桁」「 L を超えていることが確定しているかどうか」「  R 未満であることが確定しているかどうか」「非0の数字の個数」をパラメータとしてDPを組めます。メモ化再帰で書く場合は、非0の数字の個数が3を超えたら即0を返すような実装にすると、条件を満たさない整数をフィルタできます。

または下限の条件を外して、「  0 以上  R 以下で条件を満たす整数の個数」を求めることができるので、 R L-1 で2回計算して引き算しても良いですね。本番でこっちを思いついていればもっと実装が楽になったでしょう…。

ACコード

D. Vasya and Arrays

Problem - D - Codeforces

問題概要

長さ  n の数列  A と長さ  m の数列  B があり、これらをそれぞれ以下のように分割したい。

  • 分割した部分列の個数はどちらも  K 個である。
  • 全ての  i = 1, ..., K について、 A i 番目の部分列の合計と、 B i 番目の部分列の合計は等しい。

このような条件を満たす最大の  K を求めよ。(またはこのような分割が不可能であることを判定せよ。)

解法

分割が不可能である条件はすぐに分かって、  A, B の総和が一致しないことです。逆に総和が一致する場合は、最低でも  K = 1 が解になります。

最適な分割方法を考えます。 A, B の前からの部分列をそれぞれ伸ばしていって、できるだけ小さい値で部分列同士の総和が一致すれば、その点で分割するのが最適です。つまり  A, B の部分列のうち、その時点での総和が小さい方を1伸ばして判定、を繰り返すことが最適です。

ACコード

E. Covered Points

Problem - E - Codeforces

問題概要

二次元平面に  n 本の線分があり、以下の条件を満たす。

  • 線分の両端点は格子点(座標が全て整数である点)である。
  • どの2線分も同一直線上にない。

少なくとも1本の線分に含まれる格子点の個数を求めよ。

制約

  •  1 \le n \le 1000
  • 全ての線分の端点の座標は  -10^{6} \le x, y \le 10^{6} を満たす。

解法

この問題は、以下の2つのことを計算できると解けます。

  1. 線分それぞれについて独立に数えた、その線分に含まれる格子点の個数の総和
  2. 線分同士が交差する格子点と、その格子点を通る線分の個数のリスト

1で重複を気にせず独立に数え、2で数え過ぎた分を引く、という流れです。

まず1についてですが、これは最大公約数が使えます。両端点が格子点で、  x 座標が  a y 座標が  b 変化する線分に含まれる格子点の個数は  \gcd(a, b) + 1 となります。ただしどちらかが0の時は例外で、0でないほうの値を  c として  c+1 個です。

次に2についてです。交点の座標は連立方程式を解けば良いので計算できますが、コーディングだと色々面倒があります。私は以下の式を使いました。線分同士が平行である場合には0除算が起こったりするので注意。

月の杜工房 - 2直線の交点を求める

「線分の交点が存在して、かつそれが格子点」である場合を抽出します。直線の交点を求め、それが線分上にあってかつ格子点であるかを判定します。これを異なる線分全ペアについて試し、出てきた格子点とその出現回数をmapなどで集計します。

得られた重複格子点それぞれについて、重複分を引いていきます。線分  k 本が交差する格子点である場合、その格子点の出現回数は  \frac{k(k-1)}{2} 回であり、引くべき個数は  k-1 個です。出現回数から線分の本数を逆算するmapなどを作っておくと、集計した情報から引くべき個数が求められます。

ちょっと大変ですが、これでなんとか解けました…

ACコード

このコードでは線分の交点を求める際に「線分の交差判定をやってから交点座標を求める」という処理をしていますが、解法で書いたように先に交点を求めてしまったほうが楽だと思います。

さいごに

今回でこどふぉのレートが紫になりました!

f:id:betrue12:20180908205340p:plain

こどふぉはレートがガンガン変動しますね。またここから上がったり下がったりするとは思いますが、まだまだ上の色を目指して頑張ります。

Codeforces Manthan, Codefest 18 参加記録

何か不規則な解き方してますが、Fが通ったおかげでレートも結構上がりました。Dは誤読で落ちました(にゃーん)

f:id:betrue12:20180903203023p:plain

後から解いたものも含めてA~Fを振り返ります。

A. Packets

Problem - A - Codeforces

問題概要

1円玉  n 枚をいくつかの袋に入れて、「袋をいくつか適切に選ぶことで、合計金額  0, 1, 2, ..., n*1の全通りが作れる」状態にしたい。最小の袋の数を求めよ。

解法

2進数で作るとよさそうです。 2^{m} -1 \le n である最大の整数を  m として、 m 個の袋に  1, 2, 4, ..., 2^{m-1} 円を入れると、  0, 1, 2, ..., (2^{m}-1) 円の全パターンが作れます。端数が出た場合は、余った分をもう1つの袋に入れれば、  n まで全部のパターンを作れます。つまり袋の数は、  2^{M} - 1 \ge n であるような最小の整数  M となります。構成方法を示したので、これは十分条件です。

次に必要性、つまりこれより小さい解がないことを確かめます。  M 個の袋を使って得られるパターン数は、いくら値が被らないように努力したとしても、全ての袋について「選ぶ」「選ばない」で分岐した高々  2^{M} 通りです。作る必要があるパターン数は  n+1 通りなので、  2^{M} \ge n+1 が必要条件となります。これは上の式に一致するので、ちょうど必要十分です。

ACコード

B. Reach Median

Problem - B - Codeforces

問題概要

素数 n (奇数)の数列  a_{1}, ..., a_{n} と整数  s が与えられる。操作「数列の要素  a_{i} を1つ選び、+1または-1を足す」を繰り返して数列の中央値を  s にしたい。操作の最小回数を求めよ。

解法

素数が奇数の数列の中央値が  s になる条件は、要素を左から右に昇順ソートしたときに真ん中の要素が  s であることです。もう少し全体的に見ると、

  • 真ん中の要素が  s である
  • 真ん中より左の要素が  s 以下である
  • 真ん中より右の要素が  s 以上である

このようになっていればよいです。

元の数列を昇順ソートして、上記の条件を満たすように加減してやればよいです。わざわざ大小の順番を入れ替えるような操作は、得になることはありません。

ACコード

C. Equalize

Problem - C - Codeforces

問題概要

長さ  n で各文字が0か1の文字列  a, b が与えられる。 a に以下の操作を好きな順序で好きな回数繰り返して、  b と一致させたい。最小のコストを求めよ。

  •  a の文字を1つ選んで書き換える。コスト1。
  •  a の文字を2つ選んで入れ換える。コストは入れ換える2文字の距離。

解法

まず、「入れ換える」ことで得になるケースはかなり限られています。入れ換える操作は、最大2文字を書き換える操作をすれば同じことができて、そのコストは最大でも2です。つまりコストが2以上かかるような入れ換え操作はする必要がなくて、

  • 隣り合った2文字を両方書き換える(コスト2)代わりに、その2文字を入れ換える(コスト1)

以外の入れ換え操作では得をしないことがわかります。そのため、

  •  a 側が「10」で  b 側が「01」、あるいはその逆である箇所のみ、入れ換え操作を行う。
  • それ以外の場所は単純に書き換え操作を行う。

これで最適となります。

ACコード

D. Valid BFS?

Problem - D - Codeforces

問題概要

 n 頂点の木と、  1, ..., n を並び替えた数列  a_{1}, ..., a_{n} が与えられる。数列が「木を頂点1からBFSしたときの探索順序」になっているか判定せよ。

解法

問題文にも書いてありますが、BFSを実装する際は

  1. 始点をキューに入れる。
  2. キューから頂点番号を取り出す。
  3. その頂点に隣接する頂点のうち未訪問のものをキューに入れる(普通のBFSでは、このときのpush順序は実装者が勝手に選ぶ)。
  4. 2に戻る。

を、キューが空になるまで続けます。

今回は始点と探索順序が指定されているので、

  1. まず数列の始点  a_{1} をキューに入れる。ただし、これが1でない場合は No で終了。
  2. キューから頂点番号を取り出す。
  3. 数列で指定された順に、その頂点に隣接する頂点のうち未訪問のものをキューに入れる。このとき、指定された次の番号が隣接する頂点として取れない場合、順番が守れないので No で終了。
  4. 2に戻る。

これをキューが空になるまで完遂できれば Yes です。

本番では太字にしたところを完全に読み忘れていました。これでプレテスト通るのか…

ACコード

E. Trips

Problem - E - Codeforces

問題概要

 n 人の人がいて、以下を  m 回繰り返す。 m 回それぞれについて、2. の答えを出力せよ。

  1.  x_{i} y_{i} が友達になる。(友達になるペアは毎回異なる)
  2. 「グループ内に少なくとも  k 人友達がいる」を全員が満たしているようなグループを作る。そのうち最も人数の多いものを選び、その人数を出力する。

解法

友達がどんどん増える優しい世界ですが、これだと考えにくいので、時間を逆回しして友達がどんどん減っていく設定にします。(悲しいですね)

人を頂点、友達関係を辺とするグラフを考えます。まず最後の状態を考えるため、全ての辺を追加してしまいます。これ以降、辺が増えることはありません。このとき、

  1. 友達が  k 人未満の人は、絶対にグループに入れないので除外する。
  2. 他の人が除外された結果、友達が  k 人未満になってしまった人も除外する。

これを繰り返すと、最後に残った人たちは  k 人以上友達がいるため、全員でグループを組むことができます。

あとは、時間を巻き戻すごとに辺が1つずつ消えていくので、その2人について上記の1. の判定を行い、2. の判定を伝播させていけばよいです。

どれだけ伝播するかで1回1回の判定回数にはばらつきがありますが、必ず「辺を切る」という操作を伴うため、問題全体での判定の合計回数は、高々辺の数の定数倍になります。

ACコード

F. Maximum Reduction

Problem - F - Codeforces

問題概要

ちょっと問題文の読解が難しいので図にします。

f:id:betrue12:20180904003852p:plain

素数  n の数列と整数  k が与えられ、図のように「連続する  k 要素の最大値」を取っていく操作を繰り返します。要素数 k 未満になったら操作終了です。

この図では  n = 5, k = 3 です。(問題文中の2つ目のサンプル)

この操作でできる、2段目以降の数列の合計値を求めよ、という問題。

解法

この操作では、大きい数字がずっと残り続け、大きい数字の近くにある数字はmaxを取る時に消えていきます。

もちろん一番大きい数字は最後まで残るのですが、それ以外の数字になる場所だけを見てみましょう。

f:id:betrue12:20180904004501p:plain

最も大きい数字「9」以外の要素は、1段目4つ・2段目2つ。これは、「最初から1段目が左側の4要素しかなかったとしたら」と考えた時の、操作結果と全く同じになります。

一番大きい要素の位置が端っこでない場合はどうでしょうか。

f:id:betrue12:20180904005100p:plain

少しごちゃごちゃしていますが、一番大きい「9」で分断された左右が、やっぱりそれぞれ問題で与えられた操作結果と同じになっています。

ここから、「一番大きい数字で分断して再帰的に処理していく」という方針が立ちます。必要な道具は、

  1. 任意の区間内での数列の最大値と、その位置を効率的に取得する。
  2. その最大値が、2段目以降の数列全体で合計いくつ存在するかを効率的に求める。

の2つです。

1についてはセグメント木が使えます。値と位置をペアにして格納しておけば位置も取れます。

2についてですが、上図の「9」の配置なんかを見ると不規則に見えます。ので、ちょっと計算をサボって「一度全部のマスで足してしまって、残りを差分更新することで調整する」という方法を取ります。

f:id:betrue12:20180904010056p:plain

図のように差分で計算をしていけば、1度の計算で扱う範囲は3角形(場合によっては台形)のような形になり、等差数列の和の公式で数を求められます。

解法をまとめると、

  1. 区間内の最大値とその箇所をセグメント木で求める。
  2. 今考えている区間から発生する数列の要素数の合計を、等差数列の和の公式で求める。
  3. 個数×(今回の最大値 - 前回の最大値)を答えに加算する。
  4. 最大値の箇所で区間を分割し、再帰的に処理する。

これで解けます。

配点高めですが、類題の経験があったので意外とサクっと解けたような気がします。

ACコード

さいごに

f:id:betrue12:20180904011157p:plain

今回のコンテスト後のレートが1892。誤読しなければ紫になっていたと思うと虚しいですが…これもこどふぉ。問題はちゃんと読みましょう。

脚注

*1:元問題の記載では1円からですが、「袋を1つも選ばない=0円」を含めたほうが説明の都合がよいのでそうしています。

AtCoder黄色になりました

昨日のARCで、黄色になることができました!

f:id:betrue12:20180902133514p:plain

パフォーマンス推移

f:id:betrue12:20180902131759p:plain

リンク

ratedのみ載せています。青になったときと同じく、+150くらい上がって一気に届いた感じです。

このARC102は300-700-700の3完です。700を2問解ければこのパフォーマンスが出る、というのは希望が持てるのではないでしょうか。今までは、1000点くらいの問題を解かないと届かないイメージだったので…

上がってしまったからにはこれを維持しなければ…というプレッシャーがありますね。まあでも青からも1回落ちていますし、落ちてもまた上がればよいので、気楽にいきます。

やったこと

問題を解いた

f:id:betrue12:20180902134850p:plain

リンク

AC数です。この中で個人的に重要だと思うのがARC-E(上の画像だとC)とAGC-Cで、黄色に届くためには

  • ARC-Eをそこそこの頻度で解く
  • AGC-Cを安定して解く
  • (ARC-DやAGC-Bを落とさない)

のどちらか、できれば両方が必要だと感じています。ただこれは配点にもよりますし、特にARC-Dが700点とかの異常難しい回は実質ARC-Eと同じ扱いです。

ただやっぱりARC-Eは難しくて、ARC-Dをほぼ埋め終わったくらいのレベルで挑むと返り討ちにあいます。まずは解けそうな問題から埋めていって(昔の問題とか楽なのもあるのでオススメです)、その後は

  • 解説ACをしていく
  • ARC/AGC以外の、企業コンを埋めていく
  • 問題を求めて他サイトに行く

あたりから選ぶのがいいかなと思います。

企業コンはけっこうオススメで、配点の割に難しい問題もありますが(400点で二部グラフとか…)、ARC/AGCとは少し違う知識が必要になります。いわゆる「ライブラリで殴れる」ような問題も多いので、埋めていくとちょっと高度なライブラリも充実していくんじゃないかと思います。

あとはまあ「知らないと思いつかない」ような解法がいっぱいあるので、解説ACも良いと思います。というか、解説読んでも分かりません。解説を読み込んで理解し、苦労してちゃんと通せば、類題やそれより少し易しめの問題が本番で出た時に解ける見込みが出てきます。

私は現時点で解説を読んだまま放置している問題がけっこうあるので、ちゃんと通していかないと。

Codeforcesを始めた

これは好みだと思います。私は単純にコンテストの場数が増えたので良かったなと思います。問題の傾向も少し違いますし。

海外サイトなので、英語を読めるかどうかでかなり効果が分かれるかなとは思います。競プロ以前に英語でつまづくと学習効率が下がってしまいますが…「ついでに英語の訓練を」という意識ならそれでもアリです。

AtCoderはコンテスト中に正解/不正解の確定結果が知らされる「フルフィードバック」方式ですが、Codeforcesは提出直後には一部のテストしか実行されず、他参加者から不正解ケースを指摘される「hack」やコンテスト終了後に改めて全てのテストが実行される「システムテスト」があります。サンプルもAtCoderに比べると不親切な傾向があるので、自力でコーナーケースを疑ったり、危なそうなテストケースを作って実行してみる必要があります。この能力は、方式の違うAtCoderでも損にはならないはずです。

C++を始めた

青になるまではRubyだけで戦ってきましたが、ARC-EあたりからRubyでは想定解でも通らない問題が出てきます。実質的に出題数が減るのと同じことなので、なかなかキツいです。

最近はPythonで競プロをやっている人も多いので、いずれ同じようにこの壁に当たると思います。このような時の選択肢は、

  1. 今の言語を使い続ける。
  2. 今の言語と高速な言語を併用する。
  3. 高速な言語に完全移行する。

になります(それはそう)

1は率直に言ってかなりストレスがあると思います。解法が分かっているのに通せない、これは私にとっては苦痛でした。当然、実力よりもレートの伸びは悪くなります。それを受け入れられるかどうか、だと思います。

2は今の私が取っている方法です。ちょっと面倒なので「慣れ」が必要だとは思います。ライブラリを2言語用意したり、コード提出欄の言語選択に気を遣ったり。まずは過去問から練習していくといいでしょう。今の言語に愛着があって使い続けたい人向け。

3は完全移行するまでが大変ですが、それ以降を考えると一番楽だと思います。新しい言語の経験を一番多く積めるのもこの選択肢です。

やはり強い人からは直接的または間接的に「速い言語を使うべき」という話がちらほら出て、少し肩身は狭いです。でも個人的にはスクリプト言語を使っている人は勝手に応援していて、青になるまではそのままでいいんじゃないかなとは思っています。それ以降、ぼちぼちどうするかを考え始めてもいいと思います。

用意したライブラリ

前回との差分でめぼしいものを挙げます。

  • グラフ
    • 最大フロー(最小カット、二部マッチングもここに含まれます)
    • 強連結成分分解、二重辺連結成分分解
  • データ構造
    • 重み付きUnion-Find、部分永続Union-Find
  • 文字列
    • Z-Algorithm(過去問で使ったのでそのまま保存)

意外と増えてない…?青になる前に用意しすぎたかもしれません。

多分セグメント木の派生とか、文字列まわりのアルゴリズムで足りてないものがあるので、使う問題に出会ったら順次作っていきます。

データ構造だとセグメント木やBIT、アルゴリズムだと最小全域木クラスカル法)やLCAあたりは青までには使わなかったかもしれないので、作っていない場合は是非用意しておくと良いと思います。

知識や考え方については挙げていくとキリがないので…何か別の機会があれば書いてみたいなと思います。

さいごに

色が変わったというのも分かりやすい指標ではあるのですが、やはり問題を解けることが楽しいです。今まで手も足も出なかった問題に少しずつ太刀打ちできるようになっている、という実感があります。この調子でどこまで行けるか…自分の力で届くところまで行ってみたいです。

引き続きブログも続けていきます。私のブログを読んで理解して通せた、という声が励みになっています。これからもよろしくお願いします。