TopCoder SRM605

なんで DP 2 個なんだろう

250

ハンバーガーがたくさんあり，それぞれ type と taste が決まっている．
このうちの 0 個以上を食べる．このときのうれしさは，(type の種類数) * (taste の和) である．最大値を求めよ．

type ごとに，使った時の得られる taste の最大値を求めて，それをソートして種類数を全部試す．

450

1〜2N の数を 2 つの N 個ずつの集合 A, B に分ける．A の i 番目に小さい数と，B の i 番目に小さい数の差は K 以上でないといけない．分け方は何通りか．

dp[A に入れたものの数][B に入れたものの数][最近 K-1 個の様子] として，1 から順に入れる DP．
A と B に今まで同じだけ入れたときは，次の数はどちらでも自由に入れることができる．
A のほうが多いときは，A に入れるのはかまわないが，B に入れるためには対応する A が十分前に入れたものでないといけない．それは最近 K-1 個の様子を見ればわかる．B のほうが多い時も同様．

1000

1〜N の並び替えの列に対して，「ある範囲の数をすべて，その範囲の最大値で置き換える」ことが K 回までできる．何通りの列が考えられる？

最初に a が b より前に出てくるときに，後で a が b より後ろに出てくることはありえない．
また，ある数を最初の位置から，自分より大きい数をまたいだところに置くような操作は存在しない．
一方，最大値が小さいものから順に操作を行うことにすると，列が上の数の置ける範囲の制約と登場する数の順序の制約の両方を満たしてさえいれば，何回かの操作でその列に変えることができる．
操作の回数を消費しないのは，「最終的に列に登場しない」もしくは「最終的な列に登場するが，最初からあった位置のみである」ときである．
これは dp[位置][次に使おうとしている数][操作した数][もう操作数を数えたか] で DP すると求められる．

結果

250 で謎の貪欲があったので落として +50

ooo +50 1207.92 (1 位)
rating: 3172 -> 3261

TopCoder SRM597

250

文字列 A に対して，「1 文字選んで先頭に持ってくる」操作を行うことができる．A を別の文字列 B に変えるために必要な操作の回数は？

A の部分文字列で，B の後ろのほうに一致しているものの最長の長さを求める．

600

凸多角形が与えられるので，その内部（辺上は含むが頂点は含まない）に頂点が整数座標であるような別の凸多角形を取れるか判定せよ．という問題になる．

内部の点が一直線上にあるかどうかを判定する（と思う）．落ちた

900

2*M のマス目を，赤，緑，青のいずれかで塗る．同じ色が隣り合ってはいけない．また，どの 2*2 の部分についても，赤，緑，青のそれぞれが 1 マス以上なければならない．赤，緑，青のマス数が与えられるので，塗り方の場合の数を求めよ．

2 列組で考えると，「赤緑」「赤青」「緑青」のどれか（逆も含む）である．一番上の行でこれらを置く向きを決めると，それ以下は全部自動的に決まる．2*2 の部分についての条件より，同じものが隣り合ってはいけない．それぞれの必要個数は簡単に求められる．
つまり，A, B, C を決められた個数，同じものが隣り合わないように並べる場合の数 * 2 を求める問題になる．
あとは，場合の数をがんばって求める．

結果

mid を適当に眺めていたらおかしいのがあったので落として +50
mid 落ちた＞＜
oxo +50 788.04 (4 位)

rating: 3126 -> 3172

天下一プログラマーコンテスト 2013 本戦

コンテスト前

• 精神統一を実施していないことに気づきあわてて http://www.nicovideo.jp/watch/sm17720979 を視聴する（ただし時間が足りなかった）

A

• A 問題でしかも 40 点だしどうせ簡単な方法だろう
• この mod とかいうやつもフェイクに違いない
• と思って探索を書き始める
• どう考えても 2^49 以上答えあるし無理だろ
• まじめに bit DP を書く
• 通る

B

• 読む
• イメージわかない
• 手ですこし試す
• よくわからん
• よくわからないときは「きっとトリックがある」のでとりあえず 2 つのシャッフルを書いて試す
• なんかリフルシャッフルとカットは簡単な規則で交換できそう
• r 回リフルシャッフルするとして、最初に r 回やってしまってその後カットを(このとき勝手にカットの数を 1, 2, …, 2^r 倍にしてよい)行う、という場合だけ考えればよい
• 書く
• 通らない
• 何回か直す
• 通らない
• リフルシャッフルしたあとに、「あとはカットだけで直せる」状態にしないといけないが、1 度そうなったあとにまたリフルシャッフルを繰り返して同じ状態にしてからカットをしたほうがうれしい場合がある、という罠に気づく
• 書く
• 100 点
• あとで考えよう

D

• とざんが爆速で通していてやばみを感じる
• 読んでみたら包除原理やるだけっぽい
• 書く
• バグる
• C(3, 1) = 9 とか出てきてファッってなる
• 直し、C の計算を O(1) でできるようにする
• 通る

• B に戻ってきて、いろいろ試す
• 試しているうちに通る

• 残るは C と E、どっちにしよう？
• E の満点とか解ける問題に見えないので、C を書くか E の 60 点を書くか
• E のもう 60 点は最大流の場合の数を求めるっぽいけどそんなん知らんし書けない
• とりあえず E の入出力くらいは書いておいた

C

• 書けば通りそうだったのでがんばって書く
• 0 点
• 盤面は正方形に限らないらしい
• それにしても 0 点なのはおかしい
• よくみたら、「上に来る辺の番号」じゃなくて「最初上だった辺の位置」を答えなきゃいけないらしい
• 直したら 26 点が来る
• 長方形でも動くようにして 142 点

E

• C で 18 点取りに行くより E で 60 点とったほうがうれしい
• C, E で迷っている時に E を読んで部分点解法を想像しておいたので、set を使って DP すればよさそうだとわかっていた
• 書く
• 60 点

• C あと 18 点増やせる気がしない
• 内部、辺、角に分類して試すピースを限定する方法をやろうと思ったけどバグる
• 少しだけ限定する
• 142 点から増えない
• やめた

ICPC 系問題 9/6

Longest Increasing Sequence (AOJ 2430)

N(N+1)/2 個の区間を数の和で降順ソートして、ある点から終点までで LIS 分割するときの最大の分割個数で DP。O(N^2 log N)

Hakone (AOJ 2439)

"-" は無視し、上位から順に見る。

dp[位置][D のために空けておいた場所の数][U で使った場所の数]。「U で使った場所の数」は省略してもよい。

Brilliant Stars (AOJ 2291)

明らかに、連結成分ごとに独立して考えてよい。がんばると、各連結成分ごとに、「その成分の点すべてに接続しているような点 P」が必ず 1 つ以上存在することが示せる。この性質は、点を勝手に何個か取り除いても成立する。
ある連結成分がクリークならば、クリークを構成する点を勝手に 1 つ選んでよい。さもなくば、その成分についての解は 2 以上であるから、P は問答無用で取り除いてよい。残ったグラフに対して同じことを繰り返し（ただし、グラフが複数の連結成分に分かれるかもしれない）クリークになるまで繰り返す。

Psychic Accelerator (AOJ 2226)

この問題を解くために、次の問題を解く：

線分上で物体をできるだけ高速に移動させよ。物体には線分に沿って [-a, a] の範囲の加速度を加えることができる。また、線分上のいくつかの点には速度制限があり、その点を通過する際の速度はその制限速度を超えてはならない。

加速度は -a, a のみを用いればよいことはほぼ明らかである。
等加速度運動は、t-v グラフだと直線として簡潔に扱えるが t-v グラフでは位置の速度制限を扱うことができない。x-v グラフでは等加速度運動が曲線になり分かりづらい。そこで、横軸に x、縦軸に運動エネルギー（実際は v^2/2) をとったグラフを考える。
このグラフの上では、加速度 a の等加速度運動は傾き a の曲線で表され便利である。物体の速度のグラフは、できるだけ運動エネルギーの高い位置を通るべきである。
速度制限のない点における速度は、「前の速度制限のせいでこれ以上速くできない」もしくは「これ以上速くすると次の速度制限にひっかかる」のどちらかの要因により制限される。これを別々に考える。前者は、区間での最大の v^2/2 を ax+t で表すとし、t を区間ごとに順次更新すればよい。後者も同様。
この 2 つの制約により、各点での可能な最大の v^2/2 が求まる。あとは 1/v dx を積分してやれば答えが出る。

補題が解けると、元の問題は次のようにして解ける：

• まず、がんばって円弧を補完する
• 円弧上では、加速度の制限から速度の制限が生まれる。また、円弧上では加減速ができない。そのため、円弧は速度制限つきの 1 点につぶす
• 補題を解き、円弧上ではつぶした制限速度点の速度で動く

JOI 夏季セミナー 2013 参加記

day 1

• 池袋で適当にあわててから東上線に乗る
• 14:00 快速が JOI 列車だった

• NWEC 着
• (チューター, 生徒) 自己紹介したり本決めをしたりする
• 携帯ストラップを名札につける
• 近似の本が生徒の数 - 1 しか存在しない問題が起きてた
• 誰も担当の本選ばなかったらどうしようって思ってたけど決まったので安心

• セミナーの前にまずネットワークの機械を設置するが、なぜか無線アダプタが 1 個しかなくてつらぽよする
• セミナーでは、まず最初の整数論を読まないと後ろが読めないことがわかっていたので、まずそこを読んでもらったり説明したりする
• 正直本では整数論の説明がやけに難しく書いてあったので、ここだけ他の教材を用意してもよかったかもしれない

• 夜は談話室に人が集まる
• NWEC は夜は密施設になり宿泊棟も密建物になるという闇を知る

day 2

• セミナーでは、適当に本を読んでもらい、夜説明してもらった
• 本にマスハラを受けた（「示せる」と書いてある事実を示すのにB5 1 面かかった）
• AES 実装つらぽよそうだなと思う
• 集合知班がかなりやばい数式を白板に書いていてやばぽよを感じた

• ／^o^＼サファリパーク
• ＼ばばばばーん／

day 3

• あさめしでご飯大盛りにしたら倍量くらいになってやばかった

• セミナーでは、また別の部分を選んで読んでもらい、午後説明してもらった
• その間チューターは質問に答えたり 2 次ふるい法を実装したりしてた
• 試し割りの 50 倍くらいの速度が出てうれしい
• 生徒が多倍長を使ってミラーラビン実装しててすごいと思った（小並感）
• グラフ班進捗速すぎる

• 「交流」の時間に発表順とかを決める

• ごまえー♪ http://t.co/38oMegvl8A
• 夜部屋で生命科学や熱力学を少しやる

day 4

• 発表準備では、プログラムを書いてもらったりスライドを作ってもらったりしてた
• 談話室で生徒のスライドを確認したりしてた

• スクリーンセーバーを Twitter 画面にして、「再開時にログイン画面に戻る」設定にしておき、スクリーンセーバー画面で PC を放置するという遊びを思いつく

• あさめしに明太子がなくてつらぽよする
• ごまえー♪ http://t.co/1djOKt6D0i

day 5

• 発表
• Twitter の流速がやばい
• ホワイトボードの輸送が 5 日間で一番大変な作業だった

まとめ

• 乗っ取り激しすぎ

TopCoder SRM588

writer でした。今回は Magical Girl がどこにも登場しませんでした

D2Easy - KeyDungeonDiv2

各ドアに対して独立に考えてよく、赤鍵と緑鍵だけで開けようとして、足りない分を白鍵で補って開けられればよいです。

D2Mid / D1Easy - GUMIAndSongsDiv[1|2]

どう考えたって tone の昇順/降順に歌うのがいちばんいいです
Div1 のほうは、tone の最小値 / 最大値をきめると使える曲が決まるのでソートして greedy。DP なんてどうやってやるの
Div2 では、曲をきめた後 (高々 2^15 = 32768 通り) tone の最小値 / 最大値を求めてもよいです。

D2Hard - GameInDarknessDiv2

dp[t][x][y]: Bob が t 回目の動きの直後 (x, y) にいられるか。
Alice が Bob のいるマスに行く場合と Bob が Alice のいるマスに行く場合の両方で Alice が勝つことに注意。

D1Mid - KeyDungeonDiv2

白い鍵はもらったらすぐに全部赤鍵、緑鍵のどちらか（すべて同じじゃなくてもいい）に変えます。
dp[開けたドア][赤くなった白い鍵の数] として DP
見たところ、dp[開けたドア] でがんばって DP しようとして failed してる人がたくさんいました。

D1Hard - GameInDarknessDiv1

Bob の勝利条件は、「Alice からの距離 - Bob からの距離 >= 2 なる頂点 P で、盤面が下の構造を部分木として含む P が存在する」ことです。

これが満たされない時 Alice が勝てます。
別に 900 や 1000 で出してもいいかなと思ったんですが admin が話し合った結果 1100 になったらしいです。
（りんごさんによると、「admin になって以来最難問」「人間に解けるものに見えない」らしい）

(証明)
Bob の勝利条件を満たしているときは、条件をみたす点を X として、Bob は X を目指します。Alice に追いつかれずに X に到達することができます。
(距離の条件は、「その点に着くまでに Bob は Alice に捕まらない」ということです)
ここで、簡単なプログラムにより Bob が X に着いて、Alice が 2 or 3 マス隣にいる状態でゲーム開始したら Bob は逃げ続けられることが示せます。
別に木がもう少し大きくても Bob は無視して逃げ続ければかまいません。

条件をみたさないときは Alice 必勝です。
最初 Alice は Bob を追いかけます。Bob がどっちにいるかわからなくなったら、葉までの距離が 1 or 2 のほうをまず片づけます。
1 のほうは何もしなくてよいです（Bob がそこに逃げてたとすると自爆する）
2 のほうは、その枝を 1 マスだけ進むと Bob は捕まります。その後すぐに戻れば、Bob が反対側に回りこむ危険はないので枝を減らせます。

Sample 3 みたいなものは少し例外で、この場合は一度適切な葉に Alice が行ってから改めて Bob を捕まえに行くとよいです。

天下一プログラマーコンテスト 2013 予選 A

A, B

ノーコメント

D

A, B を解いて C を見たらわけわからなかったので、書けば点がもらえそうな D を先にやった。
適当に書いて 50 点をもらい、ちょっと改善して 100 点狙いに行ったらなぜか満点もらえた

C

まんなからへんは 12131213… になってないといけなさそうだと気づいて、でも小さい場合はその規則あまり役に立たないので探索したら 100*100 でもいけることに気づいたので、規則を見出して送ったら通った

E

とりあえず 8*8 くらいを探索で取りに行こうとして、調べたら 12*12 でも余裕で間に合うことがわかったので分割法全部試した