読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ARC #039

あまり更新をしている暇はないけれどB問題のもやもやが晴れたのでメモ。
D問題はまだ解いてないです。
コンテスト本番はCの実装が間に合わず200点

- A問題「A - B Probrem」

(http://arc039.contest.atcoder.jp/tasks/arc039_a)

問題概要:
3桁(100以上999以下)の値A,Bが与えられます。
A,Bいずれかの数字を選び、数字の桁の数字を一つ変えて新たな3桁の数字にすることができる。
変更後のA-Bのうち最大値を求めよという問題です。

解法:
この手の問題は貪欲でやるよりも全探索をしたほうがコーナーケースに落ちにくいと思います(個人差あり)
したがって100の位を1~9,10,1の位を0~9に変えてやったときの(9*2+10*4)パターンを全て試してA-Bの最大値を探しましょう。
桁ごとの操作はintではなくstringでやった方が楽です。
解は負の数もとりうるので解の初期値を-1000ぐらいにしておきましょう。

ソースコード:
https://arc039.contest.atcoder.jp/submissions/405455

- B問題「高橋幼稚園」

(http://arc039.contest.atcoder.jp/tasks/arc039_b)

問題概要:
この記事のメインのつもりです。
N人の子供にK個のキャンディーを配る。
i番目の子供にk_i個キャンディーを配るとき、
 \prod_{i=1}^N k_i,(\sum={i=1}^k)が子供全体の満足度となる。
満足度が最大となる配り方が何通りあるか答えよという問題です。

解法:
公式の証明がなかったのでどのように配れば満足度が最大となるかの証明から。
まず子供よりキャンディーが少なければ1個ももらえない子供が現れるので満足度は0。

N \le Kの場合について考える。
まず最低でも一人1個持たなければ満足度が0になってしまうので1個ずつ配る。
残りのキャンディーはK-N個となり、これをどのように配ればよいかについて考える。
現在子供が持っているキャンディーの個数をk_1,k_2,,,,k_Nとすると、満足度M=\prod_{i=1}^N k_iとなる。
この状態から,新たにキャンディーをi番目の子供に与える。すなわちk_i=k_i+1という動作を行うと,全体の満足度はM'=\frac{k_i+1}{k_i}*Mとなる。このとき,どのようなiを選べばM'が最大になるかということだが、\frac{k_i+1}{k_i}が最大になるようなiを選べば良い,すなわちmin_{i=1}^N k_iをとるiを選べばM'が最大になる,この操作をキャンディーの残りがK-N,K-N-1,,,,0となるまで繰り返せば満足度が最大になり、k_iが小さい順にキャンディーを分け与えていくという動作を繰り返すとk_iは均一化される。
したがって満足度が最大となるとき、max_{i=1}^N k_i-min_{i=1}^N k_i \le 1となる。
均一に配るとき,K%N人が(N/K +1)個配られ,N-K%N人が(N/K)個配られる。従って1個多く配られるK%N人をN人の中から選ぶという組み合わせの問題となるため,解は{}_{N} C_{K mod N}
また,NがKより多い場合はどう配っても満足度が0となるため,どのような配り方をしても良い。
したがってN種類からK個重複を許して選ぶ重複組み合わせと同値です。
K個の○とN-1個の仕切りを使うあれです。従って解は{}_{N+K-1} C_{K}

modのコンビネーションを求める方法はパスカルを使う方法と階乗と逆元を使って求める方法の2通りがあります。
過去にコンビネーションを求めるために使ったコードがあったので後者を使って解きました。


ソースコード:
本番中は勘で均一になったら最大値になりそうとか考えて書いたら通ってしまった。
http://arc039.contest.atcoder.jp/submissions/405872


- C問題「幼稚園児高橋君」

(http://arc039.contest.atcoder.jp/tasks/arc039_c)

問題概要:
スタート地点を(0,0)として、与えられた方角で最も近い未訪問の座標に移動する、という動作を方角が与えられた回数分行います
最終的にどの座標にいるか答えよという問題です。

解法:
想定解と違ったけど解けたのでこっちを書きます。
既訪問リストから次の座標を見つけようとすると1個のクエリにO(N)かかってしまい、TLEです。
座標を二次元配列で確保することもできないのでハッシュか二分探索木で管理することになります。

ここでちょっと考え方を変えると、次に訪問する可能性のある座標は、今までに訪問した頂点に隣接する四方のマスで、未訪問である座標、になります。
つまりある座標に到達した場合はその四方の座標を二分探索木にいれ、到達した座標を二分探索木から削除するという操作を行えば良いです。ちなみに既訪問リストも作っておかないと到達した座標を新たに未訪問リストに追加してしまう恐れがあるので注意です。

で、どうやって次に訪問する頂点を見つけるかというと、二分探索木に対して二分探索を掛けます。
x毎にy座標を格納する二分探索木と,y毎にx座標を格納する二分探索木の二つを使います。
現在の座標から次の座標に移動するとき、上下方向ならx,左右方向ならyが現在の座標と同一なので現在の座標から最も近い座標をこれらを使って二分探索で求めることができます。

ある座標を未訪問リストに追加するとき、両方の二分探索木に同じ座標を入れ、削除するときも両方に対して削除を行う必要があります。

ソースコードでは標準ライブラリのsetでは昇順方向のlowerboundしか用意されていなかったため座標に-1を掛けて降順の二分探索木も作っています。
メモリ使用量が半端ない。
計算量はO(N \log N)です。

ソースコード:
制限メモリの約半分使ってて笑う。
https://arc039.contest.atcoder.jp/submissions/406811