プログラミング備忘録

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

深さ優先探索において,引数に母親を指定する

久々の更新ですが,メモを書いておきます. 深さ優先探索において,母親を指定しておくと一回行ったかどうかを判定しなくてもいい.

void dfs (ll i, ll pa = -1) {
  dp[i][0] = 1;
  dp[i][1] = 1;
  for (auto j : box[i]) {
    if (j != pa) {
      dfs(j, i);
      
      dp[i][0] = ((dp[i][0] % mod) * ((dp[j][0] + dp[j][1]) % mod)) % mod;  
      dp[i][1] = ((dp[i][1] % mod) * (dp[j][0] % mod)) % mod;
    }  
  }
}

深さ優先探索において,引数に母親を指定する

久々の更新ですが,メモを書いておきます. 深さ優先探索において,母親を指定しておくと一回行ったかどうかを判定しなくてもいい.

void dfs (ll i, ll pa = -1) {
  dp[i][0] = 1;
  dp[i][1] = 1;
  for (auto j : box[i]) {
    if (j != pa) {
      dfs(j, i);
      
      dp[i][0] = ((dp[i][0] % mod) * ((dp[j][0] + dp[j][1]) % mod)) % mod;  
      dp[i][1] = ((dp[i][1] % mod) * (dp[j][0] % mod)) % mod;
    }  
  }
}

D - Remainder Reminder 〜ABC090〜

問題

D - Remainder Reminder

感想

かなり手こずった... 簡単な方のD問題のはずなのだが.

考え

a, b, k のいずれか一つを全探索する方法でない限り,制約条件的に時間以内にACすることはできない.

bに注目することで,余りの周期性を利用することができるためbaの上限nからあまりがk以上の組み合わせを求めることができる.

aやらkを全探索することを考えてずっと手こずっていました.....悔しい.

Accepted Program

#include <iostream>
#include <math.h>

using namespace std;
#define ll long long

int main () {
  ll n, k;
  ll ans = 0;
  cin >> n >> k;
  if (k == 0) {
    cout << n * n << endl;
    return 0;
  }
  for (ll i = k + 1; i <= n; i++) {
    ans += i - k;
    ll sub = n % i;
    if (sub >= k) {
      ans += sub - k + 1;  
    }
    sub = n / i - 1;
    ans += sub * (i - k);
  }
  cout << ans << endl;
}

D - Wide Flip 〜ABC083〜

問題

D - Wide Flip

はじめに

あけましておめでとうございます。

今年も精進していきます。

考え

計算量をまず考えると,O(NlogN) の解法を思いつかないといけないことに気づく。logNの計算量を持つ解法としてニブタンぐらいしか知らない()ので,とりあえずニブタンでできないか考える。

Kがある値iのとき,Sの要素を0にできるとすると,i以下の値では必ずSの要素を0にすることができるということがわかる。

つまり,配列としてdp[i]:K = i の時成功したら1,成功しなかったら0 と言うように考えると二分探索に落とし込むことができる。なぜならある値iで成功しなかったら,左側(left = mid)として,成功したら,右側(right = mid)とすることができるからである。

なので,最終的には二分探索 + K = iの時に成功できるか否かを決める関数,を実装することで完成する。

Accepted Program

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

int solve (string s, int k, string sub) {
  int sum = 0;
  for (int i = 1; i <= s.size() - k; i++) {
    if (i <= k) {
      int now = s[i] - '0';
      now = (now + sum) % 2;
      if (now == 1) {
        sum++;
        sub[i] = '1';
      }  
    }    
    else {
      if (sub[i - k] == '1') {
        sum++;  
      }  
      int now = s[i] - '0';
      now = (now + sum) % 2;
      if (now == 1) {
        sum++;
        sub[i] = '1';
      }
    }
  } 

  // sub[i] == '1'→ 0と1を回転させた.

  int first = 0; 
  for (int i = (s.size() - k); i < s.size(); i++) {
    int now = s[i] - '0';
    if (i == (s.size() - k)) {
      now = (now + sum) % 2;
      first = now;  
      if (first == 1) {
        sub[i] = '1';  
      }
      else {
        sub[i] = '0';  
      }
    }  
    else {
      if (i - k >= 1) {
        if (sub[i - k] == '1') {
          sum++;  
        }  
      }
      now = (now + sum) % 2;
      if (now == 1) {
        sub[i] = '1';  
      }
    }
  }
  // まずは,連続しているか確かめる
  bool follow = true;
  char last;
  int count = 0; 
  int num = 0;
  for (int i = s.size() - k; i <= s.size() - 1; i++) {
    if (sub[i] == '1') {
      if (k <= (i - 1)) {
        // ok  
      }    
      else {
        follow = false;  
      }
    }
  }
  if (follow) {
    return 1;  
  }
  return - 1;
}

int main () {
  string s;
  cin >> s;
  s = "a" + s;
  string sub;
  for (int i = 0; i < s.size(); i++) {
    sub = sub + "0";  
  }
  int left = 0;
  int right = s.size();
  /*
  for (int i = 1; i <= s.size() - 1; i++) {
    cout << i << " " << solve(s, i, sub) << endl;  
  }
  */
  while (left < right - 1) {
    int mid = (left + right) / 2;
    if (solve(s, mid, sub) == 1) {
      left = mid;  
    }  
    else {
      right = mid;  
    }
  }
  cout << left << endl;
  
}

D - トランプ挿入ソート

問題

D - トランプ挿入ソート

感想

最長増加部分列むずい.....

考え方

どの要素を取り出してもよくて,それからどこに挿入してもよいということなので,取り出さなくてよい数(組)はどのようなものなのかを考えると良い。

要素を取り出して挿入するということは,その取り出した数字はsortされていなかったということになる。つまり,取り出さない数字の組は逆に言うとsort済みということである。

よって,結果的には,与えられた組に対して最長増加部分列を求めればよいことになる。

とはいえ,最長増加部分列の実装はかなり悩みました。解説ではニブタンを使ってますが自分の実装はちょっと変ですね....笑

Accepted Program

#include <iostream>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;

int main () {
  int n;
  cin >> n;
  int a[n + 1];
  map<int, int> box;
  a[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    box[a[i]] = i;
  }
  int dp[n + 2];
  for (int i = 0; i <= n + 1; i++) {
    dp[i] = 0;
  }
  int now = 0;
  for (int i = 1; i <= n; i++) {
    if (i == 1) {
      dp[i] = a[i];
      now = i;
    }  
    else {
      int jmax = a[i] - 1;
      if (a[i] > now) {
        jmax = now;  
      }
      for (int j = jmax; j >= 0; j--) {
        if (dp[j] < a[i]) {
          if (dp[j + 1] > a[i] || dp[j + 1] == 0) {
            dp[j + 1] = a[i];
            now = (j + 1 > now) ? j + 1 : now;
          }    
          break;
        }    
      } 
    }
  }
  int max = -1;
  for (int i = 1; i <= n; i++) {
    if (dp[i] > 0) {
      max = i;  
    }
  }
  cout << n - max << endl;
}

D - サプリメント 〜ABC017〜

問題

D: サプリメント - AtCoder Beginner Contest 017 | AtCoder

考え方

動的計画法を用いる。

AtCoder Beginner Contest 017 解説 の言葉で言う,「dpで足せる区間」を求める際に自分はlatest[i] = jを使った(i というサプリメントが直近で一番最初に出てくる番号はj)。

実装が大変でした。プログラム自体はそこまで長くはないのですが,「dpで足せる区間」が具体的に何に該当するか分かるまでに時間がかかりました。

Accepted Program

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

#define ll long long
#define mod 1000000007
#define max 100001

ll pure[max], latest[max];

void init (void) {
  // 2^n 
  ll sub = 1;
  pure[0] = 1;
  pure[1] = 1;
  latest[1] = -1;
  for (ll i = 2; i < max; i++) {
    latest[i] = -1;
  }
}

int main () {
  init();
  ll n, m;
  cin >> n >> m;
  ll f[n];
  ll ans[n];
  ll sum[n + 1];
  sum[0] = 0;
  ll num[n];
  bool ok[n];
  for (ll i = 0; i < n; i++) {
    cin >> f[i];  
    ans[i] = 0;
    sum[i + 1] = 0;
    num[i] = 0;
    ok[i] = false;
  } 
  for (ll i = 0; i < n; i++) {
    if (i == 0) {
      num[i] = 1;
      latest[f[i]] = 0;  
    }    
    else {
      if (latest[f[i]] == -1) {
        num[i] = num[i - 1] + 1;  
      }  
      else {
        // まずは i の位置とlatest[f[i]]の位置の差を見て
        // num[i - 1]との関係を求める.  
        int j = i - num[i - 1];
        int l = latest[f[i]];
        if (j > l) {
          ok[i] = true;
          num[i] = num[i - 1] + 1;  
        }
        else {
          num[i] = i - l;   
        }
      }
      latest[f[i]] = i;
    }
  }
  for (ll i = 0; i < max; i++) {
    latest[i] = -1;  
  }
  for (ll i = 0; i < n; i++) {
    if (i == 0) {
      ans[i] = 1;
    }    
    else {
      if (num[i] == i + 1) {
        ans[i] = (ans[i - 1] * 2) % mod;  
      }
      else {
        if (ok[i]) {
          ans[i] = (ans[i - 1] * 2) % mod;  
        }
        else {
          ans[i] = (ans[i - 1]) % mod;
          ans[i] = (ans[i] + sum[i - 1]) % mod;
          ans[i] = (ans[i] + mod - sum[i - num[i]]) % mod;     
        }
      }
    }
    sum[i + 1] = (sum[i] + ans[i]) % mod;
    latest[f[i]] = i;
  }
  cout << ans[n - 1] << endl;
}