atcoder ABC 087 D - Grid Components

問題

D - Grid Components

解法

• $ h, w $ は 100以下という条件なので、$ h = 100, w = 100 $ で固定して考える
• $ 1 \leq A \leq 500, 1 \leq B \leq 500 $ の制約であれば、100x100 の 半分 50x50 の領域に500個の連結成分を作ることは可能

上記を前提として考えると、100x100の半分ずつの領域で白、黒それぞれ連結成分を必要数作ればよいことがわかる。

1-50行目を黒、51-100行目を白で初期化しておき、1-50行目で白の連結成分、51-100行目で黒の連結成分を作ることを考える。

連結成分は上下左右に隣合わなければ良いので、今回の制約であれば1行飛ばしでも収まるので以下のように並べて解ける。

.#.#.#.#.#
##########
.#.#.#.#.#
##########

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int a,b;
const int h=100,w=100;
char g[h][w];

int main() {
  cin >> a >> b;
  a--; b--;

  REP(i,h) REP(j,w) g[i][j] = i<h/2 ? '#' : '.';

  for (int i=0; i<h; i+=2) {
    if (h/2+(h/2)%2+2 == i) swap(a,b);
    for (int j=0; j<w; j+=2) {
      if (a==0) break;
      g[i][j] = g[i][j] == '.' ? '#' : '.';
      a--;
    }
  }

  cout << h << " " << w << endl;
  REP(i,h) REP(j,w) {
    cout << g[i][j];
    j == w-1 && cout << endl;
  }
}

atcoder ABC 087 D - People on a Line

問題

D - People on a Line

解法

以下の有向グラフを作り、DFSで頂点間の距離に矛盾が生じていないかを調べる。

• $ L_i $ から $ R_i $ まで距離 $ D_i $
• $ R_i $ から $ L_i $ まで距離 $ -D_i $

ただし、M個の入力から得られるグラフは連結していない場合があるため、その場合を考慮しなければならない。

n個全ての点について調べることで、連結していない場合もカバーできる。

#include <bits/stdc++.h>
using namespace std;
#define COUT(x) cout<<(x)<<"\n"
#define REP(i, n) for(int i=0;i<n;i++)
using P = pair<int,int>;
using ll = long long;
const int INF = 1e9;

int n,m;
vector<vector<P>> g(100010);

void dfs() {
  queue<P> q;
  vector<int> dist(n, INF);

  // 全ての点について矛盾がないか調べる
  // グラフが連結していないケースがあるためnまでループして調べる
  REP(i,n) {
    if (dist[i] != INF) continue; // チェック済み

    // スタート地点は距離0とする
    q.push({ i, 0 });
    dist[i] = 0;
    while(!q.empty()) {
      auto v = q.front(); q.pop();
      int p = v.first;

      for(auto x: g[p]) {
        int np = x.first;
        int nd = dist[p] + x.second;

        if (dist[np] == INF) {
          dist[np] = nd;
          q.push(x);
        } else {
          // 距離に矛盾があるため終了
          if (dist[np] != nd) { COUT("No"); return; }
        }
      }
    }
  }
  COUT("Yes");
}

int main() {
  cin >> n >> m;

  // m == 0 の場合はそもそも矛盾しない
  if (m == 0) { COUT("Yes"); return 0; }

  vector<int> l(m),r(m),d(m);
  REP(i,m) {
    cin >> l[i] >> r[i] >> d[i];
    l[i]--; r[i]--; // 0 index
  }

  REP(i,m) {
    g[l[i]].push_back({r[i], d[i]});
    g[r[i]].push_back({l[i], -d[i]});
  }

  dfs();
  return 0;
}

リキッドレイアウトの特定行へ差し込み要素を入れる

リキッドレイアウトで並べられたアイテムの特定行に差し込み要素を入れたい。

イメージ: 赤枠がアイテム、青枠が差込要素

リキッドレイアウトでは横幅によって1行に並ぶアイテム数が可変となる。

表示するウィンドウの横幅によっては1行3個の場合もあれば、10個の場合もあるため、動的に差込位置を決定する必要がある。

ウィンドウサイズが決まれば1行の個数が決定するため、resizeイベントで都度算出してやればよい。

Vue.js での例 codepen.io

atcoder ABC 179 D - Leaping Tak

問題

D - Leaping Tak

解法

素直にDPで解けそうだが、愚直にnに対して全ての移動を試すと $ O(N{^2}) $ となり $ 2≤N≤2×10{^5} $ の制約下でTLEしてしまう。

// このコードはTLEする
#include <bits/stdc++.h>
using namespace std;
#define COUT(x) cout<<(x)<<"\n"
#define REP(i, n) for(int i=0;i<n;i++)
#define endl "\n"
using ll = long long;
const int MOD = 998244353;

int main() {
  int n,k; cin >> n >> k;
  vector<int> l(k),r(k);
  REP(i,k) cin >> l[i] >> r[i];
  vector<ll> dp(n+1); // dp[マスi] = マスiに到達できる場合の数

  dp[1] = 1; // マス1から始まるため dp[1] = 1 にする
  for (int i = 2; i <= n; i++) {
    REP(j,k) {
      for(int k = l[j]; k <= r[j]; k++) {
        if (i-k < 0) continue;
        dp[i] += dp[i-k];
        dp[i] %= MOD;
      }
    }
  }
  COUT(dp[n]);
  return 0;
}

上記ではTLEするため、計算量を落とす方法を考える。

dpの累積和を取り、累積和の区間差分 dpsum[left] - dpsum[right] を取ることでその範囲の場合の数が得られることを利用し、計算量を落とす。

int main() {
  int n,k; cin >> n >> k;
  vector<int> l(k),r(k);
  REP(i,k) cin >> l[i] >> r[i];
  vector<ll> dp(n+1), dpsum(n+1);

  dp[1] = 1; // マス1から始まるため dp[1] = 1 にする
  dpsum[1] = 1; // dpの累積和

  for (int i = 2; i <= n; i++) {
    REP(j,k) {
      int li = max(i-r[j], 1);
      int ri = i-l[j];
      if (ri < 0) continue;

      dp[i] += dpsum[ri]-dpsum[li-1]; // 累積和の差からleft-right間の場合の数を得る
      dp[i] = dp[i] < 0 ? dp[i]+MOD : dp[i]%MOD; // MOD計算
    }
    dpsum[i] = (dpsum[i-1]+dp[i]) % MOD;
  }
  COUT(dp[n]);
  return 0;
}

atcoder ABC 178 C - Ubiquity

問題

C - Ubiquity

公式解説にある通り、包除原理を理解していれば数行で解ける問題。

包除原理にたどり着けず納得が行かなかったので公式解説動画で言及されていたDP解法で解いてみた。

DP解法

DPは [N][0を含んでいるかどうか][9を含んでいるかどうか] で取る。

4重ループで数え上げていき、dp[n][1][1] が最終的に長さnで0,9を含む数列の数となる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0;i<n;i++)
using ll = long long;
const int MOD = 1e9+7;

int n;
int dp[1000010][2][2]; // [N][0を含むかどうか][9を含むかどうか]

// DP解法
void solve() {
  dp[0][0][0] = 1;
  REP(i,n) {
    REP(j,2) {
      REP(k,2) {
        REP(x,10) {
          int nj = j | x == 0;
          int nk = k | x == 9;
          dp[i+1][nj][nk] += dp[i][j][k];
          dp[i+1][nj][nk] %= MOD;
        }
      }
    }
  }
  cout << dp[n][1][1] << endl;
}

int main() {
  cin >> n;
  solve();

  return 0;
}

GitFlowでmasterブランチにマージしたあとのrevert作業メモ

想定ケース

• GitFlowによるdevelop/masterブランチ運用。
• develop, master ブランチは保護ブランチ。基本的にはGitHub上でのPRベースでマージを行う。

feature ブランチで作業

例として newfile.txt というテストファイルを追加する作業を行う

$ git checkout -b feature origin/develop
$ touch newfile.txt
$ git add newfile.txt
$ git commit -m 'Add newfile'
$ git push origin feature

feature -> develop へマージ

GitHub で developブランチへ向けてPR作成、マージ

develop -> master へマージ

master コミットログ。featureブランチで作業したAdd newfile コミットが入っていることを確認

masterブランチでRevertを行う

revertした masterブランチから develop へのマージを行う

ここから再度revertした作業を戻して master にマージする場合

この時点では develop -> master に差分はない

revert した内容を revert することで取り消したrevert 内容を developブランチに戻す

$ git checkout develop
$ git log
commit 68ce661756642e444a68d04a32d4cc760bb03510 (HEAD -> develop, origin/develop)
Merge: d666db9 9609193
Author: tic40
Date:   Mon Apr 8 22:30:46 2019 +0900

    Merge pull request #18 from tic40/master

    Merge pull request #17 from tic40/develop

commit 960919320a75a2399e5ea34ebee1305c846e255b (origin/master, origin/HEAD, master)
Merge: 9d2b6c5 5631086
Author: tic40
Date:   Mon Apr 8 22:29:03 2019 +0900

    Merge pull request #19 from tic40/revert-17-develop

    Revert "Release"

$ git revert 9609193 -m 1
[develop 7567e16] Revert "Merge pull request #19 from tic40/revert-17-develop"
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 newfile.txt
$ git push origin develop

これで revert で打ち消した差分を develop に復活、master に再度マージが可能になる

Error retrieving access token: TypeError: Cannot read property 'expiry_date' of undefined [clasp]

I encountered an error when I use clasp command as below.

$ yarn clasp create clasp-project --rootDir ./src

yarn run v1.7.0
Error retrieving access token: TypeError: Cannot read property 'expiry_date' of undefined
error Command failed with exit code 1.
info Visit https://yarnpkg.com/en/docs/cli/run for documentation about this command.

I tried re-login and solved it.

$ yarn clasp logout
$ yarn login

github.com