Bananas Multiplier (Easy/Hard)

Quiz

• https://www.hackerrank.com/contests/yfkpo3-2/challenges/bananas-multiplier-easy
• https://www.hackerrank.com/contests/yfkpo3-2/challenges/bananas-multiplier-hard

(hardも通る)解法

• (0-indexedとする)
• 頂点0からの最短距離（辺の本数）を各頂点について求める
  • bfsなり、ダイクストラなりで
• 各頂点にたどり着いた時のcの積をそれぞれ求める。これは直前の点の値が分かればO(1)で求まるので、全体ではO(N)で求まる
  • メモ化再帰なり、dpなりで
• 例えば下記画像で、頂点２～頂点５までの積を求めたいなら、「頂点０～５までの積」÷「頂点０～２までの積」で求まる
  • modの世界なので割り算は逆元で処理する

• 画像のように、頂点aから頂点bに行くときに、頂点0を挟むかどうかの場合がある
• LCAをlog(N)で求められるように前準備しておけば、除去する辺は求まる
• 実は、どちらの場合であっても統一的に処理できる。下記コード参照

// 関数fは、頂点0からその頂点に行くまでのcの積とする

// クエリ処理
ll Q;cin>>Q;
while(Q--){
  ll a,b,banana;cin>>a>>b>>banana;
  a--;b--;

  ll lca = LCA(a,b);
  ll ans = banana * f(a) % mod * f(b) % mod;
  ans *= mod_pow(f(lca), mod-2); ans %= mod;
  ans *= mod_pow(f(lca), mod-2); ans %= mod;
  p(ans);
}

計算量

• O(Q log(N) ) : クエリ数ｘLCAのコスト

要素

• 最短距離
• メモ化再帰 or DP
• 逆元
• LCA

JOIOJI

Quiz

https://atcoder.jp/contests/joisc2014/tasks/joisc2014_h

公式解説

https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d3-joioji-review.pdf

解説

• サンプルの文字列に公式解説を適用するとこうなる
• JO[i]==JO[j] かつ JI[i]==JI[j] の組の中で一番離れているものを見つければいい
• 解説には「ソートして～」と書いてあるがここを補足しておく
• 列ごとに構造体にする。例えば

struct Data{
  int jo;
  int ji;
  int index;
}

• この構造体＋比較関数を定義する
• 比較関数で jo, ji, index の順に大小比較すれば、上記画像で言う黄色の"0, 1"はindexの順に並び、ソートにO(N logN), 最長距離はO(N)で求められる
• 参考コード https://atcoder.jp/contests/joisc2014/submissions/8932147

学び

• 累積和の移項
• ソートを最適ペア探しに使う

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

追記：AC

• https://atcoder.jp/contests/joisc2014/submissions/10996939

A - JJOOII (JJOOII) ～文字列のランレングス（文字情報あり）～

Quiz

https://atcoder.jp/contests/joi2012ho/tasks/joi2012ho1

AC code

https://atcoder.jp/contests/joi2012ho/submissions/10256473

解法

• Oの連続数に注目する
• 例えばOOOがあったとき（連続したOが3個でその隣は違う文字）、レベル3しか作りえない
  • レベル4はもちろんだが、レベル2も作れない
• 文字ごとにランレングス圧縮し、Oに注目して左がJ, 右がIであり、かつJとIの長さがO以上あれば作れる

例題

OJJOOIIOJOI

ランレングス圧縮すると
O1 J2 O2 I2 O1 J1 O1 I1

Oに注目すると
J2 O2 I2の箇所でLV2が作れる
J1 O1 I1の箇所でLV1が作れる

それらのmaxを取って答えは2

code 抜粋

using P = pair<char, ll>;
// どの文字が長さいくつ
// のvectorで返す
vector<P> run_length(string& s){
  vector<P> ret;
  ll N = s.size();
  if(N==0) return ret;
  char cur=s[0];
  ll cnt=1;
  FOR(i, 1, N){
    if(s[i]==cur){
      cnt++;
    }else{
      ret.push_back(MP(cur, cnt));
      cur = s[i];
      cnt = 1;
    }
  }
  ret.push_back(MP(cur, cnt));  
  return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    string s;cin>>s;

    stringstream ss;
    ss << 'z';
    ss << s;
    ss << 'z';

    string t = ss.str();
    vector<P> V = run_length(t);

    ll ma = 0;
    ll N = V.size();
    FOR(i, 1, N-1){
      if(V[i].first=='O'){
        ll len = V[i].second;
        // 左右見る
        if(V[i-1].first=='J' && V[i-1].second >= len && V[i+1].first=='I' && V[i+1].second >= len){
          chmax(ma, len);
        }
      }
    }
    p(ma);
    return 0;
}

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

bfsのたたき台 (2次元グリッド)

• bfsってやるだけなんだけど、これまで汎用化していなかった
• たたき台としてここに書いておく

verified

• E - チーズ (Cheese)
  • ✅https://atcoder.jp/contests/joi2011yo/submissions/10254552
• D - Grid Repainting
  • ✅https://atcoder.jp/contests/abc088/submissions/11618621
• C - 幅優先探索
  • ✅https://atcoder.jp/contests/abc007/submissions/17739188
• G-グリッド金移動
  • 少し変更して金将の移動に
  • ✅https://atcoder.jp/contests/past202005-open/submissions/22450272

code

VS S; // map
const int H_MAX = 55; // 1050とかでも通る
ll d[H_MAX][H_MAX];
ll H,W; // ちゃんとセットすること！

int dx[4] = {-1, 0, 1,  0};
int dy[4] = { 0, 1, 0, -1};

bool in_range(ll i, ll j){
  if(0<=i && i<H && 0<=j && j<W){
    return true;
  }else{
    return false;
  }
}

// 問題設定に沿って書き換える
const char block = '#';
const char pass = '.';

// 引数は(Y, X), (Y, X)
// 0-indexed
// Yが先だからね！！
ll bfs(PII from, PII to){
  rep(i,H_MAX){
    rep(j,H_MAX){
      d[i][j]=-1; // 到達不能をinfにするか-1にするかは注意！
    }
  }
  queue<PII> que;
  d[from.first][from.second] = 0;
  que.push(from);
  while(!que.empty()){
    auto pa = que.front(); que.pop();
    rep(i, 4){
      ll ny = pa.first + dy[i];
      ll nx = pa.second + dx[i];
      if(in_range(ny,nx) && d[ny][nx]==-1 && S[ny][nx]!=block){
        // can go
        d[ny][nx] = d[pa.first][pa.second] + 1;
        que.push(MP(ny,nx));
      }
    }
  }
  return d[to.first][to.second];
}

aを見つけたらbに塗るbfs

• 湖を見つけたら番号を付けながら塗る必要があったので書いた
• 再利用の機会があるかも（書くの面倒なので・・・）
• AC D. Lakes in Berland https://codeforces.com/contest/723/submission/102175410

    // search : 探す記号
    // paint : 塗り後の値
    auto fill_edge = [&](PII start, ll search, ll paint){
      if(G[start.first][start.second]!=search)return;
      
      queue<PII> que;
      que.push(start);
      G[start.first][start.second]=paint;

      while(!que.empty()){
        auto pa = que.front(); que.pop();
        ll y = pa.first;
        ll x = pa.second;
        rep(i,4){
          ll ny = y + dy[i];
          ll nx = x + dx[i];
          if(!in_range(ny,nx))continue;
          if(G[ny][nx]==search){
            que.push({ny,nx});
            G[ny][nx]=paint;
          }
        }
      }
    };

D - カード並べ

Quiz

https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_d

AC code

https://atcoder.jp/contests/joi2010yo/submissions/10252516

解法

• next_permutationで全ての並び方を考慮し、先頭k個を採用する
• 3200msかかるが、10秒制限なので大丈夫

code抜粋

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;cin>>N>>K;
    VI A(N);
    rep(i,N)cin>>A[i];

    VI I;
    rep(i, N) I.push_back(i);

    set<string> se;
    do{
      // 前のk枚
      stringstream ss;
      rep(i, K){
        ll idx = I[i];
        ss << A[idx];
      }
      se.insert(ss.str());
    }while(next_permutation(ALL(I)));

    ll ans = se.size();
    p(ans);

    return 0;
}

BICYCLE(バイスクル) RACER BACK(レーサーバック) GOLD EDGES(ゴールドエッジ) トランプ 赤/青 2デック