きままにものづくり

日々の気付いたことなんかを書いてます。

SRM573Div1Easy

問題

サイズNの配列が与えられる。Nは3の倍数である。プログラミングコンテストを考える。各要素はプログラマの実力を示し、はじめの3要素X,Y,Zが自身のチームメンバーである。チームの能力はmax(X,Y,Z)+min(X,Y,Z)で求まる。この能力より真に大きいチームは、自身のチームより高い順位となる。
この時の自身のチームの最悪の順位を求めよ。

解法

能力順にソートし、大きい要素と小さい要素で能力を比較することで答えが求まる。

計算量

O(N log N) (ソート)
O(N) (探索処理)

コード

SRM657Div1Easy

問題

SRMのようにEasy, Medium, Hardの3つでひとつである問題セットを考える。E,M,HはそれぞれEasy, Medium, Hardの問題であり、EMはEasyにもMediumなれる問題であり、MHはMediumにもHardにもなれる問題である。
E,M,H,EM,MHの数が与えられた時の問題セットの最大値を求めよ。
E,M,H,EM,MHの最大値はNである。

解法

問題セットの数を固定すれば、それを満たすかの確認はできる。
問題セットの数に対して二分探索をすることで、答えが求まる。

計算量

O(log N)

コード

SRM659Div1Easy

問題

N個のフルーツが並んでおり、それらはりんごかオレンジである。K個の連続するフルーツは最大でもK/2個のりんごしかない。
いくつかのりんごの位置の配列が与えられた時の最大のりんごの数を求めよ。

解法

左側の要素から探索していき、周囲K個のりんごの数がK/2より小さいならその要素をりんごにする。

計算量

O(NK^2)

コード

SRM658Div1Easy

問題

サイズN*Nの配列xが与えられる。サイズNのツリーを考え、配列の各要素はx[i][j]はiからjまでの距離が偶数か奇数かを示している。与えられた配列の条件を満たすツリーを求めよ。

解法

kmjp.hatenablog.jp
ここの解答を参考にした。

ツリーの構築として、偶数か奇数しか制約がないのでひとつのルートを選び、奇数のノードと偶数のノードを接続すれば、条件を満たすツリーを構築できる。

計算量

O(N^3)

コード

SRM591Div1Easy

問題

ルートからの距離がxであるノードを cnt_x個持つツリーを考える。この時のツリーの直径を求めよ。

解法

各ノードをルートとした時の子であるノードの中で深さが最大となる2つを選ぶ。これを全てのノードに対して行うことで答えが求まる。
最初に与えられたツリーのルートが、直径となるノードどうしのパスに含まれるとは限らない。しかし、必ずルートを通るという条件をつけると、その時の最大距離は子であるノードの長で深さが最大となる2つを足し合わせた値となる。

計算量

O(N^2)

コード

SRM592Div1Easy

問題

サイズNの文字列が与えられる。各要素はR,G,Bのどれかである。何もない文字列から始め、一文字ずつ文字を加え与えられた文字列にする時の最高のスコアを求めよ。
スコアは以下のように追加される。

  • 初めの要素の場合は0ポイント
  • 文字列の端に追加した場合は、もとの文字列の文字の種類の分だけスコアを足す
  • 文字列の間に追加した場合は、左右の文字列の文字の種類の分だけスコアを足す

解法

左用と右用の集合を用意し、それに追加してくことで答えが求まる。

計算量

O(N log N)

コード

SRM593Div1Easy

問題

N*Nの配列が与られる。各マスは六面体となっており、要素はXか-である。Xの箇所を任意の色で塗りたい。ただし、隣り合うマスでは違う色とする。この時に必要な色の最小数を求めよ。

解法

3色あればどんな場合でも塗ることができる。なので、0、1、2のどれであるかを調べることで答えが求まる。Xがない場合は0、Xが隣合ってない場合は1となる。一つの要素としか隣合っていない場合は2となる。深さ優先探索を行うことで答えは求まる。

計算量

O(N^2)

コード