Hatena::Grouptopcoder

peryaudoのTopCoder日記

 | 

2016-02-15

WalkOverATree

| 20:41

#include <vector>

using namespace std;

class WalkOverATree {
 public:
   int maxNodesVisited(vector<int> parent, int L) {
     vector<int> depths(parent.size() + 1, 0);
     for (int i = 1; i < depths.size(); ++i) {
       depths[i] = depths[parent[i - 1]] + 1;
     }

     int ans = 0;
     for (auto&& depth : depths) {
       if (L - depth < 0) {
         continue;
       }

       const int cur = depth + 1 +
         min<int>((L - depth) / 2, depths.size() - depth - 1);
       ans = max(ans, cur);
     }

     return ans;
   }
};

DP書きかけてウガーっってなって調べたらO(N)解法があった。

ちゃんと考えて動けるようになりたい…

PaintTheRoom

| 15:49

#include <string>

using namespace std;

class PaintTheRoom {
 public:
   string canPaintEvenly(int R, int C, int K) {
     if (K == 1)
       return "Paint";
       
     if (R * C % 2 == 0)
       return "Paint";
     else
       return "Cannot paint";
   }
};

大体あってたのに変な特殊ケースをベタ書きしたせいで一発ACしそこねた。

SubdividedSlimes

| 15:10

class SubdividedSlimes {
 public:
  int needCut(int S, int M) {
    for (int i = 0; i < S; ++i) {
      if (CalcScore(S, i + 1) >= M) {
        return i;
      }
    }

    return -1;
  }

  int CalcScore(int length, int sections) {
    const int unit = length / sections;
    const int unit_plus_one_sections = length % sections;
    const int unit_sections = sections - unit_plus_one_sections;

    int ans = 0;
    ans += unit_sections * unit * (length - unit);
    ans += unit_plus_one_sections * (unit + 1) * (length - unit - 1);
    ans /= 2;
    return ans;
  }
};

相変わらず自力でとけん…

想定誤解法しました

 |