perogram

C++の改行でendlは'\n'の20倍遅い

f:id:peroon:20191008220320p:plain

対象者

  • coutを使っている

確認コード

差分

  • coutの改行でendlを使ったのが1番目、'\n'を使ったのが2番目
  • 500000行ほど出力する必要がある時にendlを使っていると時間制限ギリギリ

対処

  • 普段から改行には'\n'を使う
  • 私の場合はこう(↓)
#define p(s) cout<<(s)<<'\n'

B - The Number of Products

Quiz

https://codeforces.com/contest/1215/problem/B

Submission

https://codeforces.com/contest/1215/submission/62082416

解法

  • dpのようにi番目まで考えた時の ansP (正の組み合わせ数) を考える
  • A[]の値は+1, -1に単純化しておく
  • 前から i まで見ていった時、全部かけた場合の符号が決まる
  • 今、iを見ているとして、そこの符号と、それまでに出てきた同じ符号の数を見れば、足す数が決まる
  • (Aからbalが決まり、balからsが決まり、sからansPが決まる)

画像イメージ

f:id:peroon:20191008065801p:plain f:id:peroon:20191008065659p:plain

B - Graph Partition ~二部グラフ判定&グラフの直径~

Quiz

https://atcoder.jp/contests/agc039/tasks/agc039_b

AC Code (二部グラフ判定&グラフの直径)

https://atcoder.jp/contests/agc039/submissions/7879736

解法

  • 解説放送の通り、二部グラフ判定し、二部グラフなら構成可能
  • 構成可能な場合、グラフの直径+1が答え
  • 必要なコードは
    • 二部グラフ判定
    • グラフの直径
  • 二部グラフ判定については、蟻本p94にある通りdfsする
  • グラフの直径については、ワーシャルフロイドして全点間距離を求め、その中の最大値が直径
const int N_MAX = 205;
ll N; 
ll d[N_MAX][N_MAX]; // 隣接行列 ワーシャルフロイド用
VV G; // 隣接グラフ dfs用

// 二部グラフかどうか
// 蟻本 p94
int color[N_MAX];
bool dfs(int v, int c){
  color[v] = c;
  for(ll to : G[v]){
    if(color[to]==c) return false;
    // 隣接している頂点がまだ塗られていないなら-cで塗る
    if(color[to]==0 && !dfs(to, -c)) return false;
  }
  // すべての頂点を正しく塗れたらtrue
  return true;
}
bool is_bipartite(){
  if(dfs(0, 1)==true){
    return true;
  }else{
    return false;
  }
}

おまけ解法(BFS)

f:id:peroon:20191006074002p:plain

  • コンテスト中はこちらで解いた https://atcoder.jp/contests/agc039/submissions/7868873
  • どこかの点からBFS
  • 訪れていない隣接点のセットが得られる。そのセット内で辺があれば打ち切り
  • 隣接点のセットから、次の隣接点セットを得る。繰り返し
  • それを全点を開始点として試し、最大のkを求める

A - Connection and Disconnection

Quiz

https://atcoder.jp/contests/agc039/tasks/agc039_a

AC Code

https://atcoder.jp/contests/agc039/submissions/7879593

ランレングス圧縮 (復元はできない)

// ランレングス
// 例 s = "aabccc" => [2, 1, 3]
VI run_length(string s){
  char prev = s[0];
  VI V;
  ll cnt = 1;
  FOR(i, 1, s.size()){
    char c = s[i];
    if(c!=prev){
      V.push_back(cnt);
      // reset
      cnt = 1;
      prev = c;
    }else{
      cnt++;
    }
  }
  V.push_back(cnt);
  return V;
}

通らない人のためのテストケース

aba
3

answer : 2

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

No.898 tri-βutree ~LCA~

Quiz

https://yukicoder.me/problems/no/898

Submission

https://yukicoder.me/submissions/387090

解法

  • editorialの通り
  • dijkstraLCAの過去コードをコピーペースト

f:id:peroon:20191005041359p:plain f:id:peroon:20191005041408p:plain

その他

  • 全点間距離が必要?ワーシャルフロイド?制約的に無理・・・
  • と思ったけれどLCAを使えばいいのね

D - Menagerie

Quiz

https://atcoder.jp/contests/abc055/tasks/arc069_b

AC Code

https://atcoder.jp/contests/abc055/submissions/7840056

解法

  • editorialの通り、添字0, 1の動物を決めてしまえば連鎖的に後ろが決まる
  • 最後に整合性チェックをするのだが、私は最初、動物[N-1]から見た左右のチェックしかしていなかった
  • それでは不足で、画像のように動物[0]の左右もチェックする必要がある

f:id:peroon:20191004060102p:plain

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

pのk乗はoverflowするか?

  • https://codeforces.com/contest/1228/problem/C
  • この問題を解いていて、入力nが1018までなので、long longギリギリまで入力されうる
  • pow(p, k)をナイーブに求めたらoverflowするし、modをとると正しく判定できない
  • ということで判定関数を作った
  • pk > 1018ならoverflowと判定する。そのままpowしたら溢れるのでlogpを取って判定

f:id:peroon:20191001215508p:plain

// 底をpとしたlogp(n)
double logp(ll p, ll n){
  return log(n) / log(p);
}

// p^k is overflow ?
bool is_overflow(ll p, ll k){
  double a = logp(p, 1e18);
  if(k > a){
    return true;
  }else{
    return false;
  }
}

AC Code

https://codeforces.com/contest/1228/submission/61606338

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?