ctyl's problem solving

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

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

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

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

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

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

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がたくさんあるのもあってなかなか記事にするモチベーションが)

競技プログラミングを始めて2ヶ月が経ちました

General

唐突ですが，直前のエントリーで話題にしたCODE FESTIVAL予選B，通過していました．久しぶりにこの種類の嬉しさを噛み締めています．というのも，大学に入ってからは評価というものは公正でないものも多く(これは考え方の問題ですが)，評価の仕方も教官によってまちまちだったのですが，今回はオートジャッジによる絶対評価と順位が1人単位でわかり，1つ順位を上げる価値が場所によってはとても大きくなるというもので，大会ならではという感じがします．自分がかつて参加した中で一番近いのだと数学オリンピックがそれにあたりますね．さすがにオートジャッジではなかったですが・・

決勝はベテラン勢が上位を制するのは見えているのですが，それでもあと半月あがいて納得できる成績を残したいです．具体的な数値目標としては上位半分(つまり100位以内)に入ることでしょうか．

かつて数学の大会の虜になったのも，中学入りたての当時とりあえずと参加した数学の大会で学内唯一予選を突破し決勝では運良く準優勝したのが，その後高校卒業までモチベーションを上げ続ける最大のトリガーだった記憶があるので，この年ながら競プロでもいい流れを作っていきたいなどと思っています．

さて，競技プログラミングを始めて2ヶ月が経ちましたが，今のところの到達度を書いておきます．もし競プロ始めたての方が万が一この記事を読まれていたら参考にしていただけると嬉しいです．

  • TopCoder Rate: 1131(緑, Highest)
  • Codeforces Rate: 1619(青, Highest: 1661)
  • ABCは全完できるようになった(始めてから皆勤で全回全完)
  • yukicoderを★3を中心に70問弱解いた(知らないアルゴリズムに関しては解説や他人のソースコードを見ながら学んだ)
  • CODE FESTIVAL 2015予選突破

当然ですがまだまだコーディングスピードや思考速度は遅く，あらゆるコンテストに出て上位を狙う，というアクロバティックなことはできないので，TopCoder, Codeforces, AtCoderを軸としてちょっとづつ手を広げられれば良いと思っています．

アルゴリズム的な知識や実装技量に関しての自己評価も載せておきます．

  • 実装系の問題は思考終了から実装に落とすまでの時間がまだ長い
  • STLのコンテナのメンバ関数の扱いは未だ不慣れ(mapにlower_boundがあることを知らなかったり)
  • DPはメモ化再帰方式だったり更新則が少し変わると対応できないことが多い
  • DFS，BFSに関しては理解したつもりだが，まだコンテストでの使用経験が少ない
  • Binary Search, Binary Index Treeなど計算時間が対数時間だったり1クエリに対して対数時間の処理で済むアルゴリズムやデータ構造は未習部分が多い．Segment Tree早く理解実装できるようにならないと・・
  • TLEが起きなさそうか起きなさそうかの見極めが甘い
  • 貪欲に関してはあまり深く考えずに使うことが多い
  • 整数・行列の累乗やmodに関する処理に関してはある程度は慣れた(気がする)

今はyukicoderを中心に各種アルゴリズム習得に利用しているのですが，AtCoderの問題は問題文も理解しやすく問題もいくらか洗練されている気がするので，ある程度までやったら今度はARCの過去問を中心に進めていく予定です．

 

 関連サイト：

http://codeforces.com/

https://www.topcoder.com/

AtCoder (アットコーダー)

http://yukicoder.me/

 P.S. チーム戦が可能なコンテストで誰かと一緒に組んで参加してみたい．