だいぶ解くことから逃げた問題もあるが、そのうち89問を一応(所見/解答見て)提出できたようだ。 一応http://d.hatena.ne.jp/anta1/20121209の時からやっているので、3ヶ月弱かかってしまったことになる。 問題数で割ったら1日1問とかそんな感じで、サボりま…

問題 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で足す」という…

問題 Editorial 問題 大きいマップに縦の道路と横の道路が最大600個くらいあるから道路を渡る回数を最小化して 解答 座標圧縮してBFS。 自分は道路の前後も座標に含めたらメモリがギリギリになってしまった。 含めるのは道路の座標そのものだけでいいらしい…

問題 Editorial 問題 n人の人とプレゼントがn個ある。それぞれの人の各プレゼントのスコアvalueが与えられる。 今、人iはプレゼントiに割り当てられている。 ここから、何人かでプレゼントを交換したとき、新たな各人のスコアの総和がそれをする前より増加す…

問題 Editorial 問題 数列seqが与えられる。この数列に"imposition"という操作をN回行った後の数列を求めよ。 "imposition": 各要素にその次(最後の要素の次は最初の要素)の要素をmod100で足す 2 0 1 解答 行列累乗するだけ。 (A[i][i] = 1; A[(i+1)%n][i] =…

問題 Editorial 問題 指定されたプログラムcommandsRobbie,commandsSpeedyに従って動くロボット2台がある。 プログラムはU,D,L,Rからなり、それぞれ右・左・上・下に動く。壁の方向に動こうとする場合は動かない。 今xSize*ySizeのグリッドがある。 この任意…

解答書きました: http://d.hatena.ne.jp/anta1/20130201/1359651597 ※一瞬このブログに別の問題文を載せてましたが、問題変えました ※少しの発想で作っただけで、よく考えたりしていないので、質は良いとはいえないです。 問題 サイズN(≦10^3)の、段yの幅はy…

問題 Editorial 問題 画像が上手く表現できないので略 解答 (交差点の(x * y * (真ん中, 四隅)))でDPするだけ。 (width コメント これは一瞬で解けるべき コード #include <string> #include <algorithm> #include <cstring> #include <complex> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i</complex></cstring></algorithm></string>…

問題 Editorial 問題 (問題の肝の部分のみ) width*heightの長方形の中にx*yの長方形が回転してでも入るかどうかを判定せよ 全ての数値は整数, [1,1000] 解答 回転後の幅と高さは(x cosθ + y sinθ, x sinθ + y cosθ)。 それを適当にいろんな感じで二分探索し…

問題 Editorial 問題 Nつに分割されたパイがある。Nは3の倍数である。そのそれぞれの部分の面積piecesが与えられる。 これを自分と相手で交互に食べ、自分が食べる面積を最大化したい。 自分は、任意の部分を1つ選び、それを食べることができる。 次に、相手…

問題 Editorial 問題 複数行コメントを削除したい。それはネストできる。 複数行コメント"MLC"は以下の構文で定義される: MLC := "/*" <Nester> "*/" Nester := ("/*"も"*/"も含まない文字列) | <Nester> <MLC> <Nester>プログラムlinesがvectorで与えられる。これは各行を表していて、文</nester></mlc></nester></nester>…