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

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

ABC#005

多忙のため記事の更新が遅れていますが一日一題片付けています()

- A問題「おいしいたこ焼きの作り方」

(http://abc005.contest.atcoder.jp/tasks/abc005_1)

問題概要:
持ってる小麦粉からたこ焼きが何個作れるかを計算して出力する問題です。

解法:
整数型の除算による余りの値の切り捨てをそのまま利用すればOKです。

ソースコード:
http://abc005.contest.atcoder.jp/submissions/340226


- B問題「おいしいたこ焼きの売り方」

(http://abc005.contest.atcoder.jp/tasks/abc005_2)

問題概要:
一番新しくできたたこ焼きが何秒前にできたか出力する問題。
出来立てを食べるのはいいけどそれ以外の冷めたたこ焼きはどうするんでしょうね。

解法:
i-1番目までのたこ焼きができた時間の暫定最小解を保持し、i番目のたこ焼きの時間との最小値をi番目までの暫定最小値としてこれをNまで繰り返す。
O(N)で実現。

ソースコード:
http://abc005.contest.atcoder.jp/submissions/340223


- C問題「おいしいたこ焼きの売り方」

(http://abc005.contest.atcoder.jp/tasks/abc005_3)

問題概要:
ある時間に来たお客さんに対して作ってからの時間がT以内であるたこ焼きを売りつける問題です。たこ焼きができていなくてお客さんを待たせてしまってもアウト。


解法:
たこ焼きができた時間+Tを賞味期限と考えましょう。お店としては一番賞味期限が古いけどセーフなやつを売りつけるのが一番効率いいです。
i番目のたこ焼きができる時間をitem[i],t番目のお客さんが来る時間をman[t]として配列に格納します。itemとmanはそれぞれ昇順にソート済み。
i=0番目のお客さんが来ました。時間はman[i]です。
このとき、この時間よりもT秒以前にできたたこ焼きは全て捨てます。tをたこ焼きの番号とすると
man[i]-item[t]>Tを満たすたこ焼きは全て捨てることになります。
man[i]-item[t]<=Tを満たしてかつお客さんが来る前に出来上がった一番古いたこ焼きを売りつけます。
売れなかったらflagをfalseにすればOKです。
計算量は二重ループになっていますがtは常に増加するので配列itemへのアクセスは最大でN回です。
したがってO(M+N)

ソースコード:
http://abc005.contest.atcoder.jp/submissions/340220


- D問題「おいしいたこ焼きの焼き方」

(http://abc005.contest.atcoder.jp/tasks/abc005_4)

問題概要:
焼く部分によっておいしさが変わる謎のたこ焼き器を使ってたこ焼きを作ります。
また、各従業員は技量によって同時に焼けるたこ焼きの数が変化します。
各従業員の一度に作るたこ焼きのおいしさの最大値を求めましょう。

解法:
典型的な領域分割?分割統治?の問題です。子問題を解くことで大問題を解くことができ全パターンを高速に計算できます。
rect[i][j][w][h]を座標(i~i+w,j~j+h)の領域で焼いたときのたこ焼きのおいしさの合計と定義すると、
rect[i][j][w][h]=rect[i][j][w-1][h]+rect[i+w][j][0][h]
例 rect[i][j][3][2]=rect[i][j][3-1][2]+rect[i+3][j][0][2]

■ ■ ■ ■■ ■ ■ +
■ ■ ■ ■■ ■ ■ +
■ ■ ■ ■■ ■ ■ +
という風に子問題が解けていればO(1)で計算できます。
これはあらかじめrect[i][j][0][h]を全て求めておくことで上記の式の計算を行うことが可能になります。
rect[i][j][0][h]の計算も同様にして
rect[i][j][0][h]=rect[i][j][0][h-1]+rect[i][j+h][0][0]
という風に子問題から解くことでO(1)で計算できます。
rect[i][j][0][0](1マス分のたこ焼きのおいしさ)の値は入力で与えられるので、
これをもとにrect[i][j][0][h]を全て計算し、rect[i][j][w][h]を解くという手順で解けば各領域におけるおいしさの合計を求められます。
この操作の計算量はrect[i][j][w][h]を全てO(1)で計算できるので、O(1*N^4)=6.25*10^6程度です。
次に、各面積についての最適解を計算します。面積がk以下のときの最適解をopt(k)とすると
opt(k)=max(opt(k-1),面積がkのときの最大値)というように解けるのでこれもDPもどきでO(N)で解けます。
面積がkのときの最大値はrect[i][j][w][h]が確定したときに(w+1)*(h+1)の面積の暫定最大値がO(1)で求められるはずなのでそこで求めておきましょう。

ソースコード:
http://abc005.contest.atcoder.jp/submissions/340219