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

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

yukicoder 188/189/190

本番20分遅れで参加して189から解き始めたが実装時間が足らず0完。
yukicoder3問を1時間で解ききるのが今のところの目標です。
yukicoderは時間設定が短すぎる気がします。

188 HAPPY DAY

- 問題概要

2015年のxx月yy日について、xx=yyが成り立つ日の数を出力せよという問題です。

- 解法

カレンダー見て手動で数えました()何月が何日あるとか覚えてません()

- ソースコード

30を出力するだけなのでソースコードはありません()

189 SUPER HAPPY DAY

- 問題概要

M,Dが与えられたとき、1 \le X(=x_1x_2,,,x_n) \le Mかつ1 \le Y(=y_1y_2,,,y_m) \le Dを満たすX,Yについて、\sum_{i=0}^n x_i = \sum_{j=0}^m y_jを満たすX,Yの組み合わせの数をMOD10^9+9で出力せよという問題です。
なぜ10^+9なのでしょうか。

- 解法

全探索をしようとすると値の入力が10^200まであるのでそもそも入力処理すらままならない状態です。
そこで、文字列として入力を受け付け、桁ごとにとりうる数字について考えていきます。この方法を桁DPと呼ぶそうです。
M=1234を例にして考えます。
x_1=1のとき、x_2は2以下となります。
x_1=0のとき、x_2x_3x_4の組み合わせは000~999となります。(本当は0000は含んではいけませんが計算の簡略化のため)

x_1=1のときについて掘り下げていきます。
x_2=2のとき、x_3は3以下となります。
x_2=0or1のとき、x_3x_4の組み合わせは00~99となります。

x_3=3についても同様に考えていきます
x_3=3のとき、x_4は4以下となります。
x_3=0or1or2のとき、x_4は0~9となります。
したがって、0から9,99,999までの桁の和の組み合わせについてあらかじめDPで求めておくことで、
再帰的な手続きによって結果を計算することができます。
再帰呼び出しの回数はO(\log M)です。
桁の和の最大値は9*200=1800ですので、i桁の値の和がjのときの組み合わせ数をd(i,j)とすると、0 \le j \le 1800を満たすについてd(i,j)が既に求まっているとき、d(i+1,k)を求めるのに必要な計算量は計算量は10*1800になります。
以上から、O(10^5 * \log M)で求められます。

190 Dry Wet Moist

- 問題概要

2*N個の数字が与えられます。
N個の数字のペアを作るとき、合計値が負の数となるペアの数の最大値、合計値が0となるペアの数の最大値,合計値が正の数となるペアの数の最大値をそれぞれ求めなさい。

- 解法

二部マッチングなので正しい答えは最大フローを使えば求められます。
しかし計算量がO(N^3)となってしまうので計算量が間に合いません。
貪欲法を使って解く方法を考えます。
合計値が負の数となるペアの数の最大値を求めます。
まず最も小さい負の数を選びます。そのペアとして和が負の数になる最も大きい値を選ぶと未選択の数字に小さい値が沢山残ります。
二番目に小さい負の数を選び、そのペアとして和が負の数になる最も大きい未選択の値を選ぶのが最良です。
このとき、二番目のペアの大きい数字の値は1番目のペアの数字の値以下となることに注目します。
数字列をソートすると、外側から数字が選ばれていきます。左側と右側がぶつかったとき、もう和が負の数になるペアが作れないという合図です。
このO(N)の操作をすることでDry,Moist,Wet全ての数字を求めることができます。
計算量は事前に数列のソートが必要なのでO(N \log N)

- ソースコード

http://yukicoder.me/submissions/21386
入力で与えられる数字の数は2*N個なので注意しましょう(戒め)