ctyl's problem solving

競技プログラミングが主な話題です。

ABC #031D 語呂合わせ

AtCoder

問題：

abc031.contest.atcoder.jp

本番中なぜか3進数列(ll.64-67)を作るところでずっと詰まっていて実装が終わらなかった．こういうシンプルな全探索が実はbitDPへの登竜門となっているのは面白いと思いました．

C++は文字列の取り扱いがやりにくいなあという印象があるのですが，他の言語はどうなんでしょう？

ABC031D

SRM #673 Div.2 Hard BearPermutations2

このレベルの問題を1時間で解くにはまだ修行が足りないと感じました．

解法はDP(Editorialを大分参考にしました)．

要素数 nの場合のスコアをdp[n]とする．求めるべきは dp[N]．

下の図のようなシチュエーションである頂点から左A個のヒープと右B個のヒープに分断されるケースを考える．こうなるケースは _{n-1}C_{A}通りの組み合わせがある．A>0かつB>0のときは必ず最初の分岐のスコアが左右のヒープの中のスコアに合算される．(AとBどちらかが0のときはdp[n-1]が足される．)最初の分岐のスコアは根(図の丸)からそれぞれのヒープまでの距離として独立に計算できる．

  • ヒープAに関連するスコア

ヒープAのみのスコアは _{n-1}C_{A} \cdot {B!} \cdot dp[A]

根からヒープAの根までのスコアは _{n-1}C_{A} \cdot A! \cdot B! \cdot \frac{A+1}{2}

ここで\frac{A+1}{2}とは根からヒープAまでの距離の平均である．(1からAの値までが全て同じ数づつ現れるのは明らか)

  • ヒープBに関連するスコア

ヒープBのみのスコアは _{n-1}C_{A} \cdot {A!} \cdot dp[B]

根からヒープBの根までのスコアは _{n-1}C_{A} \cdot A! \cdot B! \cdot \frac{B+1}{2}

これを全てのA=0,1,\cdots,n-1において合算するとdp[n]となる． 整理すると

dp[n] \displaystyle = \sum _{A+B=n-1}^{} _{n-1}C_{A} (B! \cdotdp[A] + A! \cdot dp[B] \displaystyle + A! \cdot B! \cdot \frac{n+1}{2})

f:id:ctylim:20151121001218p:plain

SRM #673 Div.2 Hard

プラグインをCodeProcessorからKawigiEditに変えてみた．IDEを使っている身としてはこちらの方が断然良いですね！

KawigiEdit Documentation

CODE FESTIVAL 2015 参加レポート

Events AtCoder

先週末に自分にとって初の競プロオンサイトコンテスト"CODE FESTIVAL 2015"に参加しました．至れり尽くせりの2日間で，競技プログラミングでここまで本気で企画したリクルートさんすげえ，と感じました．

本戦に関しては時間内ぎりぎりに5完し，総合156位．もっと速く解けていればもう少し良い順位が取れたという思いもありましたが，2ヶ月間少し頑張っただけで2日分のコンテンツを楽しむ権利が与えられた，と思ったら気がラクになりました．(パーカー届くの楽しみにしてます．)

2日目リレーに関しては順位が高いほど後ろの問題に割り当てられる(割り当ては順位関係なく自由だけれど，どこのチームも順当にそうなったのでは)わけですが，強い人が難しい問題を考察している様子が間近で見れたのは最大の収穫だったかもしれません．

各コンテンツの様子などは他の参加者の記事に一任することにして，最後に所感を書き並べておきます．

  • 音ゲーフリープレイの場所が普通にゲーセンっぽくて少しワクワクした．
  • 案外スケジュールがタイトすぎて，セッションなどを聞いていると和エリアに滞在できる時間がほとんどなくなる．
  • コード川柳でコード書いている人がほとんどいない(それはそうか)
  • エキシビションマッチで強い人の問題解いている様子を見ていて，自分がやっているのは「競技」ではないと感じた

総括：もっと強く，もっと速くなりたい．

短文ですが，とりあえずここまで．来年から学生で無くなってしまうので，参加できないのが本当に残念です・・

Codeforces #331 Div.2 C Wilbur and Points

Codeforces

(x,y)が与えられた点集合に含まれているならば x'\leq x,y'\leq yを満たす全ての x',y'もその集合に含まれるという条件を読み落とし，問題を難しく解釈し結局時間内に解けなかった．注意力不足を感じた回でした．

解法は貪欲+2分探索．計算量はO(n\log n)．

Codeforces #331 Div.2 C

yukicoder No.226 0-1パズル

yukicoder

数学★4．というよりは実装★3.5くらい・・？の問題．

問題：No.226 0-1パズル - yukicoder

解法：解説ページにもあるように，仮に第1行目が0または1が一回でも連続したら第2行め以降はuniqueに決定する．uniqueに決定しない場合は0101...か1010...と交互に並ぶ場合．その場合は各行のセル情報をチェックし，任意の行が0101...か1010...で書けるかを確認する．例外の処理を丁寧に実装するところが肝．(下の解答例では，最初はわかりやすく書こうと努力したが途中からそれを放棄した感が出てしまった・・)

yukicoder No.226

P.S. 明日はCODE FESTIVAL本戦ですね！

ARC028D 注文の多い高橋商店

戻すDPというのをyukicoderで知ったので，理解を深めるために類題をやってみました．

arc028.contest.atcoder.jp

yukicoderの該当問題へのリンク： No.155 生放送とBGM - yukicoder

時系列順だとyukicoderよりもARCが先のようですね． クエリの入力が1000000あるので，速い入出力を使いましょう．1000000個の入力だと入出力次第で1秒くらい実行時間に幅が出るようですね．余談ですが，静的配列と動的配列の宣言の速度はそこまで大差ないようです(動的配列のほうが少し遅いですが，入出力の差に比べれば誤差です)

普通のDPで出そうな問題： {N}種類の商品がそれぞれ {A_i}個づつあります．但し同じ種類の商品はお互いに区別できないものとします．このとき合計M個買うには何通りの買い方がありますか．

このときに計算するmatrixは {dp(i,j) = \sum _{k=0}^{A_i}dp(i-1,j-k)} のようになります．計算量は {O(MN)}です．

さらに条件としてある1種類の商品を買う個数が指定されたクエリ形式になったのが今回の問題です． 詳しくは公式の解説スライド参照なのですが， {dp(i-1, j)}を {dp(i,j) = \sum _{k=0}^{A_i}dp(i-1,j-k)} から逆算する要領でその1種類の商品を買う前のmatrixに戻すのが「戻すDP」の肝です．それを {O(1)}でやらなければいけないので，うまく {dp(N,:)}のみの行を用いて工夫して計算しなければいけません．とはいえ紙に書いていけばこの部分は思いつきますね(自分は初回 {O(M)}の処理を書いてTLEしましたが・・)．

ARC028D

yukicoder No.259 セグメントフィッシング+

yukicoder

BIT★4．BITを学んだ後に解く問題でBITやるだけ，では物足りない方にはオススメかもしれません．

右向きに場所{0,1,\cdots,N-1}で泳ぐマスと左向きに場所{N-1,\cdots,1,0}で泳ぐマスを連結させ長さ{2N}のBITを用意する．LコマンドやRコマンドに相当する挿入は{t = 0}のときどこにいるかを計算する．Cコマンドでは指定する範囲がBITでは両端を含むような時があることに注意すること．もちろん右向きと左向きがあるので最低でも指定する範囲は2つある．

No.259 セグメントフィッシング＋ - yukicoder

yukicoder No.259

最近は木構造をAOJなどでやっています．画像処理とかで使うようなアルゴリズムもあるので，教養として抑えておきたい部分もあるかも．(本当は学部時代にやっておくべきなのですが・・)　RMQなども記事化できるといいなあ(わかりやすいreferenceがたくさんあるのもあってなかなか記事にするモチベーションが)