2018-12-14

D - 語呂合わせ〜ABC031〜

問題

考え方

深さ優先探索でぐるぐる回す。n の数だけクエリがあるが，これを全部足し合わせて一つの文字列 sum_v, sum_w について深さ優先探索をすると楽に解ける。

計算量が気になったが，各語呂合わせの文字の制約で3文字以下に収まるということがあったので多分大丈夫であった。

Accepted Program

#include <iostream>
#include <string>
using namespace std;

int stamp[10] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0  
};

string sum_v = "";
string sum_w = "";
int k, n;
string ans[9 + 1];
string v[51], w[51];

bool dfs (int s, int ss) {
  if (s >= sum_v.size() && ss < sum_w.size()) {
    return false;  
  }
  if (ss >= sum_w.size() && s < sum_v.size()) {
    return false;  
  }
  if (s == sum_v.size() && ss == sum_w.size()) {
    for (int i = 0; i < n; i++) {
      string sub = "";
      for (int j = 0; j < v[i].size(); j++) {
        int itr = v[i][j] - '0';
        sub = sub + ans[itr];   
      }   
      if (sub != w[i]) {
        return false;  
      }
    }      
    return true;
  }
  int now = sum_v[s] - '0';
  if (stamp[now] == 1) {
    for (int i = 0; i < ans[now].size(); i++) {
      if (ss + i >= sum_w.size()) {
        return false;  
      }
      if (ans[now][i] != sum_w[ss + i]) {
        return false;    
      }  
    }  
    return dfs(s + 1, ss + ans[now].size());
  }
  else {
    string sub = "";
    for (int i = 0; i < 3; i++) {
      stamp[now] = 1;
      if (ss + i >= sum_w.size()) {
        stamp[now] = 0;
        break;  
      }
      sub += sum_w[ss + i];
      ans[now] = sub;
      if (dfs(s + 1, ss + i + 1)) {
        return true;  
      } 
      stamp[now] = 0;
    }
    return false;
  }
}

int main () {
  cin >> k >> n;
  for (int i = 0; i < n; i++) {
    cin >> v[i] >> w[i];   
    sum_v += v[i];
    sum_w += w[i];
  }  
  for (int i = 0; i <= k; i++) {
    ans[i] = "";    
  }
  if (dfs(0, 0)) {
    for (int i = 1; i <= k; i++) {
      cout << ans[i] << endl;     
    }
  }
}

2018-12-06

C - 高橋くんのバグ探し〜ABC015〜

あとで解く問題

問題

C - 高橋くんのバグ探し

Accepted Program

#include <iostream>
#include <vector>

using namespace std;

int dp[5][5];

int main () {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> dp[i][j];  
    }  
  }
  vector<int> ans;
  for (int i = 0; i < m; i++) {
    ans.push_back(dp[0][i]);  
  }
  int num = 1;
  while (num < n) {
    vector<int> sub;
    for (int i = 0; i < ans.size(); i++) {
      for (int j = 0; j < m; j++) {
        sub.push_back(ans[i] ^ dp[num][j]);    
      }  
    }    
    ans = sub;
    num++;
  }
  for (int i = 0; i < ans.size(); i++) {
    if (ans[i] == 0) {
      cout << "Found" << endl;
      break;  
    }
    if (i == ans.size() - 1) {
      cout << "Nothing" << endl;  
    }
  }
}

2018-12-04

C - 友達の友達〜ABC016〜

あとで解く問題

問題

C - 友達の友達

考え方

制約条件が難しくないので割と簡単です。例えば，以下のようにして解くことができます。

ある人Aとして，Aが友達Bを見て友達Bをチェックしておく（ set などで）→その友達Bの友達Cを見る→ Cがset に入っていない友達だったら，AにとってCは友達の友達

ただダイクストラ法の勉強にもなるのでそっちで解くのがオススメかなと思います。（今回は上の愚直解で書いてみました。）

Accepted Program

#include <iostream>
#include <set>
using namespace std;

int stand[11];
int dp[11][11];

void init (int n, int num) {
  for (int i = 0; i <= n; i++) {
    stand[i] = 0;  
  } 
  if (num == 0) {  
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= n; j++) {
        dp[i][j] = 0;  
      }  
    }
  }
}

int dfs(int n, int x) {
  set<int> ans;
  stand[x] = 1;
  for (int i = 1; i <= n; i++) {
    if (dp[x][i] == 1 && stand[i] == 0) {
      stand[i] = 1;
      for (int j = 1; j <= n; j++) {
        if (dp[i][j] == 1 && stand[j] == 0) {
          ans.insert(j);  
        }  
      }  
      stand[i] = 0;
    } 
  }  
  int answer = ans.size();
  for (auto q = ans.begin(); q!= ans.end(); ++q) {
    if (dp[x][*q] == 1) {
      answer--;  
    }    
  }
  return answer;
}

int main () {
  int n, m;
  cin >> n >> m;
  init (n, 0);
  int s, ss;
  for (int i = 0; i < m; i++) {
    cin >> s >> ss;
    dp[s][ss] = 1;
    dp[ss][s] = 1;  
  }    
  for (int i = 1; i <= n; i++) {
    init(n, i);
    cout << dfs(n, i) << endl;  
  }
}

2018-12-03

C - 菱型カウント〜ABC021〜

競技プログラミング

問題

C - 菱型カウント

感想

やるだけではあると思うのですが，実装が重いのでめんどくさかったです。こういう問題苦手。自分はプログラミングが向いてないなと実感する問題ですね笑.....

考え

(i, j) 点に関して全探索をする。そして，上下左右に Kの幅を伸ばして白であるか確かめる必要があります。この時に上下左右の両方（二方向）で K について全探索すると $O(RCKK)$ となり TLE となるので，片方の方向だけ全探索をして，もう片方は部分和を使って全探索を省く必要があるでしょう。

Accepted Program

#include <iostream>
using namespace std;
#define ll long long

int main () {
  int h, w, k;
  cin >> h >> w >> k;
  string str[h];
  for (int i = 0; i < h; i++) {
    cin >> str[i];  
  }
  ll ans = 0;
  ll sum[h][w];
  for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      sum[i][j] = 0;
      if (j == 0) {
        if (str[i][j] == 'x') {
          sum[i][j] = -1;  
        }  
        if (str[i][j] == 'o') {
          sum[i][j] = 0;  
        }
      }  
      else {
        if (str[i][j] == 'x') {
          sum[i][j] = sum[i][j - 1] - 1;  
        }  
        if (str[i][j] == 'o') {
          sum[i][j] = sum[i][j - 1];  
        }
      }
    }  
  }
  for (int i = k - 1; i <= h - k; i++) {
    for (int j = k - 1; j <= w - k; j++) {
      for (int l = 0; l < k; l++) {
        if (l == k - 1) {
          if (str[i - l][j] != 'o' || str[i + l][j] != 'o') {
            break; 
          }  
        }
        else {
          int yoko = k - l - 1;
          if (j - yoko == 0) {
            if (sum[i - l][j + yoko] != 0) {
              break;
            }  
            if (sum[i + l][j + yoko] != 0) {
              break;
            }
          }  
          else {
            if (sum[i - l][j + yoko] - sum[i - l][j - yoko - 1] != 0) {
              break;
            }  
            if (sum[i + l][j + yoko] - sum[i + l][j - yoko - 1] != 0) {
              break; 
            }
          }
        }
        if (l == k - 1) {
          ans++;  
        }
      }         
    }  
  }
  cout << ans << endl;
}

2018-11-30

C - 収集王〜ABC023〜

競技プログラミング

問題

C - 収集王

感想

飴があるところとないところを分けて考えることが難しかった。この分け方を思いつくまでにかなりの時間を要しました。

難しかったけれどその分解法を思いついた時の嬉しさはひとしおでしたね。

考え

まず，(i, j) について二重ループを回すことを思いついた。つまり，

各マス目を全探索する
(i, j)のとき獲得する飴の個数は，各 i行，j 列についての累積和（総数）を先に計算しておいて求める。

ということだが，条件より各マスを探索するとTLEになってしまう。なので全探索をしないで求める必要がある。

次に思いついたのは，各マスを考えるのではなく，行と列に分けて求めるということである。つまり，

i 行目，j 列目の飴の総数（sum_r[i], sum_c[j] とした）を記録しておく。
記録した後で，行と列ごとに飴の総数を記録する。（行についてみたときに飴の数が1個とれる行は sc[1]つ，2個とれる行は sc[2]つ...，列についてみたときに飴の数が1個とれる列は sr[1]つ...というように）
K個獲得するということは，行についてみたときに num 個とれて，列についてみたときに K - num 個とれるということに対応するので，K 回ループさせる。

ただしかし，ここで問題となるのは，飴がある場所については，sum_r[i]，sum_c[j] が二重でカウントされていることである。

なので，上記の手順で計算して求められた値 ans に対して，「飴がある場所に移動してかつ，総数が K - 1 であったマスの数」を引いて，「飴がある場所に移動してかつ，総数が `K であったマスの数」を足す必要がある。

Accepted Program

#include <map>
#include <iostream>
using namespace std;
#define ll long long
int main () {
  ll R, C , K;
  cin >> R >> C >> K;
  ll N;
  cin >> N;
  ll r[N], c[N];
  ll sum_r[R], sum_c[C];
  ll sr[R + 1], sc[C + 1];
  for (ll i = 0; i < R; i++) {
    sum_r[i] = 0;  
    sr[i] = 0;  
  }
  sr[R] = 0;
  for (ll i = 0; i < C; i++) {
    sum_c[i] = 0;  
    sc[i] = 0;  
  }
  sc[C] = 0;
  for (ll i = 0; i < N; i++) {
    cin >> r[i] >> c[i];
    r[i]--;
    sum_r[r[i]]++;
    c[i]--;  
    sum_c[c[i]]++;
  }
  for (ll i = 0; i < R; i++) {
    sc[sum_r[i]]++;
  }
  for (ll i = 0; i < C; i++) {
    sr[sum_c[i]]++;
  }
  ll ans = 0;
  for (ll i = 0; i <= K; i++) {
    if (K - i <= C && i <= R) {
    ans += sr[i] * sc[K - i];    
    }
  }
  ll plus, minus;
  plus = 0;
  minus = 0;
  for (ll i = 0; i < N; i++) {
    if (sum_r[r[i]] + sum_c[c[i]] - 1 == K - 1) {
      minus++;  
    }     
    if (sum_r[r[i]] + sum_c[c[i]] - 1 == K) {
      plus++;    
    }
  }
  ans = ans - minus + plus;
  cout << ans << endl;
}

2018-11-26

C - 数式の書き換え〜ABC033〜

競技プログラミング

問題

C - 数式の書き換え

感想

フェルマーの小定理と繰り返し二乗法を使った。
とてもためになった問題でした。
昔のC問題むずすぎないか....笑

考え

フェルマーの小定理 $a^{p} \equiv a$ $（modp）$ を利用します。 $(p = 1000000007)$

$x = 3, y = 3$ のときは，求める解は組み合わせを考えて $_{x - 1 + y - 1} C _{y - 1}$ となります（これを $\displaystyle \frac{s}{t}$ とします）。このとき，割る動作を行わなければいけません。割る動作は $x, y$ が十分に大きくない時にはできるのですが，大きくなるとオーバーフローを招いてしまいます。分子を先に $modp$ で考えておくことができなくなるからです。

つまり，割る動作を行うとすると

分子を求める（この時 $modp$ で考えれない）
分子の値を割っていく
最後に $p$ で割ってその時の余りが答えとなる

ということになるのですが，最初の分子を求める過程でオーバーフローしてしまうでしょう。この分子の値を割るという動作をしないで解を求める時に使うのがフェルマーの小定理です。

フェルマーの小定理は， $a, p$ が互いに素であるとき， $a^{p-1} \equiv 1$ となります。つまり，

$\displaystyle \frac{s}{t} × 1 \equiv \displaystyle \frac{s}{t} × a^{p - 1}$

となります。ここで $a = t$ とすれば割る動作をなくすことができます。 $s × t^{p - 2}$ の $p$ での余りを求めれば解を得ることができるのです。 $t^{p - 2}$ の求め方については繰り返し二乗法を用いましょう。

Accepted Program

#include <iostream>
#define ll long long
#define mod 1000000007
using namespace std;

ll db (ll x, ll y) {
  // xをy乗する
  if (y == 1) {
    return (x % mod);  
  }
  if (y % 2 == 0) {
    ll sub = (db(x, y / 2) % mod);
    return ((sub % mod) * (sub % mod)) % mod;
  }  
  else {
    return ((x % mod) * (db(x, y - 1)) % mod) % mod;  
  }
}

int main () {
  ll w, h;
  cin >> w >> h;
  w = w - 1;
  h = h - 1;
  if (h > w) {
    swap(h, w);  
  }
  ll ans = 1;
  ll sub = 0;
  
  // (w + h) C (h)
  // 1. 分母
  for (ll i = 0; i < h; i++) {
    sub = w + h - i;
    ans = ((ans % mod) * (sub % mod)) % mod;
  }   
  // 2. 分子
  sub = 1;
  for (ll i = 1; i <= h; i++) {
    sub = ((sub % mod) * (i % mod)) % mod;    
  }
  // cout << ans << " " << sub << endl;
  // return 0;
  sub = db(sub, mod - 2);
  cout << ((ans % mod) * (sub % mod)) % mod << endl;
}

2018-11-19

C - たくさんの数式 / Many Formulas 〜ABC045〜

競技プログラミング

問題

C - たくさんの数式 / Many Formulas

考え

入力を文字列として受け取り，それについてどこに+を入れるか全探索すればACとなる。

例えば"125"を受け取った時，

"1" + "25"
"12" + "5"
"125" ...

のように+を挟んでいくが，これは文字列"125"に関して数字の間に+を入れていくことに対応する。つまり，"1/2/5"のように考えて，/に+を入れるかあるいは入れないかを考えていけばよい。

ただ，実装は難しかった。自分はまず/の数を数えて（xとする），0 ~ 2^xに対して全探索をする。そして，0 ~ 2^xの中のあるiについて 0, 1の1bitで構成される文字列に対応させた。つまり，"125"が入力として/の数は2であり，i = 1とすると01という文字列（s）を対応させた。これにより，このときの数字の和としては，12 + 5に対応している。同様にi = 2ならば，s = "10"であり，数字の和は1 + 25となる。

愚直にfor文をx重に回してもいいとは思ったけれど，少しかっこ悪いよね笑。

Accepted Program

#include <iostream>
#include <algorithm>
#include <bitset>
#include <string>
using namespace std;

string to_binString(int value, int length) {
  string h;
  if (value == 0) {
    h = "0";  
  }  
  while (value != 0) {
    if ((value & 1) == 0) {
      h.insert(h.begin(), '0');  
    }    
    else {
      h.insert(h.begin(), '1');  
    }
    value >>= 1;
  }
  // hを0詰めする
  while (length != h.size()) {
    h.insert(h.begin(), '0');  
  }
  return h;
}

int main () {
  string h;
  cin >> h;
  if (h.size() == 1) {
    cout << stoi(h) << endl;
    return 0;  
  }
  long long forloop = 1;
  for (int i = 0; i < h.size() - 1; i++) {
    forloop *= 2;  
  }
  long long ans = 0;
  for (long long i = 0; i < forloop; i++) {
    string s = to_binString(i, h.size() - 1);
    long long before = 0;
    long long sub = 0;
    for (long long j = 0; j < s.size(); j++) {
      if (s[j] == '1') {
        sub += stol(h.substr(before, j - before + 1));
        before = j + 1;     
      }  
    }
    sub += stol(h.substr(before, h.size() - before));
    ans = ans + sub;
  }
  cout << ans << endl;
}

プログラミング備忘録

日頃のプログラミングの成果をここに書いていきます．

D - 語呂合わせ〜ABC031〜

問題

考え方

Accepted Program

C - 高橋くんのバグ探し〜ABC015〜

問題

Accepted Program

C - 友達の友達〜ABC016〜

問題

考え方

Accepted Program

C - 菱型カウント〜ABC021〜

問題

感想

考え

Accepted Program

C - 収集王〜ABC023〜

問題

感想

考え

Accepted Program

C - 数式の書き換え〜ABC033〜

問題

感想

考え

Accepted Program

C - たくさんの数式 / Many Formulas 〜ABC045〜

問題

考え

Accepted Program