naoya_t@hatenablog

いわゆるチラシノウラであります

〈企業コン埋め〉500点問題篇

粛々と埋めて参ります

12/25(火)

CODE FESTIVAL 2016 qual B

C - Gr-idian MST (500)

  • 縦方向に1本、横方向に1本、少なくとも貫通させないといけない
    • 例えばL字型にまず道を敷設
  • あとは左下からDP的に、下ないし左への最短路を繋げて行きたい (\min(p_i,q_j))
    • でも1つずつやっていくとO(N^2)でアウト
  • i,j(というかp,q)の順番はどうでもよさそう。ソートしてしまおう。
  • ある j について、p_i\le q_j なものについてはp_iを採用、そうでなければq_jを採用
    • jについての総和は p_i\le q_j な範囲のp_iの総和 + q_j×(p_i\gt q_jp_iの個数) で求められ、事前に累積和を求めておけばO(\log W)で求められる。
  • これをすべてのjについて求めれば良いのでO(H\log W)ないしO(W\log H)で求まる

→AC
https://atcoder.jp/contests/code-festival-2016-qualb/submissions/3874204

解説読んだ

pとqをソートした後に編み込んでいくような感じで解いてる。なるほど。
(先頭同士で小さいほうから貪欲に使っていく感じ)

12/26(水)

CODE FESTIVAL 2017 qual B

C - 3 Steps (500)

最初こんなん解けるかいって思ったんだけど
五角形・六角形・七角形とか書いてて
あれ、奇数だと全結合になりがち?偶数だと1個おきにしか繋げない?

そうこうしているうちに「接続可能な行き先は奇数番目のみ」ということに気づいた
そこから

    • 二部グラフにできる場合:偶数番目の任意のノードから奇数番目の任意のノードに辺が引ける
      • (偶数サイドのノード数)x(奇数サイドのノード数)- M が答え
    • 二部グラフにできない場合(偶数番目同士、あるいは奇数番目同士の接続が最初からある場合):全結合できてしまう
      • N(N-1)/2 - M が答え

という結論に行き着いた。

ノード数が3以下の場合は増設不可能なので0を返す。

→AC
https://atcoder.jp/contests/code-festival-2017-qualb/submissions/3877245

解説読んだ

同様


12/27 (木)

みんなのプロコン 2018

C - 駆引取引 (500)

問題の意味がさっぱり読み取れず悩んだ

  • 「高橋くんが持っていて売ることのできる物」と「青木くんが持っていて売ることのできる物」は別物。(そういうレベルで読めてなかった)
    • 高橋くんが売ったものを青木くんから買い戻すことにはならない
    • 売る順番は決まっているので、n個売るとしたら「先頭からn個」以外の選択肢はないし、0\le n\le Nである
  • 「高橋君は得点を最大化するように、青木君は得点を最小化するように行動する」というのがわからない
    • 高橋くんはn個(0\le n\le N)売って出来た金で買うだけ。最大化するといってもN+1通りのベストを取るだけ。
      • だから高橋くんの行動については「N+1通り試す」という点以外には考える必要がなさそう
    • 青木くんには高橋くんがどのタイミングで売りを止めるか予測できない?
      • 高橋くんがn個売った時点で、高橋くんがn個で止める場合 〜 N個全部売り切る場合 までがありうるけど…
      • 高橋くんがn個売って止める(その時点での高橋くんの持ち金はわかっている)とき、青木くんは高橋くんに都合の悪いN-n個をチョイスして店頭に並べる?

N=18とか言っても2^{18}=262144通りのパターンがあってそれに18ビットを掛けた O(N2^N)なループが回るイメージかな

  • とりあえず2^N\le 262144通りの商品パターンの金額と価値を計算しておいて
  • n個売って得た金で買える額が最小になる販売停止パターン (_NC_n通りの中から)をbitDP的に求めて
    • 0\le n\le Nについての最大を答える(のでO(N^2 2^N)かな)


サンプル1〜3までは合うんだけど、サンプル4が合わない…それでずっと悩んでた

自分が求めたのは「n個売って得た金があって、店舗の品揃え集合が与えられたときに得られる最大の価値」で、これは高橋くんと青木くんの都合は入っていない。nを動かして、各nにおいて価値が最小になるものを選び、それが最大になるnの時の値を答えていたわけで。(※これはこれで後の計算に使える)

解説読んだ

どのような順序で商品が廃止されたかは重要ではなく、今現在どの商品の販売が停止しているか、だけが重要であることは明らかでしょう。

そうだと思ってたんだけど、だったら自分の実装で通るのでは?意味分からん

はまやん先生の記事の実装を見て理解

青木くんの最善手の取り方がまずかったのか…

  • 青木くんは各段階において、どの商品の販売を停止するかについてすべて考える
    • ある商品の販売を停止するとして、

f(n,S) = n個売った時点で商品集合がSだったとして獲得できる価値の最大値、としよう。

求めたいのは f(0,2^N-1)、即ち、0個売った時点で商品集合が(全商品)だったとして獲得できる価値の最大値である。

このf(n,S)再帰的に求めることができる。

f(n,S)
= max( n個で売り終わって、持ち金で店頭在庫Sの中から買った場合の最大値,
n個で売り終わらなかった(n+1個目も売ることにした)場合に獲得できる最大値 )

n+1個目も売ることにした場合に獲得できる最大値は青木くん側のムーブ、即ちどの商品の販売を停止したかが絡んでくる。
青木くんは販売停止する商品のチョイスすべてを考慮して決めたい。

max() の第1項は「n個売って得た金があって、店舗の品揃え集合が与えられたときに得られる最大の価値」なので、前にbitDPで求めたものが使える。(dp[n][S]としよう)
第2項は、n+1個目に販売を停止する商品をkとして、可能なすべてのkについてf(n+1,S\setminus k)を求めた中の最小値が(青木くんが提示する)ムーブの結果である。

  • f(N,\emptyset) = 0
  • f(n,S) = max(dp[n][S], min f(n+1,S\setminus k))
  • 求める値はf(0, 2^N-1)

→AC
https://atcoder.jp/contests/yahoo-procon2018-qual/submissions/3882152

n個の商品集合からn-1個の商品集合への遷移はすべてが可能なわけではないので、単に dp[すべてのn][N-n]個の商品から成るすべてのS] を見るのとは違った結果になる。自分の元の実装で計算が合わなかったのはそういうことだろう。

まとめ

青木くんは「店舗の品揃え集合」を可能な限り高橋くんに不利なように遷移させたいのだけれど、青木くんのその意思をどう実装したらいいかわからなかった

↓↓↓↓

すべての可能性を計算させ(実際はメモ化再帰なりDPなりで省エネできる)た上で、高橋くんにとって一番都合が悪い結果を引かせればよい


という視点のトランスフォームをすれば良い、というのが今回の学び。