問題概要： 各頂点に重みのついた木が与えられる.. 木の情報は以下の通り .... 木の頂点数はnで表される .... 木の各頂点には0からn-1までの番号が割り振られており、 .... i番目(0 .... また、各頂点の子の数は高々２である この木を使ってゲームをする ゲ…

問題概要 : 正しい対応関係を持つ括弧の文字列が与えられる その文字列の先頭の開き括弧 ( とそれより後ろにあるいずれかの閉じ括弧 ) を削除する 削除後の文字列の括弧の対応関係も正しくなければならない このとき、括弧の消し方は何通りあるか？解法： 後…

問題概要： サイズがnであるような2つの数列s,tが与えられる。 数列s,tの各要素には0からn-1まで番号がふられている。 数列sに対して以下の２つの操作を任意の回数だけ適用してtにできるか。 できるならその適用した順序を１つ出力せよ。 操作1. s[i] = s[i]…

問題概要： 整数nとkが与えられる 次の条件を満たすような最小の整数mを求めよ： 1. m は n 以上である 2. m を２進数表記にしたとき、1が少なくともk個連続する箇所が存在する制約 : 1 1 解法： mの中で1がk個連続する箇所をループで決める このとき、mがn…

問題概要 :長さ n (1 Aの各要素A[i]は 0 以上 50 以下である この数列に対して以下の処理を行う1. 変数 X を用意し、 X に 0 を代入する 2. 数列 A のなかから、まだ使っていない要素 A[i] を選び X の値を次の式で更新する : X = X + ( X xor A[i] ) これを…

問題概要： 1以上100以下の整数Nが与えられる。 以下の条件を満たすサイズNの文字列の集合Sを１つ見つけよ。 条件を満たすようなものは必ず存在する。条件 1. 集合Sの要素である文字列の長さは１以上100以下である。 条件 2. 集合Sの要素である文字列は英小…

問題概要： 次の制約を満たすような木は存在するか？1. 木の頂点iのeccentricityがちょうどd[i]である.ここで、頂点iのeccentricityとは、頂点iから最も遠い頂点との距離のことである. 存在するのであればその木の辺集合を配列にして返すこと. 存在しないの…

問題概要 : n人にm回質問をする. 人と質問にはそれぞれ0からn-1,0からm-1まで番号が割り振られている. 人iの質問jに対する回答は英大文字('A'~'Z')として表現される. 各人の各質問への回答が入力として与えられる. 全ての人を区別するためにしなければならな…

問題概要 : n人の生徒からなるクラスがある. 各生徒には強さがあり、それらは0以上255以下の整数として表される.n人の生徒を3つのグループに分ける. ただし、グループ分けを行う際に、だれも生徒が属さないようなグループが出来てはいけない. グループの強さ…

問題概要 : n個のノードが存在し、それらは0からn-1まで番号が割り振られているノードiはi+1がn-1以下であればノードi+1に向けて重みw1[i]の辺を持つまた、ノードiはi+2がn-1以下であればノードi+2に向けて重みw2[i]の辺を持つ各辺は無向辺であるこのように…

問題概要 : 任意の２点間に辺があるような重み付き有向グラフが隣接行列Dとして与えられるこのグラフはn個の頂点から成り、各頂点には0から順にn-1まで番号が割り振られている全ての頂点を少なくとも１回以上訪れるような閉路について考えたとき、この閉路に…

問題概要 : n個の頂点とn本の無向辺があり、頂点は0からn-1まで番号が割り振られている また、辺は頂点iから頂点a[i]に向けて貼られている ( ただし、i != a[i] )このグラフに対して次の処理を行う 1. 新たな頂点 n を追加する 2. 0からn-1までの頂点集合か…

問題概要 : '('と')'からなる文字列sが与えられる この文字列に対して次の処理(1,2を連続で)を行うことができる 1. ２つの整数l,r (l 例 s = "((()", l = 1, r = 3 => s = "(((" 2. s[l]からs[r]までの各文字に対して、'('なら')'に、')'なら'('に変更する …

問題概要 : N人の人がいて、それらの人は0からN-1まで順に番号が割り振られている これらの人の間には友好関係があり、これは２つの整数で表される 友好関係は2つの配列A,Bとして表されA[i]番の人とB[i]番の人は友達である A[i] != B[i] これらの友好関係は…

問題概要 : 4と7から構成される正の整数をLucky Numberと呼ぶ [0-9]と?から構成される文字列が与えられる ?には何の数字が入っても良いので、2つのLucky Numberの和がその文字列と等しくなるようなもののうち最小の和を求めよ解法 : 動的計画法 dp[桁][値][…

問題概要: これまた備忘録なので略解法： １からNまでの周期が存在するので（＜＝ノートに書いてたらそんな感じ、直感的に） １からNまでの最小公倍数を求めれば良い（＜＝さっきのことがわかればそうなるでしょうね） １からNまでで存在する素数を列挙し…

[備忘録] 問題概要 : 備忘録なので略解法 : DP { 0, 0, 3, 3, 0, 0 } という数列が与えられたとする 0..1...2...3...4...5...6 0 0 3 3 0 0 みたいな感じで間に板を置き、左から昇順に番号を割り振る dp[i] := 0番の板からi番の板までで条件を満たす組み合わ…

問題概要: H * W マスからなるフィールドがあり、各マスは次のいずれかである '.' : 空マス 移動可能 '#' : 障害物 移動不可能 'S' : ロボットが最初にいる場所 移動可能 ロボットは命令に従って移動する 命令は 'U','D','L','R' で表されるコマンドがいくつ…

問題概要 : 長さNの文字列がある 初期状態ではそのうちのいくつかに'A'か'B'が書かれていて、 その他は何も書かれていない これから何も書かれていない場所に'A'か'B'を書いていく ただし何も書かれていない場所全てに'A'か'B'を書い後、隣接する２つの場所…

問題概要 : 貴方はホテルを経営している 今年も既にn人から予約が入っている n人の到着する日と出発する日が与えられる 貴方はn人の中から何人か選んでその人らにプレゼントをあげる プレゼントをもらった人はハッピーになる プレゼントをもらった人と同じ日…

問題概要 : 短いし分かりやすいので略解法 : 素因数分解 + ローリングハッシュで通せたが怪しい気がしなくもない 愚直に値を計算すると当然オーバーフローするので、素因数分解してからq1,q2の各素因数の数だけを増やしていく感じにした setにmapを詰めたと…

SRMの進捗を記録したかった SRM 進捗情報とメモ ディビジョン ラウンド easy medium hard 一言 Div2 500 o o SRM 500 Div2 Hard : GeometricProgressions - 土下座しながら探索中 mediumが読めない Div1 500 Div2 501 Div1 501

問題概要： 長さNの配列Aがある この配列は要素として０からN-1までの値がちょうど１つずつ入っている 配列Bを以下のように定義し、これを配列Aの子と呼ぶ 1. B[0] = 0 2. B[i] = A[B[i-1]] ( 1 配列Bの要素が0からN-1までをちょうど１つずつ持つ時、AとBはp…

問題概要： S個の歌がある その音楽を３人のボーカロイドGumi, Ia, Mayuが歌う Gumi は gumi回、 Ia は ia回、 Mayu は mayu回だけ歌う S個の歌は少なくとも３人のうち1人に歌われなければならない そのような歌に対するボーカロイドの割り当て方は何通り存…

問題リンク：Nails | Aizu Online Judge解法： いもす法のサイトの解説参照以下手順だけ 輪ゴムの頂点を(x,y),三角形のサイズをdとする ２次元配列gを用意する（vectorで動的にサイズを確保した） gの(x,y),(x+1,y+d+2),(x+d+2,y+d+1)の値をプラス１ (x+1,y)…

問題概要： N個の要素をもつ配列が与えられる その配列の各要素の初期値は０である あなたは次の２つのオペレーションを行う事ができる 1. 配列の１つの要素を選び、その要素に１加える 2. 配列内の各要素を２倍する N個の要素を含むもうひとつの配列が与え…

問題概要： 6角座標のグラフがvectorで与えられる グラフは'X'と'-'の二種類の要素からなる 自分はグラフ上の全ての'X'に色を塗る ただし色を塗る際に6角の一辺が接していて要素が'X'であるような場所はそれぞれ異なる色にしなければならない 最小で何色必要…

問題概要：略解法： 各ノードに対して Y[i]を+0.5,0.0,-0.5したx軸と平行な直線を引いて何本と交差するか確かめる 単純にY[i]だけでやると 0 1 0 1 0 1 みたいなときに誤って３と出力してしまう コード：：： double err[] = {0.5,0.0,-0.5}; class Piecewis…

問題概要： n枚のカードが与えられる (1 n枚のカードにはそれぞれ表に文字列、裏に数字が書いてある（文字列の長さは全て同じ） このn枚のカードの中から適当にカードを選びつなげた時の文字列が回文となっているものの中でそれらのカードの裏の数字の和が最…

問題概要： n (1 n を hexagonal number の和で表した時に必要な最小の hexagonal number の数を返せ解法： DPで解いた 最初に n 以下の hexagonal number をベクターとかに入れておく dp[n] := n を作るために必要な最小の hexagonal number の数 として fo…