SRM658Div1Easy
問題
サイズN*Nの配列xが与えられる。サイズNのツリーを考え、配列の各要素はx[i][j]はiからjまでの距離が偶数か奇数かを示している。与えられた配列の条件を満たすツリーを求めよ。
解法
kmjp.hatenablog.jp
ここの解答を参考にした。
ツリーの構築として、偶数か奇数しか制約がないのでひとつのルートを選び、奇数のノードと偶数のノードを接続すれば、条件を満たすツリーを構築できる。
計算量
コード
SRM591Div1Easy
問題
ルートからの距離がxであるノードを個持つツリーを考える。この時のツリーの直径を求めよ。
解法
各ノードをルートとした時の子であるノードの中で深さが最大となる2つを選ぶ。これを全てのノードに対して行うことで答えが求まる。
最初に与えられたツリーのルートが、直径となるノードどうしのパスに含まれるとは限らない。しかし、必ずルートを通るという条件をつけると、その時の最大距離は子であるノードの長で深さが最大となる2つを足し合わせた値となる。
計算量
コード
SRM592Div1Easy
問題
サイズNの文字列が与えられる。各要素はR,G,Bのどれかである。何もない文字列から始め、一文字ずつ文字を加え与えられた文字列にする時の最高のスコアを求めよ。
スコアは以下のように追加される。
- 初めの要素の場合は0ポイント
- 文字列の端に追加した場合は、もとの文字列の文字の種類の分だけスコアを足す
- 文字列の間に追加した場合は、左右の文字列の文字の種類の分だけスコアを足す
解法
左用と右用の集合を用意し、それに追加してくことで答えが求まる。
計算量
コード
SRM593Div1Easy
問題
N*Nの配列が与られる。各マスは六面体となっており、要素はXか-である。Xの箇所を任意の色で塗りたい。ただし、隣り合うマスでは違う色とする。この時に必要な色の最小数を求めよ。
解法
3色あればどんな場合でも塗ることができる。なので、0、1、2のどれであるかを調べることで答えが求まる。Xがない場合は0、Xが隣合ってない場合は1となる。一つの要素としか隣合っていない場合は2となる。深さ優先探索を行うことで答えは求まる。
計算量
コード
SRM594Div1Easy
問題
N個の惑星の相対サイズAとM個の惑星の相対サイズBが与えられる。各要素は中心からの距離が近い順に並べられている。相対サイズとはある基準に対して何倍であるかを示す値である。AとBそれぞれの中では基準は同一であるが、AとBで同じ基準であるとは限らない。
この時の最小の惑星の数を求めよ。
解法
最長共通部分列で答えが導ける。
基準を同じにするためにAとBそれぞれから一要素だけ選択し、その要素を選択していない方のすべての要素にかける。
計算量
コード
SRM595Div1Easy
問題
サイズMの配列が与えられる。各要素は白か黒である。その配列に対してロボットがある操作を行う。ロボットはサイズNの配列L,Rを持っている。その配列に従い、L[i]~R[i]までを白か黒で塗りつぶす。ロボットの作業が終わったあとの配列の状態の総数を求めよ。
解法
各操作に番号を振り、シミュレートをし、残った番号の数を2の指数とすると答えが求まる。
計算量
コード
SRM557Div1Easy
問題
隣り合う要素の差分が1である長さnの数列を考える。はじめの要素h0と最後の要素hnが与えられる。差分を示す文字列historyが与えられた時、そのhistoryを実現できるかを判定せよ。historyの要素はUかDのどちらかで、Uはh[i+1]-h[i]=1、Dはh[i+1]-h[i]=-1を示す。数列の各要素は必ず0以上である。
解法
h0からhistoryを始め、その時の最小値を求める。最小値分だけh0に足し合わせ、常に0以上になるようにする。historyと最小値の分を引き、あまりの要素の数を求める。その要素とhnとh0の差分を求め、それが0以上かつ偶数ならば"YES"を返し、それ以外なら"NO"を返す。
計算量
