ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC149 E - Handshake

二分探索

問題
提出コード

解法

明らかに、得点の和が高いペアから順番に握手をしていくのが最適です。
ある得点Xが達成できるとすると、明らかにX未満の任意の得点Yは、全く同じ手を選ぶことで達成でき、達成できないときはX以上の得点はどう頑張っても達成できないので、

  • X以上の得点を達成できるか

について単調性が存在します。
このXについて二分探索をしたいのですが、うまくいきません(僕はいきませんでした)。ので、少し見方を変えます。
得点の和が高いペアから順番に握手をしていくのが最適だったので、ある得点Pについて、

  • P以上となるペアについては握手を行い、P未満となるペアについては握手をしない

という区切り目が存在するはずです。
P以上となるペアの個数がM個以上になると、M回握手することができます。
P以上となるペアの個数についても、Pが減少すれば個数が増加し、単調性が存在しています。ので、

  • P以上となるペアの個数がM以上になる

ような、最大のPを二分探索で求めることができます。
すると、そのP以上のペアの総和を求めればよいです。
片手がA_{i}のとき、もう片方の手は、(P-A_{i})以上のA_{j}を選ぶことができます。このA_{j}の個数は、Aが降順ソートされていれば、二分探索で求めることができます。
これにより、ペアの個数を求めることができました。
総和についてもほぼ同様で、A_{1}からA_{j}までの総和と、A_{i}\times(選べるA_{j}の個数)の総和を全てのiについて足したものになります。
これは、後者についてはそのまま個数をかければよく、前者については累積和をあらかじめ計算しておくことで、高速に計算することができます。
あとは、コーナーケースである、

  • P以上となるペアの個数がぴったりMではなかった場合

についての差分を計算すればよいです(サンプル2参照)。
得点の和がP+1以上となるペアはM個未満になってしまうはずなので、今P以上となるペアの個数がM+q個あるとしたときに、総和から除くべきq個のペアは、得点がPとなっているものについてです。
ということで、Pqを、全体の総和から引いてあげれば求める答えとなります。

感想

見るからに二分探索をしたいなぁ、と思っていたのですが、うまく二分探索をする方法を考えるのに詰まってしまいました。
見方の変え方が課題です。

ABC149 D - Prediction and Restriction

動的計画法(DP)

問題
提出コード

解法

次に出す手は、K手前の手にのみ依存します。
よって、じゃんけんの出す手は、Kで割った余りごとに独立して考えることができます。
dp[i][j] = i番目に出す手がjであるときにおける、i \ mod \ Kの手番についての得点の総和の最大値
とすると、答えは\displaystyle \sum_{i=N-K + 1}^{N} max(dp[i][j])
となります。
dp[i][j] = max(dp[i-k][k] + (jで勝てる場合はその得点) ) (j \neq k)
となります。

感想

貪欲でも解けるらしいのですが、証明を短時間で行うのが難しそうな上、DPの方が確実な気がします。
言われてみれば確かに…ってなりました。

ARC050 B - 花束

二分探索

問題
提出コード

解法

P個の花束を作成できるかどうか、を調べます。
まず、2種類の花束どちらも、1つの花束につき少なくとも1本使用することになるので、最低P本ずつ使用することになります。
この部分を除くと、

  • 赤い花をx-1本使用する

  • 青い花をy-1本使用する

の2通りの操作どちらかを行うことで、1つの花束を作成することができます。
ので、結局、
\frac{R-P}{x-1} + \frac{B-P}{y-1} \geqq P
であれば、P個の花束を作成することができます。
この条件を調べて、P個の花束を作成することができるとわかったとき、P個未満の花束は明らかに作成することができます。
ということで、単調性が存在するため、上の条件を満たす最大のPを二分探索で求めれば答えとなります。

感想

個数を決め打ち、どちらか片方のコストを0にして考えやすくする、といったよくある考え方が詰まっている気がします。

ARC044 B - 最短路問題

数え上げ

問題
提出コード

解法

頂点1が距離0でない場合や、頂点1以外が距離0である場合は、明らかに答えが0になるので処理しておきます。
それ以外のグラフについて考えます。
あらかじめ、距離がxの頂点の個数c_{x}をそれぞれカウントしておきます。
距離がxである頂点は、距離がx-1である頂点、xである頂点、x+1である頂点に向けて辺を張ることができます。x+1である頂点との辺は、距離がx+1である頂点から張る辺について考慮するときに計算すればよいので、距離がxである頂点について考えるとき、x-1の頂点とxの頂点に向けて張る辺についてのみ計算していきます。

  • 距離x-1の頂点に向けての辺の張り方
    距離xの頂点を1つ選びます。すると、この頂点は、距離がx-1である頂点のうちすくなくとも1つの頂点に向けて辺が張られていなければなりません。
    今選んだ頂点と、c_{x-1}個の頂点との辺の張り方は、2^{c_{x-1}}通りありますが、この中で選んではいけないパターンは、どこにも辺が張られていないパターンただ1つです。
    ということで、距離xの頂点1つに対し、距離x-1の頂点との辺の張り方は2^{c_{x-1}} - 1通りとなります。
    これが、c_{x}個の頂点について同じことが考えられるので、最終的に距離xの頂点とx-1の頂点についての辺の張り方は、
    (2^{c_{x-1}}-1)^{c_{x}}通り
    です。

  • 距離xの頂点同士を結ぶ辺の張り方
    距離xの頂点同士を結ぶ辺の張り方は、_{c_{x}}C_{2}通りです。今回は、全ての辺について、張る、張らないの2パターンを自由に選べます。
    ということで、
    2^{_{c_{x}}C_{2}}
    通りの張り方が存在します。

ということで、a_{i}の最大値をmとして、
\displaystyle \prod_{x = 1}^{m} (2^{c_{x-1}}-1)^{c_{x}} \times 2^{_{c_{x}}C_{2}}
が答えとなります。

AOJ 2435 - Zero division checker

未分類

問題
提出コード

解法

計算結果は、いずれのタイミングでも、どのように計算しても最大で256通りです。
毎回、2つの変数を用いて演算を適用するので、256^{2} = 65536通りとなります。
演算は|s|未満であることは確実なので、十分計算が間に合います。
よって、可能性のある計算結果を全列挙しつつ愚直に演算を当てはめていけば、0除算があるかどうかがわかります。

AOJ 2402 - 天の川

幾何 ダイクストラ法

問題
提出コード

解法

任意の五芒星から別の五芒星に向かう際に通る最短距離さえ計算できれば、あとはベガからアルタイルに向けてダイクストラ法で最短経路を計算すればよいです。

五芒星は5本の線分でできています。ということで、2つの五芒星の最短距離を調べる際は、それぞれ5本の中から1本ずつ線分を取り出し、2本の線分同士の最短距離を計算して、25通りの取り出し方の中で最も小さいものを距離とすればよいです。
ということで、2本の線分同士の距離を求めることができればいいことになりました。
2本の線分同士の最短距離は、少なくともどちらか片方の線分については端点が選ばれます(片方の線分を点のあつまりとみなし、もう一方の線分との距離が最短になる点を探していくとどちらか一方は端点になります)。 ということで、4つの端点に対し、点と線分の距離を求めてあげれば、その中の最小値をとってあげることで、線分同士の最短距離を求めることができます。

AOJ 2640 - 不審者

実装系

問題
提出コード

解法

言われた通りに実装をしましょう。

感想

最後に出力すべきものを誤読していたため、時間がかかってしまいました…
行う操作によって手数が変わるかもしれない、とdpっぽくやっていったのですが、(本来の)答えが一意に決まることに気づいたのはその誤読に気づいてからでした。
この量の実装で細かいバグもなく一発で通せたのは気持ちいいです。