読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

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

Codeforces #331 Div.2 C Wilbur and Points

 (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パズル

数学★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 セグメントフィッシング+

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ヶ月が経ちました

唐突ですが,直前のエントリーで話題にした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. チーム戦が可能なコンテストで誰かと一緒に組んで参加してみたい.

CODE FESTIVAL 2015 予選B

結果:3完 + 40点.

順位:110位

A通過を除くとどうやらギリギリ80位以内に入っているみたいですが・・結果を待つのみ.

code-festival-2015-qualb.contest.atcoder.jp

 

区間を管理する解法ですが,STL不慣れが原因で時間がかかってしまった.コンテスト中の40点解法はlower_boundを使わない方式で,それ以外は特に変わりません.以下ACしたコード.

CodeFes2015B_D

CODE FESTIVAL 予選突破練習会 参加レポート

一度競技プログラミング系のオフラインイベントには行きたいと思っていたので,思ったら即実行という感じでなんだか自分が参加しても大丈夫そうなイベントがあったので参加しました!

atnd.org

若さオーラを感じながら(人通りは少なかったが)久々に駒場に.KOMCEE周辺がかなり様変わりしていました.

参加者の中では自分は間違いなく年長者に区分されていたはず(大学生が多く,高校生も少数いた).

内容は予選のD相当の難易度の問題を解いていこうというもの.問題の内容については特に触れませんが(atndのリンクにある問題を解いていました),一つの問題に対し複数人で意見を出し合うのは5,6年ぶりで気分だけでも若くなれて参加して本当に良かった.

今週末はまあ,あまり気張らずに普段通りいこうと思います.どうやらDPが出題される説が濃厚のようですね.

やはりモチベーションを上げながら続けるにはライバルが必要.