ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

CODE FESTIVAL 2018 Final (Parallel) 参加記録&解説(A~F)

オープンコンテスト8位でした。

f:id:betrue12:20181118231936p:plain

A~Fについて書きます。この記事を書いている時点で解説が公開されていないため、Twitterなどで見た他の参加者さんの解法を大いに参考にしながら書いています。

A - 2540

A - 2540

解法

長さが  l 2540-l の2本の辺で、ちょうど1つの端点を共有するペアを数えればよいです。ただし、重複しないように注意する必要があります。

私の方針は以下です。

  • 頂点  v と辺の長さ  l ごとに、「頂点  v から伸びている長さ  l の辺の本数」をmapで管理する。
  • 辺を1本ずつ見ていく。そのとき、
    • その辺の端点それぞれについて、その時点でのmapを使ってこれ以前に見た辺のうちペアになるものの辺の本数を数える。
    • その後、辺をmapに追加する。

このようにすると重複なく数えられます。

ACコード

B - Theme Color

B - Theme Color

解法

要求されている答え方が特殊ですが、まずは普通に確率の求め方を考えます。結論を書くと、求めたい確率は

 p = \frac{N!}{r_{1}! r_{2}! \cdots r_{M}!} (\frac{1}{M})^{N}

になります。この計算は、 M=2 の場合は「反復試行の確率の公式といろいろな例題」に説明があり、これを「多項定理の例題と2通りの証明」に書かれている式のように  M\ge 3 の場合に拡張したものです。

さて、求めたいのは  p \ge 10^{-x} を満たす最小の整数  x です。指数の形を除去するため、両辺底が10の対数を取ります。対数を取ると積は和になるので、

 \log_{10}p = \log_{10}N! - (\log_{10}r_{1}! + \cdots + \log_{10}r_{M}!) - N\log_{10}M \ge -x

という式になります。この式から求めたい整数  x

 x = \lceil -\log_{10}N! + (\log_{10}r_{1}! + \cdots + \log_{10}r_{M}!) + N\log_{10}M \rceil

となるので、 \log_{10}k! 1 \le k \le N の範囲で前計算しておけば  x を計算できます。

ACコード

Rubyのコードは多項定理ではなく二項定理の組み合わせで書いているので少し無駄な計算が入っていますが、やっていることは同じです。

C - Telephone Charge

C - Telephone Charge

解法

制約が特殊です。それぞれのプランで、通話時間  A_{i} の時に料金が他のプランより安くなるということは、グラフで描くと以下のような関係になっているはずです。

f:id:betrue12:20181119004253p:plain

色が各プラン、太線になっているところがその区間での最安のプランを示しています。このグラフから、例えば図中の  T_{i} の位置であれば、 プラン3またはプラン2が最安になることがわかります。

解法としては、プランを  A_{i} の値でソートしておき、各  T_{i} についてどの  A_{i} の間に位置するかを二分探索などで特定し、その2つ(端なら1つ)の値を両方試して安い方を採用すればよいです。

ACコード

D - Three Letters

D - Three Letters

解法

本番は解けませんでしたが…

文字列の中から文字列の並びを探す時に、文字種とインデックスのどちらでループを回すかによって計算量の見積もりが変わってきます。今回の場合、「1文字目と3文字目は文字種で、2文字目はインデックスで」という少しトリッキーな考え方が必要になります。

ある文字列  A_{i} について、2文字目のインデックスを左から右にずらしていきます。このとき、「左側に各文字がそれぞれ何個あるか」「右側に各文字がそれぞれ何個あるか」は、累積和のように計算することができます。

f:id:betrue12:20181119194955p:plain

このようにすると、

  • 2文字目は、文字のインデックス全てについて全探索(全文字列合わせて最大  90000
  • その2文字目に対して、1文字目と3文字目を文字種全てについて全探索( 52^{2})し、ともに1個以上あるかチェック

として、3文字の文字列の存在を判定することができます。

ただしこの数え方をそのまま行うと、ある  A_{i} に対して同じ文字列を重複して数えてしまう可能性があります。それを防ぐため、3文字の文字列パターン全てにおいて「その文字列が最後に発見されたのはどの  A_{i} か?」という値を管理しておきます。こうすると重複カウントを防ぐことができます。

※計算量について、単純計算すると  90000\times 52^{2} \simeq 2.4 \times 10^{8} となるので、これがもし想定解ならばかなり厳しい気がしています。ただコンテスト終了後のTwitterの書き込みを見た感じ、高速な言語を使ってこの解法で通した人が多そうです。

ACコード

実装においては、配列のインデックスなどに文字を使うためにアルファベット52文字を0~51の整数に変換しています。アルファベット大文字と小文字の間はASCIIコード上で連続していなかったりするので地味に注意です。

E - Tough Journey

E - Tough Journey

解法

高橋くんが町  i にいるとき、手持ちの水が合計何本になるように買うべきか考えます。もし距離  K 以下の位置に今いる町よりも水の安い町がある場合、町  i ではその町に行けるだけの水を買って、安いほうの町で新しく水を買うべきです。

そのため高橋くんが町  i にいて、次に訪れる町  i より水の安い町が町  i+k であるとき、

  •  k \le K ならば、町  i では手持ち  k 本になるように水を買う。
  •  k \gt K ならば、仕方がないので町  i で上限の  K 本まで水を買う。

このように水を買うのが最適となります。

あとはこれを効率的に解く実装を考えればよいです。実装方法もいくつかあると思いますが、私の方針は

  1. 町を水の安い順にソートする。
  2. セグメント木を用いて、ソートした町に対して以下を順番に行う。今考えている町を  i として、
    • それまで見てきた町から、  i よりインデックスが大きいものの中で最もインデックスが小さいものを求める。
    •  i をセグメント木に追加する。

としました。具体的な実装はコードを参照してください。

ACコード

F - Dinner Planning

F - Dinner Planning

解法

まず単純に考えると、順番に食事をしていくことを仮定しながらグルメ度の変化を見ていって、

  • グルメ度が  K を超えてしまった場合、それまでに行ったレストランの中で最も美味しさが低いものをキャンセルする。
  • グルメ度が  0 を下回ってしまった場合、それまでに行ったラーメン屋の中で最も美味しさが低いものをキャンセルする。

ということをしたくなります。

ただし、これでは困るケースが出てきます。例えば以下のグラフのように、「グルメ度が  K を超えたので過去のレストランをキャンセルしたら、そのせいでグルメ度が0未満になる日が出てしまった」というケースです。

f:id:betrue12:20181119202732p:plain

こうなっては困るので、キャンセルすべきは「最後にグルメ度が0になった日以降で、美味しさが最も低いレストラン」となります。グルメ度が0を下回った場合は全く逆のことをします。

※これを毎回貪欲に選んで大丈夫なのか?後々の選択と合わせるとより良い選び方があるのでは?という疑問が浮かびますが、ちゃんとやると証明できると思います。記述がかなり長くなりそうなのでここでは省略します…

ということで、求めたいのはそれまでのグルメ度の推移を全て計算しておき

  • 最後にグルメ度が0(または  K )になったのはいつか?
  • ある区間におけるレストラン(またはラーメン屋)で一番美味しさが低いのはどれか?

を求めることです。これだけならどちらもセグメント木を用いて求めることができます。グルメ度に関してはある日から現在までの区間最小値が0かどうか(または最大値が  K かどうか)で二分探索です。

ただしグルメ度に関してはそれに加えて「過去に遡って、食事をキャンセルした日以降のグルメ度を1変化させる」という操作が必要です。そのため区間に対する操作を行える遅延評価セグメント木を用いれば、必要な全ての操作が可能になって解くことができます。

ただ、これまた想定解ではなさそうですね…。

ACコード

Submission #3623458 - CODE FESTIVAL 2018 Final (Parallel)