na_o_ysのブログ

プログラミングなど

SRM 638 Div1 Easy, ShadowSculpture

SRM

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13355&rd=16081

N*N*N (N <= 10) の空間に 1*1*1 のキューブをいくつか配置する. XY・YZ・ZX平面の投影図がそれぞれ与えられる. 配置したキューブは全て隣接し得るかどうか答えよ.

方針

座標 (i, j, k) にキューブが存在し得る条件: XY[i][j] && YZ[j][k] && ZX[k][i]

  • 各座標について,
    • DFSで存在し得る隣接キューブにマークを付ける
    • マークがついたキューブから 3 平面の投影図を作り, 入力と一致するかどうかチェックする

解答

#include <iostream>
#include <vector>
#include <algorithm>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define from_to(from, to, i) for(int i=from;i<=to;i++)
 
using namespace std;
 
class ShadowSculpture
{
public:
    string possible (vector <string> XY, vector <string> YZ, vector <string> ZX)
    {
        this->XY = XY;
        this->YZ = YZ;
        this->ZX = ZX;
        N = XY.size();
        loop (N, i) loop (N, j) loop (N, k) {
            if (XY[i][j] == 'Y' && YZ[j][k] == 'Y' && ZX[k][i] == 'Y') {
                A[i][j][k] = 1;
            }
        }
 
        loop (N, i) loop (N, j) loop (N, k) used[i][j][k] = 0;
 
        loop (N, i) loop (N, j) loop (N, k) {
            loop (N, i) loop (N, j) loop (N, k) visited[i][j][k] = 0;
            dfs(i, j, k);
            if (check()) return "Possible";
        }
        return "Impossible";
    }
 
    vector<string> XY, YZ, ZX;
    int N;
    int A[10][10][10] = {};
    int used[10][10][10];
    int visited[10][10][10];
 
    void dfs(int i, int j, int k) {
        if (used[i][j][k] || !A[i][j][k]) return;
        used[i][j][k] = visited[i][j][k] = 1;
        if (i-1 >= 0) dfs(i-1, j, k);
        if (i+1 < N)  dfs(i+1, j, k);
        if (j-1 >= 0) dfs(i, j-1, k);
        if (j+1 < N)  dfs(i, j+1, k);
        if (k-1 >= 0) dfs(i, j, k-1);
        if (k+1 < N)  dfs(i, j, k+1);
    }
 
    bool check() {
        int xy[10][10] = {}, yz[10][10] = {}, zx[10][10] = {};
        loop (N, i) loop (N, j) loop (N, k) {
            if (visited[i][j][k]) {
                xy[i][j] = yz[j][k] = zx[k][i] = 1;
            }
        }
        loop (N, i) loop (N, j) {
            if (XY[i][j] == 'Y' && !xy[i][j]) return false;
            if (YZ[i][j] == 'Y' && !yz[i][j]) return false;
            if (ZX[i][j] == 'Y' && !zx[i][j]) return false;
        }
        return true;
    }
};

SRM 633 Div1 Easy, PeriodicJumping

SRM 幾何

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13234&rd=16076

int x, vector<int> jumpLengths が与えられる.
二次元平面上の原点 (0, 0) からスタートして, 点 (x, 0) に到達したい.
平面上を jumpLengths で与えられた距離だけ順に移動する. (jumpLengths = {2, 5} の場合は, 距離 2, 5, 2, 5, .... ずつ移動する. )
最短何回の移動で到達できるか.

  • -109 <= x <= 109
  • jumpLength contains 1 between 50 elements.
  • a ∈ jumpLength について, -109 <= a <= 109

方針

多角形の成立条件: 最大辺の長さ <= その他の辺の合計長
を使う.
n 回の移動で辺 (0, 0) to (x, 0) を含む多角形を構成できるかどうかを確かめる.

N = len(jumpLength), S = sum(jumpLength) とする.

  1. x == 0 の場合
    • 解は 0
  2. x > S の場合
    • 最大辺の長さは x
    • 移動距離の合計が初めて x を超えた時の移動回数を求めれば良い
  3. x <= S の場合
    • 最大辺の長さは max(x, max(jumpLength))
    • 少なくとも 2N 回の移動で多角形を構成できる.
    • n = 1, ..., 2N について, n 回の移動で多角形を構成できるかどうか確かめれば良い.

解答

class PeriodicJumping
{
public:
    int minimalTime(int x, vector <int> jumpLengths)
    {
        x = abs(x);
        int N = jumpLengths.size();
        ll S = 0;
        for (int l : jumpLengths) S += l;
        if (x == 0) return 0;
        if (x <= S) {
            loop (N*2, i) {
                ll m = 0, len = 0;
                loop (i+1, j) m = max(m, (ll)jumpLengths[j%N]);
                m = max(m, (ll)x);
                loop (i+1, j) len += jumpLengths[j%N];
                len += x;
                if (m <= len/2) return i + 1;
            }
        }
        if (x > S) {
            int ans = N * (x/S);
            x %= S;
            for (int l : jumpLengths) {
                if (x <= 0) break;
                ans++;
                x -= l;
            }
            return ans;
        }
        return -1; // dummy
    }
};

感想

本番では, 愚直に移動回数毎の移動可能範囲を求めて解いた. 2N 回の移動で半径 2S の範囲をカバーできることに気付くまでに時間がかかった. 凡ミスで failed systest.

まともな幾何の問題は初めてだった. 素振りが足りない.

SRM 632 Div1 Easy, PotentialArithmeticSequence

SRM

問題

a[0], ..., a[N-1] の N 個の非負整数がある. ただし, a は与えられない. 代わりに, 2進数表現での trailing zero の数 d[0], ..., d[N-1] が与えられる. a[0], ..., a[N-1] について, 1 ずつ増加する部分列の個数の最大値を求めよ.

  • 1 <= N <= 50
  • 0 <= d[i] <= 109

解法

全ての i, j (i < j) について d[i], ..., d[j] が 1 ずつ増加する数列になりうるかどうかを確かめる.

必要十分条件: 2k+1 個おきに, k が出現する

解答

class PotentialArithmeticSequence
{
public:
    int numberOfSubsequences (vector <int> d)
    {
        int N = d.size();
        int ans = 0;
        loop (N, i) loop (N, j) {
            if (i > j) continue;

            vector<int> e;
            from_to(i, j, k) e.push_back(d[k]);
            bool ok = true;
            int k = 0;
            for (; ok && e.size() > 1; k++) {
                int l = e[e.size()-1] == k ? e.size()-1 : e.size()-2;
                while (ok && l >= 0) {
                    if (e[l] == k) e.erase(e.begin()+l);
                    else ok = false;
                    l -= 2;
                }
            }
            if (ok && e[0] >= k) ans++;
        }
        return ans;
    }
};

SRM 630 Div1 Med, SuffixArrayDiv1

SRM

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13377&rd=16061
ある文字列に対する接尾辞配列 SA が与えられている. 元の文字列は何種類のアルファベットで構成されているか. 最も少ない場合の種類数を求めよ.
接尾辞配列 - Wikipedia

文字列長は 1 以上 50 以下とする.

解法

接尾辞を辞書順に並べた時に, 先頭文字が最低何回変わらなければならないかを考える.
文字列の i 文字目を c(i), i 文字目以降の接尾辞を suff(i) で表すと,

suff(i) < suff(j) \iff c(i) = c(j) かつ suff(i+1) < suff(j+1), または c(i) < c(j)

が成り立つ. これを用いて, 各 i について suff( SA[i] ) と suff( SA[i+1] ) の先頭文字を等しく出来るかどうかを確かめる.

解答

#include <iostream>
#include <vector>
#include <algorithm>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define from_to(from, to, i) for(int i=from;i<=to;i++)

using namespace std;

class SuffixArrayDiv1
{
public:
    int minimalCharacters (vector <int> SA)
    {
        int N = SA.size();
        vector<int> I(N+1);
        loop (N, i) I[SA[i]] = i;
        I[N] = -1;

        int cnt = 0;
        loop (N-1, i) {
            if (I[SA[i]+1] > I[SA[i+1]+1]) cnt++;
        }

        return cnt+1;
    }
};

SRM 630 Div1 Easy, Egalitarianism3

SRM

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13284&rd=16061
頂点数 n, 辺数 n-1 の木が与えられる. 各辺には距離が設定されている. k 個の頂点を選び, 頂点間の距離が全て等しくなるようにしたい. k の最大値を求めよ.
頂点数は 1 以上 50 以下, 各辺の距離は 1 以上 1000 以下とする.

解法

条件を満たす頂点集合は次の三通り

  • 任意の 1 頂点 (k = 1)
  • 任意の 2 頂点 (k = 2)
  • スター型 (k > 2)
    ハブ頂点までの距離が等しく, ハブ頂点までの路を共有しない頂点の集合

スター型については, ハブ頂点を決め, 各頂点への距離を dfs で求める.

解答

#include <iostream>
#include <vector>
#include <algorithm>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define from_to(from, to, i) for(int i=from;i<=to;i++)

using namespace std;
using P = pair<int, int>;
const int MAX_D = 60000;

class Egalitarianism3
{
public:
    int D[MAX_D];
    int latest[MAX_D];
    vector<P> G[100];

    int maxCities (int n, vector <int> a, vector <int> b, vector <int> len)
    {
        loop (n-1, i) {
            G[a[i]-1].emplace_back(b[i]-1, len[i]);
            G[b[i]-1].emplace_back(a[i]-1, len[i]);
        }

        int ans = n >= 2 ? 2 : 1;
        loop (n, i) {
            fill(D, D+MAX_D, 0);
            fill(latest, latest+MAX_D, -1);

            for (P& p : G[i]) {
                dfs(p.first, p.second, i, p.first);
            }
            loop (MAX_D, j) ans = max(D[j], ans);
        }
        return ans;
    }

    void dfs (int n, int d, int rev, int orig) {
        if (latest[d] != orig) {
            latest[d] = orig;
            D[d]++;
        }
        for (P& p : G[n]) if (p.first != rev) {
            dfs(p.first, d+p.second, n, orig);
        }
    }
};

備考

任意の 2 頂点のパターンを見逃してる人が多かった.

SRM 628 Div1 Easy, DivisorsPower

SRM

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13241&rd=16009
{ d(x) } は x の 1 以上 x 以下の約数の個数を表す. { h(x) = x^{d(x)} } とする. 与えられた整数 { n (2 \leq n \leq 10^{18}) } について, { h(x) = n }を満たす最小の x を求めよ. 存在しない場合は -1 を返す.

解法

n \leq 10^{18} より, d(x) の値は最大でも60である. (2^{60} = 1.15 * 10^{18})
d(x) = 2\dots60 について x = n^{1/d(x)} を求め, d(x), x の関係が条件を満たしているかどうか確かめれば良い.

解答

class DivisorsPower
{
public:
    long long findArgument (long long n)
    {
        for (int i = 60; i >= 2; i--) {
            ll x = pow(1.0*n, 1.0/i) + EPS;
            ll p = 1;
            repeat (i) p *= x;
            if (p == n && divisors(x) == i) return x;
        }
        return -1;
    }

    ll divisors(int n) {
        int cnt = 0;
        for (int i = 1; i*i <= n; i++) {
            if (n%i) continue;
            cnt++;
            if (i != n/i) cnt++;
        }
        return cnt;
    }
};

備考

本番では x = 1\dots(10^{18})^{1/4} について h(x) を求めてハッシュマップに保存, d(x) = 2, 3 の場合だけ別処理, みたいなめんどくさいことをしてしまった.
75分まるまる使って AC.

SRM 627 Div1 Easy, HappyLetterDiv1

SRM

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13274

[a-z] のみからなる文字列 L (1 <= |L| <= 50) が与えられる. 一度の操作で, 文字列中の任意の異なる文字ペアを消去する (例えば "aabbc" -> "aab"). この操作を繰り返して, 最後に残ったアルファベットを winning letter と呼ぶ. winning letter になりうるアルファベットを全て求めよ.

解法

あるアルファベット c について, c が winning letter になりうる条件は次の通り.
c 以外の文字に対して操作を繰り返して, 「c の個数 > c 以外の文字の個数」にすることができる

c 以外の文字をうまく減らす戦略を考える. c を除いて最も個数が多い 2 文字を消していく戦略が考えられる. これを実装する.
最適性の証明が出来なくて苦しかったけど, AC だった.

解答

class HappyLetterDiv1
{
public:
    string getHappyLetters (string letters)
    {
        int chars[26] = {};
        for (char c : letters) chars[c-'a']++;
        string ans = "";
        loop (26, i) {
            int cs[26] = {};
            loop (26, j) if (j != i) cs[j] = chars[j];

            while (1) {
                sort(cs, cs+26);
                if (cs[24] == 0) {
                    if (cs[25] < chars[i]) ans += i + 'a';
                    break;
                }
                cs[24]--;
                cs[25]--;
            }
        }
        return ans;
    }
};