土下座しながら探索中

主に競技プログラミング

SRM

SRM 714 div 1 easy : ParenthesisRemoval

SRM

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

SRM 712 DIV 1 easy : LR

SRM

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

SRM 711 : ConsecutiveOnes

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

SRM 709 Div1 easy : Xscoregame

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

SRM 708 : Div1 easy BalancedStrings

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

SRM 704 Div1 easy : TreeDistanceConstruction

SRM

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

SRM 694 Div1 medium : DistinguishableSetDiv1

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

SRM 694 Div1 easy : TrySail

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

SRM Div1 easy : BiconnectedDiv1

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

SRM 692 Div1 easy : HardProof

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

SRM 691 Div1 easy : Sunnygraphs

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

SRM 688 Div1 easy : ParenthesesDiv1Easy

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

SRM 682 Div1 easy : SmilesTheFriendshipUnicorn

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

SRM 655 Div1 easy : LuckySum

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

SRM 652 Div1 250 : ThePermutationGame

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

SRM 653 Div1 250 : CountryGroupHard

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

SRM 651 Div1 easy : RobotOnMoon

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

SRM 650 Div1 easy : TaroFillingAStringDiv1

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

SRM 645 Div1 easy : JanuszTheBusinessman

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

SRM 500 Div2 Hard : GeometricProgressions

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

SRM 進捗状況

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

SRM Div1 Easy : PerfectPermutation

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

SRM Div2 hard : VocaloidsAndSongs

SRM

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

AOJ 0574 : Nails

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

SRM 596 Div1 easy

SRM

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

SRM 593 DIV1 easy : HexagonalBoard

SRM

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

SRM586 Div1 easy

SRM

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

SRM499 Div2 hard PalindromeGame

SRM

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

SRM205 Div2 hard HexagonalSums

SRM

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

SRM582 Div2

midだけ・・・mid 問題概要: m人の魔法少女とn体の敵がいる 魔法少女と敵はそれぞれ強さMS[i](i 魔法少女は自分の強さ以下の敵を倒せる 一回の攻撃で倒せる敵は1体のみである 一回攻撃する度に攻撃した魔法少女は疲労が1たまる(初期は疲労0) 魔法少女…