2019-03-29

ARC003B さかさま辞書

問題概要

\(N\)個の文字列が与えられた時、それぞれの文字列の末尾から逆順に並べた辞書を作成しようとしている。
与えられた文字列から逆順に並べた辞書を作成し、元の文字列をその逆順辞書の順番で出力する。

制約

\(1≤N≤100\)
文字列は全て英小文字からなる。

問題へのリンクはこちら

考えたこと

元の文字列を後ろから読んだ文字列と、元の文字列自身を一つのペアとして管理する。この時、pair<string, string> を使用するが、pairの第一引数には、反転させた文字列を入れるようにする。(理由は後述)
上で作成したpair文字列の組を配列に格納していく。
全てのpairを配列に入れ終わったら、配列を並び替える。この時、C++のstd::sortは、pairの第一引数を基準に並べ替えてくれる。そのため、上のようなpairの引数構成となっている。

書いたコード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N; cin >> N;
  vector<pair<string, string> > v(N);
  for(int i = 0; i < N; ++i) {
    string s; cin >> s;
    v[i].first = s;
    v[i].second = s;
    reverse(v[i].first.begin(), v[i].first.end());
  }
  sort(v.begin(), v.end());
  for(int i = 0; i < N; ++i) {
    cout << v[i].second << endl;
  }

  return 0;
}

2019-03-28

ARC34B

問題概要

正整数\(n\)に対し、\(n\)の十進表記における各桁の和を\(f(n)\)で表す。正整数\(N\)が与えられた時に、\(x+f(x)=N\)を満たす正整数\(x\)を全て求めよ。

制約

\(1≤N≤\)10¹⁸

考えたこと

Nの制約が 10¹⁸ ということもあり、\(O(N)\)のアルゴリズムではTLEしてしまう。
\(f(x)\) は桁和であるため、\(f(x)\) の最大値を考えてみると、\(9 \times 17 < 200\) とわかる。
そのため、\(N-200 <= x < N\)として\(f(x) = N-x\)というこの等式を満たす\(x\)の個数とその値を求めればよいという問題に帰着できる。

書いたコード

#include <bits/stdc++.h>
using namespace std;

long long f(long long x) {
  string X = to_string(x);
  long long sum = 0;
  for(int i = 0; i < X.size(); ++i) {
    sum += (long long)(X[i] - '0');
  }
  return sum;
}

int main() {
  long long N; cin >> N;
  long long cnt = 0;
  vector<long long> v;
  for(long long x = N; x >= N - 200; x--) {
    if(f(x) == N-x) {
      cnt++;
      v.push_back(x);
    }
  }
  cout << cnt << endl;
  if(cnt != 0) {
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); ++i) {
      cout << v[i] << endl;
    }
  }
  return 0;
}

2019-02-19

ABC99 C - Strange Bank

問題概要

ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかである。
- 1 円
- 6 円、 6² 円、 6³ 円
- 9 円、 9² 円、 9³ 円

この銀行からちょうどN 円を引き出す時の最小引き出し回数を求めよ。

制約

1 ≤ N ≤ 100000
N は整数

問題へのリンクはこちら

考えたこと

貪欲法でいけないかどうか Nを超えない最大の6または9の倍数で引いていく方針を考える。しかしながら、N = 12の時、この方針だとうまくいかないため、(12→3→2→1→0 よりも12→6→0 の方が回数が少ないため。) =>違う方針を検討
DPを用いる。
n-1回目からn回目への遷移を考えると、1円を引けばいいため、回数は一回増える。
n-6回目からn回目への遷移は、6円を引けばいいため、回数が一回増える

このような遷移を6,9のべき乗に対して考えてあげた上で、回数の最小値がdp[N] の答えとなる。

#include<bits/stdc++.h>
using namespace std;
int NMAX = 100000;
int dp[NMAX+10];

int main() {
  int N; cin >> N;
  dp[0] = 0;
  for(int n = 0; n <= NMAX; ++n) {
    dp[n] = NMAX;
    int power = 1;
    while(power <= n) {
      dp[n] = min(dp[n], dp[n-power] + 1);
      power *= 6;
    }
    power = 1;
    while(power <= n) {
      dp[n] = min(dp[n], dp[n-power] + 1);
      power *= 9;
    }
  cout << dp[N] << endl;
  return 0;
}

2019-02-19

ABC96 C-Grid Repainting 2

問題概要

H行W列のマス目で表されるキャンバスがあり、最初、全てのマス目は白色である。
このキャンバスに黒い絵の具を使って絵を描く時、\(s_{i,j}\) = '#'の時、マス(i, j)を黒色、\(s_{i,j}\) ='.'の時、マス(i, j)を白色にすることがゴールである。
しかし、黒く塗る時、次のような制約の下で塗らなければいけない
- 上下左右に隣接する２つのマスを選び両方黒く塗る
- すでに黒く塗られているマスを選ぶこともでき、この時は黒のまま

ゴールの図形を描くことができるかどうかを判定せよ。

制約

Hは1以上50以下の整数
Wは1以上50以下の整数

問題へのリンクはこちら

考えたこと

孤立する#が存在しなければ必ずゴールとなる図形を描写できる。ただし、ここでいう孤立とは、#の上下左右が全て.で表されるような状況のことを指す。
マスの数が50 \(\times\) 50 程度しかないため、全探索で求められる。

#include<bits/stdc++.h>
using namespace std;
// 上下左右を表すための配列
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int HMAX=50;
const int WMAX=50;

int main() {
  int h, w; cin >> h >> w;
  char s[WMAX][HMAX];
  for(int y = 0; y < h; ++y) {
    for(int x = 0; x < w; ++x) {
      cin >> s[x][y];
    }
  }
  for(int y = 0; y < h; ++y) {
    for(int x = 0; x < w; ++x) {
      if(s[x][y] == '#') {
        int cnt = 0;
        for(int i = 0; i < 4; ++i) {
          if(s[x+dx[i]][y+dy[i]] == '#') cnt++;
        }
        if(cnt == 0) {
          cout << "No" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Yes" << endl;

  return 0;
}

2019-02-18

ABC 89 C-March

問題概要

N人の人がいて、i番目の人の名前は\(S_i\)
この中から、以下の条件を満たすように3人を選ぶ
- 全ての人の名前がM, A, R, C, H のどれかから始まる
- 同じ文字から始まる名前を持つ人が複数いない
これらの条件を満たすように3人を選ぶ方法の総数を求めよ。ただし、選ぶ順番は考えない。
答えが32bit整数型に収まらない場合に注意せよ。

制約

1 ≤ N ≤ 10⁵
\(S_i\)は英大文字からなる
1 ≤ \(S_i\) ≤ 10
\(S_i \neq S_j, (i \neq j)\)

問題へのリンクはこちら

考えたこと

5つの文字から3つの文字を選ぶ方法はたかだか10通り
それぞれの文字が何回出たかを管理するための配列を用意して、上で選んだ３つの配列の個数の積を足し合わせる

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll backet[5] = {0};

int main() {
  int n; cin >> n;
  // どの３つが選択されたかを表す配列３つ
  int p[10] = {0,0,0,0,0,0,1,1,1,2};
  int q[10] = {1,1,1,2,2,3,2,2,3,3};
  int r[10] =  {2,3,4,2,4,4,3,4,4,4};
  
  for(int i = 0; i < n; ++i) {
    string s; cin >> s;
    if(s[0] == 'M') bucket[0]++;
    else if(s[0] == 'A') bucket[1]++;
    else if(s[0] == 'R') bucket[2]++;
    else if(s[0] == 'C') bucket[3]++;
    else if(s[0] == 'H') bucket[4]++;
  }
  ll ans = 0;
  for(int i = 0; i < 10; ++i) {
    ans += bucket[p[d]] * bucket[q[d]] * bucket[r[d]];
  }
  cout << ans << endl;
  
  return 0;
}

2019-02-18

ABC76 C-Dubious Document2

問題概要

宝物が入っていそうな箱を開けたいが鍵がかかっている。
この箱には鍵がかかっていて、開けるためには、英小文字からなる文字列Sが必要
鍵となりうる文字列S'を見つけ、これは、文字列Sの0個以上|S|個いないの文字が'?'に置き換わった文字列である。
鍵を解くためのヒントが書かれた紙には次の2つのことが書かれていた。
- 文字列Sの中に連続する部分文字列として英小文字からなる文字列Tが含まれている。
- Sは、上の条件を満たす文字列の中で辞書順最小の文字列この時、鍵となる文字列Sを出力せよ。ただし、そのような文字列Sが存在しない場合は、'UNRESTORABLE'と出力せよ。

制約

1 ≤ |S'|, |T| ≤ 50
S'は英小文字と?からなる
Tは英小文字からなる

問題へのリンクはこちら

考えたこと

Tとマッチするような文字列をおける可能性のあるのはSの頭から数えて何文字目か(これをkとする)を求める。
これが見つからない場合は、UNRESTORABLEを出力
見つかった場合は、s[k+i] = t[i]を埋めたのち、残りの?を辞書順最小を満たすためにaで埋める

#include<bits/stdc++.h>
using namespace std;
string s, t;

bool match(int k) {
  for(int i = 0; i < t.length(); ++i) {
    if(t[i] != s[i+k] && s[i+k] != '?') return false;
  }
  return true;
}

string construct(int k) {
  string ans = s;
  for(int i = 0; i < t.length(); ++i) {
    ans[k+i] = t[i];
  }
  for(int i = 0; i < s.length(); ++i) {
    if(ans[i] == '?') ans[i] = 'a';
  }
  return ans;
}

int main() {
  cin >> s >> t;
  int k = -1; // マッチする文字列が見つからなかったために-1で初期化
  string ans;
  for(int i = 0; i < s.length() - t.length() + 1; ++i) {
    if(match(i)) k = i;
  }
  if(k==-1) {
    cout << "UNRESTORABLE" << endl;
  } else {
    ans = construct(k);
    cout << ans << endl;
  }
  return 0;

2019-02-16

ABC75 C問題

問題概要

自己ループと二重辺を含まない\(N\)頂点\(M\)辺の無向連結グラフが与えられる。
\(i\)番目の辺は頂点\(a_i\)と頂点\(b_i\)を結ぶ。
グラフから辺を取り除いた時、グラフ全体が火連結になるような辺のことを橋と呼ぶ時、橋の本数を求めよ。

制約

\(2 ≤ N ≤ 50\)
\(N-1 ≤ M ≤ min(N(N-1)/2, 50)\)
\(1 ≤ a_i < b_i ≤ N\)
与えられるグラフは自己ループと二重辺を含まない
与えられるグラフは連結である。

考えたこと

無向グラフのアルゴリズムには前回ABC54 C問題と同様に深さ優先探索を用いる(他にも幅優先探索、UnionFind, ワーシャル・フロイド法などが利用できるらしい)
dfsでは、N個の頂点それぞれに訪問したかどうかを調べる目的で使用する。

#include<bits/stdc++.h>
using namespace std;
const int ilmit=50;
bool graph[limit][limit];
bool visited[limit];
int n, m;
int a[limit], b[limit];

bool dfs(int v) {
  visited[v] = true;
  for(int v2 = 0; v2 < n; ++v2) {
    if(graph[v][v2] == false) continue; // そもそも辺がなければスキップ
    if(visited[v2]) continue;
    visited[v2] = true;
    dfs(v2);
  }
}

int main() {
  cin >> n >> m;
  for(int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = true // グラフ上に辺があることを示す
  }
  
  int ans = 0;
  for(int i = 0; i < m; ++i) {
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = false; // 一つの辺を取り除く
    for(int j = 0; j < n; ++j) visited[j] = false; // どの頂点もまだ訪れていないということを表現
    dfs(0); // 頂点1から探索開始

    bool bridge = false;
    for(int j = 0; j < n; ++j) if(visited[j] == false) bridge = true;
    if(bridge) ans += 1;
  
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = true; // 取り除いた辺を復元
  }
  cout << ans << endl;

  return 0;
}