問題 Editorial 問題 ある文字列のサブシークエンスとは、その文字列から任意の個数の文字を消したものである(連続している必要はない)。 3つの文字列a,b,cが与えられる。この3つの文字列に共通する空でないサブシークエンスの数(同じ文字列は重複して数えな…

問題 Editorial 問題 箱を2*2*heightに積む。 それぞれの箱は独立に、0.5の確率でダイナマイトが入っていて、そうでなければ空である。 「ダイナマイトクラスター」とはダイナマイトの入った箱の集合で、連結なものである(面でのみ接しているとみなす)。 サ…

問題 Editorial 問題 立方体であって、6面がそれぞれ[0..6]の色で塗り分けられているレンガがいくつかある。 2つのレンガが同じであるとは、ある回転をしたときに全ての面が同じ色で塗られていることである。 bricksが与えられる。それらの面を塗り替えて全…

問題 Editorial 問題 略 解答 状態を圧縮する。 スタート・Wの場所のそれぞれ4方向分の状態と止まった状態を考えればいい。 その関係式を行列累乗でやる。 ガウスの消去法で解いても出来ると思う。http://d.hatena.ne.jp/anta1/20130217/1361087344のように …

問題 Editorial 問題 digits つの数字が入る所がある。今入っている数字はdigitsで与えられる。'_'の所は空であることを表す。 '_'の数だけ独立にランダムに順番に数字が選ばれる。 1つの数字が選ばれた時、次の数字が選ばれる前に、どこに数字を入れるかを…

map<string,int> a; for(int i = 0; i < name.size(); i ++) { string s = name[i]; a[s] = a.count(s) ? max(a[s], score[i]) : score[i]; } 名前のリストと(負の数もありうる)スコアのリストが与えられるので名前ごとの最大スコアを計算するという趣旨のコード。 しか</string,int>…

問題 Editorial 問題 xSize*ySizeの矩形領域がある。 領域内のいくつかの場所(x[i], y[i])に「膨張する」円がある。それは、時間tのとき半径tになる。今(時間0)では限りなく小さい。 自分は今(時間0)(px, py)にいる。自分はどんな方向にも1の速さで移動する…

問題 Editorial 問題 略 解答 グラフを作って全点対最短路出して対は全探索。 ダイクストラとか01-bfsしてもいいが、Floyd-Warshall法は十分に速いようだ。 あと、グラフの作り方として辺のコスト = 終点のコストにして最後に始点のコストを足す奴が使える。…

問題 Editorial 問題 辞書dictが与えられる。 この辞書dictに含まれる単語を使ってしりとりをする。 ただし、同じ単語を複数使っても良い。 しりとりをして文字列を作ることが出来る。例えば"abc"と"cd"と"efgh"でしりとりすると"abcdefgh"という文字列にな…

問題 Editorial 問題 2人でゲームをする。 シークエンスの集合sequencesが与えられる。 最初のプレイヤーはsequencesから1つ選ぶ。 相手のプレイヤーは最初のプレイヤーが選んだものとは違うシークエンスをsequencesから1つ選ぶ。 その後ランダムなコインを…

問題 Editorial 問題 無限のグリッドにそれぞれ小文字アルファベットが書かれている。 (i,j)に書かれている文字は(g[i mod R][j mod C] where gはR*Cのサイズ)である。 (0,0)から(x,y) (x,yは非負整数)を通る半直線上の(厳密にその座標を通った)文字を繋げる…

問題 Editorial 問題 数列sequenceが与えられる。 「どれかを1増加させる」「どれかを1減少させる」という操作ができる。なお、マイナスにすることもできる。 最低K個の相違なる数を含ませるようにするとき、操作回数を最小化せよ 1 1 1 解答 Editorialを見…

問題 Editorial 問題 文字列の集合dictionaryが与えられる。 長さnの文字列のうち、dictionaryに含まれる単語を部分文字列として含むものの数をmod 10000で求めよ 1 1 1 解答 行列累乗。 単語へのマッチング状態を状態として持って、次の文字で行く所に+1す…

問題 Editorial 問題 数列initialが与えられる。 これの各々を移動させて、等差数列の並び替えにしたい。ただしそれぞれの数値は重複があってはいけない。 移動させるのに移動させた分だけコストがかかる。 コストを最小化せよ 2 -2*10^9 解答 Editorialを見…

問題 Editorial 問題 任意の平面グラフは交差しない線分だけで描けることが知られている。 平面グラフgraphが与えられる。整数座標上で交差しない線分で描くとき、それを収める(座標軸に平行な)矩形の面積を最小化せよ 1 解答 Editorialを見た。 基本的な方…

問題 Editorial 問題 略 解答 二分探索*二部マッチング。 mid以下の時間でたどり着ける位置同士に辺を張って、完全マッチングが出来るかどうかで判定する コード #include <string> #include <vector> #include <sstream> #include <cmath> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i</cmath></sstream></vector></string>…

http://www.codechef.com/FEB13 初めてのChef long。結果は振るわなかったけれど、考えるのが面白かった。 Problems BUY1GET1 数える CLMBSTRS フィボナッチ数列をDPで LECARDS 各カードがどんな数値であっても、それを取るなら相対スコアが+1・取らないなら…

問題文 解説pdf AOJ 問題(概略) 木の各頂点に数値がついています。以下のクエリに答えなさい: 「頂点(v, w)を結ぶ経路上でL番目に小さい数値を出力せよ」 1 1 1 解答 解説pdfを読んで、最後に書いてある「別解」を実装してみた。 自分で考えて実装したので、…

※全然まとまってない 参照 http://imoz.jp/algorithms/imos_method.html 早稲田大学プログラミングコンテスト I: その味は甘くて 解説スライド 呼び方 自分はこの記事では、以下の呼び方を使います。特に、演算とそれを用いたアルゴリズムの違いに、"〜法"を…

※上手く書けなくて、途中から放棄してます http://d.hatena.ne.jp/anta1/20130118/1358492699で書いた、作った問題の想定解法です。詳細はその記事を参照してください。 問題概略 「ある位置にパスカルの三角形の最初の何段かをmod1000000007で足す」という…