Competitive Programming Advent Calendar 2014の記事です。自分はかつてTopCoder Marathon Matchに参加していた時期があったのですが、今回はその感想を書きます。

Competitive Programming Advent Calendar Div2013の12月2日の分です。ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。 はじめに segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです（定番中の…

メモ。 立命館合宿企画者さまとAOJの管理者さまには大変お世話になりました。 コンテスト参加者のみなさまと、かなり無理なスケジュールを押し付けてしまったスタッフのlyoz君とfura2君と、インフラ用意してくれたhasi君と、それからついでに自分もお疲れさ…

問題概要 長さL(スワップして回文になるようにしたい。必要なスワップの最小回数を求める問題。回文にできないのであれば指摘する。 解法 奇数回現れる文字が2個以上あれば不可。それ以外のときは、以下のような手順で最小コストの回文が得られる(未証明)。 …

蟻本の一番最後に載っている問題。 最終的には蟻本と同じになるのだけど、前回の記事で書いた方法でより機械的に解いてみる。 まず前段階として、問題のサイズはそんな大きくないし、基本的には?の部分を開催するかどうかという2択から選ぶのだから最小カッ…

様々な問題をLPやその双対を駆使して解きまくっているwataさんが格好良すぎるので、ちょっといくつかの最小カットの問題を解き直してみた。 私はLPにも最大流にも詳しくないので、完全ユニモジュラとか言われても「成り立ってることを祈りましょう」くらいし…

Competitive Programming Advent Calendar Div2012の12月4日分の記事です。私はこの1年でいくつかのプログラミングコンテストに主催者寄りの立場で関わって来ました。具体的には、 OUPC HBPC SuperCon Autumn Fest JAG主催のコンテストのいくつか などです。…

コンテストのときに使ったりしているライブラリやらスクリプトの一部をgithubに置くことにした。 ライブラリはドキュメントの扱いを決めかねているのでしばらく放置。スクリプトまわりは、今使っているビジュアライザをもうちょっと改良してから上げる予定。…

問題概要 W*H(W,H 解法 幅優先探索をN回やるので十分。もう少し賢いやり方があるかもしれない。

問題概要 [1..K](K 解法 個数制限なしナップサックと同様にやればよい。最大ケースでは64bitでも足りないので多倍長が必要。

問題概要 パスカルの三角形風に数字が並んでいる。上から斜め下のどれかに移動できる。途中で拾った数の和を最大化する問題。 解法 典型的な動的計画法。色んな所で類題が出題されている。

問題概要 [0..9]の部分集合が与えられる。二つの集合に分けて適当に順序を変えて10進数の数字を作り差を最小化する問題。 解法 数が少ないので全探索が間に合う。桁数決め打ちで分けてnext_permutationくらいでも余裕。

問題概要 [1..N](N 解法 next_permutationで意外と早く見つかる。

問題概要 連結グラフが与えられる。ある点を中心とした距離の近いほうN個の平均長の最小値を求める問題。 解法 真面目に幅優先で求めて十分間に合う。

問題概要 頂点数N( 解法 クエリiの後にクエリjを処理できるかどうかで辺を張ってDAGを構成し最小パス被覆を求めればよい。

問題概要 n( 解法 平均値について二分探索する。

問題概要 01のならんだ文字列が与えられる。自マスと隣接マスが0の個数を数える問題。

問題概要 N( 解法 大きい数にf(x)=sqrt(2*x)をたくさん作用させられるようにするため大きい方から貪欲に選べばよい。

問題概要 [0,H)*[0,W)の中に軸に平行な長方形をN( 解法 座標圧縮してflood fillすればよい。長方形を配置するのはいもす法を使う。

問題概要 n( 解法 見るからに二分探索+2SAT風。

問題概要 T個のテストケースに対して答がY/Nという結果がT個ならんでいる。完全一致していたら正解でそれ以外は不正解となる。 解法 どれが答になっているか全探索する。全部合わなかったら全部NOと出力する。

問題概要 階差数列の和が一定数を越えるか判定する問題。

問題概要 N( 解法 平面走査でやるのはすぐに見えるけど、簡潔な実装方法を選べないと厳しい。Range Sum Queryで区間に足し込み、新たに線分を加えるときオーバーラップしているかどうか判定する方法でやった。走査線を左右、上下の4方向に動かせば全部検出で…

問題概要 頂点数n( 解法 既に通った頂点集合と今いる頂点を組にしてDPすればよい。ただし、適切なトポロジカル順序をつけるのが難しいのでベルマンフォードのように適当にn回回して緩和する。

問題概要 n( 解法 約数の個数については前処理で篩っぽく計算できる。どの子が取り除かれるかについてはBITで計算する(割と典型手法)。

問題概要 盤面サイズ250のライツアウトを解いて最短かつ辞書順最小の解を出現する。 解法 連立一次方程式。最短かつ辞書順最小が難しいが、問題文をよく読むとランク落ちしないと書いてあるので最小も何もなく解は一意に定まる。

問題概要 A,G,C,Tからなる長さL[i]( 解法 ICPC Asia Regionalなどでお馴染みのShortest Super String。他の文字列に包含される文字列を消去した上で巡回セールスマンっぽいのを解けばよい。面倒なのは辞書順最小の構成だけど、これは例によって前から順番に…

問題概要 H*W(H,W 解法 基本的には分裂するgrundy数なんだけど、斜めのチョコレート割の扱いに困った。y+xとy-x(+W)の下限と上限を持っておけばうまく処理できる。

問題概要 頑張って問題文を読むと、奇数個の部分和になりうるかつ偶数個の部分和になり得ない値の個数を求める問題だと解釈できないこともない。 解法 計算量O(N*M)だけど定数が軽いのと多分テストケースが弱いのとで普通にDPやって通る。

問題概要 2次元ボード[0,2^31)*[0,2^31)がある。その内N( 解法 平面走査する。イベントラインは区間への加算をサポートするRMQで持っておけばよい。つまり、点(x,y)を追加するとき[y,y+H)に書かれている数値を足し込む。削除する時は負の値を足し込めばよい…