Algorithm
なんで DP 2 個なんだろう 250 ハンバーガーがたくさんあり，それぞれ type と taste が決まっている． このうちの 0 個以上を食べる．このときのうれしさは，(type の種類数) * (taste の和) である．最大値を求めよ．type ごとに，使った時の得られる tast…
250 文字列 A に対して，「1 文字選んで先頭に持ってくる」操作を行うことができる．A を別の文字列 B に変えるために必要な操作の回数は？A の部分文字列で，B の後ろのほうに一致しているものの最長の長さを求める． 600 凸多角形が与えられるので，その内…
コンテスト前 精神統一を実施していないことに気づきあわてて http://www.nicovideo.jp/watch/sm17720979 を視聴する（ただし時間が足りなかった） A A 問題でしかも 40 点だしどうせ簡単な方法だろう この mod とかいうやつもフェイクに違いない と思って探…
Longest Increasing Sequence (AOJ 2430) N(N+1)/2 個の区間を数の和で降順ソートして、ある点から終点までで LIS 分割するときの最大の分割個数で DP。O(N^2 log N) Hakone (AOJ 2439) "-" は無視し、上位から順に見る。dp[位置][D のために空けておいた場…
writer でした。今回は Magical Girl がどこにも登場しませんでした D2Easy - KeyDungeonDiv2 各ドアに対して独立に考えてよく、赤鍵と緑鍵だけで開けようとして、足りない分を白鍵で補って開けられればよいです。 D2Mid / D1Easy - GUMIAndSongsDiv[1|2] ど…
A, B ノーコメント D A, B を解いて C を見たらわけわからなかったので、書けば点がもらえそうな D を先にやった。 適当に書いて 50 点をもらい、ちょっと改善して 100 点狙いに行ったらなぜか満点もらえた C まんなからへんは 12131213… になってないといけ…
250 「なにもしないか、X 段階段を昇る」を X=1,2,...,N まで繰り返す。ただし 1 段立ち止まってはいけない段がある。最もたくさん昇るときどこまでいけるか。「毎回昇って大丈夫」か判定 500 三角形いくつかを XOR した気分の図形の面積を求めよ。何箇所か…
250 1 次関数をいくつかくっつけた形をした関数 f(x) がある。y = f(x) の解の個数の最大値を求めよ。無限にある場合は -1 を返せ。各点と、±εの点を y として試す。vector を vector に移すというアホなミスで落とした＞＜ 500 いくつかの国があり、それぞ…
▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂
250 きつねたちの間でダンスパーティが開かれている。A, B が友人もしくは、ある C が存在して A, C、B, C がいずれも友人であるときに A, B はダンスをすることができる。後者の場合ダンスの後 A, B は友人になる。1 回の曲の間に、各きつねは高々 1 人とダ…
250 盤面上にいくつか鳥がいて、そのうち何羽かは goose である。goose は 1 羽以上存在し、偶数羽存在する。goose から Manhattan 距離 D 以下の鳥は goose である。goose の場所のパターンは何通りあるか。距離 D 以下の鳥の属性(goose or not) は同じでな…
250 人々と自分の rating 一覧が与えられる。単純な規則に従ってランダムに SRM? の部屋割りを決める。自分の部屋の rating の平均値の期待値を求めよ。自分の rating がすごい低い（最後に部屋に割り振られる）かそうでないか（そこでさらに自分の部屋の人…
配点をみて驚愕 250 ソートして、自分のチームの順位を下げる方向に貪欲。 残っているものから順に、「max を選ぶ」「できる限り低く min を選ぶ」「できる限り低く mid を選ぶ」を行う。 450 (位置, 高さ) で Dijkstra。高さはどこかの位置の高さになってい…
問題 うさぎがプログラミングコンテストに参加した。コンテストはいくつかの問題からなり、そのうちいくつかは採点され全うさぎについての正誤が判明しているが、それ以外の問題についてはまだどのうさぎの正誤も判明していない。 このコンテストの上位 qual…
250 パスワードの先頭 K 文字と末尾 K 文字が一致するように、パスワードの文字を変える。できるだけ変える文字数を少なくするときその数を求めよ。union find を使うとどことどこが等しいかわかるのでやるだけ 500 hit and blow の hit だけバージョン。質…
div1 なのにやたら自明だった 250 自明 500 やるだけ 1000 長さが奇数だったら最後の文字は決して動かない。 あとは 2 文字ずつ動く（2 文字内の順番はどうでもいい）。 それぞれ可能な辞書順最小文字列に変換してからソートする。 結果 16 分で終わって眠く…
今年は Algorithm タグがつきました（後述）。 競技について 今年は分業をしました。1, 2, 3 を kitayuta が解いて、4 以降を semiexp が解くようにしました。最初のうちは 1, 2, 3 と 4 以降を交代で実装して、途中で冷えたら交代して紙デバッグするように…
かきかけです 9/22 直前合宿 バスに乗って空港へ出発 結局集合の 1 時間くらい前に着く。1 時間後のバスでよかった気がする 合宿では、いくつかの問題の解説があった りんごさんによる Sails の解説がぱなかった 9/23 Arrival Day 成田→フランクフルト→ミラ…
ひさしぶりに SRM した 250 一瞬「えっ＞＜」ってなるもちょっと書きだしてみたら（根拠もなしに）N≡0,2 mod 3 のときは全色同じずつ、N≡1 のときは 1 色だけ多くなるだろーって思って二分探索した 500 長方形 2 個選ぶ典型問題。 長方形 O(N^4) 通り全部調…
writer やってました。 Div2 Easy(250) AkariDaisukiDiv2 f(X) = Waai + X + Akari + X + Daisuki なる string -> string の関数を考える時、S = f(X) なる (Waai, Akari, Daisuki, X) の組の数を求めよ。問題名とかいろいろおかしいですが(ivan さんに「"Wa…
想定解法は「永続平衡二分木」を使うものですが、そんなもの一般人には書けません。そこで、一般人にも使える道具だけを使って点数を取りに行く試みをしました。
Copy and Paste むずすぎ・・・ 2完ゲーッ
昨日よりましになった。リス（3完）
昨日の問題が簡単に見えるレベル 問題の内容は省略します。
多分 JOI 史上最難問セット。 満点取りに行こうとしましたが、90+100+100だったので（かつ他の人より高い点が得られたので）よしとします。
これだけはテストできないので、思いついた解法を書きます。 解法 木に対して「辺を取り除く」「頂点とそれにつながる辺を取り除く」という操作は、元の木を分解していくつかの新しい木を生み出す操作である。よって、木の Grundy 数を求めればよい。 N >= 1…
Contest はやっぱり結構難しいと思う… 解法 hogloid がO(N log N) で解いたらしいが知らない。 下のコードは O(N^2)。 まず、各チームを「2人とも点数分かってる」「1人しか分かってない」「2人とも分かってない」という基準で、A群、B群、C群に分類する。 …
Belt はかなり面倒な幾何に見えますが、実は実装は比較的楽に書けます。 解法 動く歩道から距離D以下の範囲にある家を最大化したい。「動く歩道」を考えるのは面倒なので、幅2Dの帯を考え、その帯を動かして考える。すると、帯を平行移動することにより、帯…
93位。 A 兵士がN人いて、兵士のための服がM枚ある。それぞれ大きさが決まっていて、大きさがAの兵士は大きさが [A-X, A+Y] の範囲の服を着ることができる。兵士-服の最適な割り当て（最も多くの兵士が服を得ることができる）を求めよ。greedy やるだけで通…
問題 係数が mod 2 の世界で、N (高々 49)次の多項式の M (高々 1016) 乗の K 乗の係数を求めよ。 解法 まず、多項式の M 乗は結構大変なことになりうるので、大変なことにならない状態を考える。 多項式の 2 乗を考えると、mod 2 の世界では各項の指数が 2 …
