TCO 2016 Round 1A Div1

競プロ

寝過ごして参加できなかったので復習しました．

[Easy 250: EllysTimeMachine ]

問題

アナログ時計の現在の時刻が"HH:MM"の形式で与えられる．HHは短針が表す時間，MMは長針が表す分を表している．ただし，

  • HH \in \{01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12\}，
  • MM \in \{00, 05, 10, 15, 20, 25, 30, 40, 45, 50, 55\}

の値をとる．
短針と長針の向きを交換したときの現在の時刻を答えよ．ただし，HHとMMはそれぞれ上の取りうる値に近い値にする（進める方向）．

方針

問題文通りにシミュレーションをします．一つ一つステップに従って愚直に実装します．詰まりそうな部分は上手くまとめようとせずに書きます．

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

class EllysTimeMachine {
public:
	string getTime(string time) {
            int hh = (int)(time[0] - '0') * 10 + (int)(time[1] - '0');
            int mm = (int)(time[3] - '0') * 10 + (int)(time[4] - '0');
            string res;

            if (mm == 0)
                res = "12";
            else {
                if (mm < 50)
                    res = "0" + to_string(mm / 5);
                else
                    res = to_string(mm / 5);
            }

            res += ":";
            if (hh == 12)
                res += "00";
            else if (hh == 1)
                res += "05";
            else
                res += to_string(hh * 5);

            return res;
	}
};

[Med 500: EllysSocks ]

問題

各々の靴下のサイズを表す配列Sが与えられる．この中でP個の靴下の組を求める．ただし，選んだ各々の靴下の組のサイズの差の絶対値の最大値を最小化する組合せを求め，その時の最小値を答えよ．

制約
  • 2 \le |S| \le 1,000
  • 1 \le S_i \le 1,000,000,000
  • 1 \le P \le |S|/2
方針

蟻本の「最小値の最大化（pp.131-132）」と同様な考え方で二分探索法を用いて解きます．
靴下の組の差がd以下になるようにたくさの靴下の組を選んだときにP個以上選べるかを考えます．このとき，dの値で二分探索を行います．先ほどの条件を満たすならばdの値の小さい部分を探し，満たさないなら大きな部分を探します．
次に，どのように条件を判定するのかを考えます．まず，選ぶべきペアはソートしたときに隣り合う靴下同士を選ぶ方が差の絶対値が小さくなります．また，(a, b, c) がサイズの小さい順にソートされているとしたときに，(a, b) が選べるならば (b, c) を選ぶよりも (a, b) を選んだ方が残りの部分で選べる靴下の組の数が増える可能性があります．したがって，靴下のサイズでソートしたときに，小さい順から貪欲的に隣り合う靴下との差の絶対値がd以下なら選ぶとして組を作っていきます．そして，選んだ組の数がP個以上ならtrueを返し，それ以外ならfalseと返すことによって判定することが出来ます．

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

class EllysSocks {
public:
	int getDifference(vector <int> S, int P) {
            const int n = S.size();
            sort(S.begin(), S.end());

            int lb = -1, ub = 1000000000;
            while (ub - lb > 1) {
                int mid = (lb + ub) * 0.5;

                int num = 0, idx = 0;
                while (idx + 1 < n) {
                    if (S[idx + 1] - S[idx] <= mid) {
                        ++num;
                        ++idx;
                    }
                    ++idx;
                }

                if (P <= num)
                    ub = mid;
                else
                    lb = mid;
            }

            return ub;
      }
};

[Hard 1000: EllysTree ]

問題

ラベル付されたN+1頂点の根付き木が与えられる．それぞれのラベルは0からNであり，根のラベルは0である．
頂点u,vに対して，uがvの先祖またはvがuの先祖ならuとvの間を移動することが出来る．ただし，既に訪れた頂点には移動できない．
今，根にいるとしてすべての頂点にちょうど1回訪れるような移動順序を答えよ．ただし，そのような移動順序が複数あるならば辞書式順序で最小のものを答えよ．また，すべての頂点をちょうど1回訪れるような移動順序が存在しないなら空集合を返せ．

制約
  • 1 \le N \le 100
方針

解法が思いつかなかったのでmayokoさんの解法を参考にしました．
2016 TCO Algorithm Round 1A hard: EllysTree - mayoko’s diary

まず全探索することを考えます．現在いる頂点から訪れることが出来て，まだ訪れていない各々の頂点に対して次に訪れるとして再帰的に探索をします．途中で，現在いる頂点から訪れることが出来る頂点が存在しないならこのような移動順序は存在しません．このような全探索を行うと計算時間はO(N!)となり解くことができません．
ここで，求める解が辞書式順序の上で最小となるものを見つけることに注目します．すなわち，次に訪れる頂点の候補としてu, v（u, v）があり，uの後の移動順序がL，vの後の移動順序がL'としたときに， L'< L であっても uL < vL' となります．これは，距離の総和の最小化などでは成り立ちません．
したがって，次に訪れることが出来る頂点の中でラベルの小さい頂点uを優先的に探索を行います．uを訪れた後で残りの頂点を訪れることができるのならuを選びます．
次に，頂点uを訪れた後で残りの頂点を訪れることが出来るのかの判定部分を考えます．ここからは自分の中でよく分かっていないのでmayokoさんのブログをご覧ください．ここからはより支離滅裂です．
頂点uが訪れることが出来る頂点はuの部分木と根からuへのパスの頂点になります．ここで，このような移動することが出来るに注目して構成したグラフを考えます．先ほどの判定部分はこのグラフ上でuを始点としたハミルトン路が存在するかの問題に等しくなります．一般のグラフではハミルトン路の存在判定はNP完全になりますが，先ほどのように構成されたグラフでは効率的に解けるかは分かりません．ここらへんはもう少し考えてみます．

ソースコード







    
まとめ