ICPC Calculator

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1602&lang=ja

AC

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4007025#1

解法

• 入力をN行全部読み込んで後ろから処理
• サンプル

10
+
.+
..6
..2
.+
..1
..*
...7
...6
.3

• 文字列 ".3"はレベル1, 数字3なので(1, 3)としてスタックに積む
• 同様に、(3, 6), (3, 7)を積む
• 次に演算子, レベル2の＊が出てきたので、スタック上のレベル3のものを演算子で処理する。今回の場合、7＊6=42である
• 結果の42を、レベル2の42として積む (2, 42)
• 以下同様

Code

bool is_operator(string s){
  if(s.find('+')!=s.npos) return true;
  if(s.find('*')!=s.npos) return true;
  return false;
}

bool is_multiply(string s){
  if(s.find('*')!=s.npos) return true;
  return false;
}

// "...2" => 3
ll level(string s){
  ll L = s.size();
  ll cnt = 0;
  rep(i, L){
    if(s[i]=='.') cnt++;
  }
  return cnt;
}

// "...2" => 2
ll num(string s){
  ll i = 0;
  while(s[i]=='.'){
    i++;
  }
  string sub = s.substr(i);
  return stoll(sub);
}

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

    // input
    ll N; 
    while(cin>>N){
      if(N==0) return 0;
      if(N==1){
        ll v; cin >> v;
        p(v);
        continue;
      }

      VS S(N);
      rep(i, N){
        cin >> S[i];
      }
      reverse(ALL(S));

      stack<pair<ll,ll>> st;
      rep(i, N){
        string s = S[i];
        if(is_operator(s)){
          ll lv = level(s);
          if(is_multiply(s)){
            ll mul = 1;
            while(st.size()>0 && st.top().first == lv+1){
              mul *= st.top().second;
              st.pop();
            }
            st.push(make_pair(lv, mul));
          }
          else{
            ll sum = 0;
            while(st.size()>0 && st.top().first == lv+1){
              sum += st.top().second;
              st.pop();
            }
            st.push(make_pair(lv, sum));
          }
        }
        else{
          // 数字
          ll lv = level(s);
          ll n = num(s);
          st.push(make_pair(lv, n));
        }
      }
      // 全部終えたら
      ll ans = st.top().second;
      p(ans);
    }
    return 0;
}

目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦

E - 車の乗り継ぎ

Quiz

https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_e

AC

https://atcoder.jp/contests/gigacode-2019/submissions/8639311

サンプル6

解法

// i番目の車で j まで行く最短時間
double dp[2050][2050];

• と定義してDP
• 始点と終点にも車を定義して、車の位置の昇順でソートした、長さN+2の配列にて、

    // DP
    rep(i, 2050){
      rep(j, 2050){
        dp[i][j] = inf;
      }
    }
    // 0番目について
    FOR(i, 0, N+2){
      // iまで行けるか
      ll d = C[i].x;
      if(C[0].d >= d){
        // 行ける
        double t = (double)d / C[0].v;
        dp[0][i] = t;
      }
    }

    // i番目の車で行けるところまで行く
    FOR(i, 1, N+1){
      // i番目の車までに到達する最短時刻
      double until = inf;
      rep(j, N){
        chmin(until, dp[j][i]);
      }
      
      FOR(j, i, N+2){
        // i to jまで行ける？
        ll d = C[j].x - C[i].x;
        if(C[i].d >= d){
          // 行ける
          double t = (double)d/C[i].v;
          chmin(dp[i][j], t+until);
        }
        else{
          // 行けない
          break;
        }
      }
    }

    cout << setprecision(20);
    double ans = inf;
    rep(i, N+1){
      chmin(ans, dp[i][N+1]);
    }
    p(ans);

その他：公式解説はないのかな？

• https://atcoder.jp/contests/gigacode-2019
• GigaCode 2019、解説はないのかな？解説があると、後から見た人が精進に使えるので、資産になる

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

F - Sugoroku

Quiz

https://atcoder.jp/contests/abc146/tasks/abc146_f

AC

https://atcoder.jp/contests/abc146/submissions/8639063

解法

• 後ろから貪欲
• 補助配列Fを作った。iに飛びたい時、s[i]=='0'ならそのまま飛べるけれど、s[i]=='1'の時はその手前の'0'の位置を教えてくれるもの

木上の点に一律の値を足す & 各点の現在値を求める

Quiz

• npca2015年部誌_木に対する一般的なテク達.pdf p36
• Running Away from the Barn (USACO 2012 December Gold)

木上の点に一律の値を足す

• これをO(logN)でする方法が必要
• 下図のようなグラフを考える

• オイラーツアーとBITを使う
• vの先祖がuである場合のみ使える方法です (2021/08/07追記)
• u, v (depth[u] < depth[v])とする
• BITのleft[u]に+1, left[v]+1に-1する（ここでいうleftとはオイラーツアーの左端)
• uの値を求める時はBIT.sum(left[u]) - BIT.sum(right[u])
• 実際に求めてみると下図のようになり、求まっている

学んだこと

木上の点に一律の値を足す方法

【要検証】先祖関係でない場合

• LCAを求めて足し引きすればよさそう
• TODO：何らかの問題でverify

C - On Changing Tree ～オイラーツアーとセグ木～

Quiz

https://codeforces.com/contest/396/problem/C

N頂点の木 (3 x 10^5)
クエリQ (3 x 10^5)
・1 v x k : 頂点vにxを足す。vの子孫にも、vからの距離 i によりx - i kを足す
・2 v : 頂点vの値をmod 10^9+7でprint

• 足す値が一律ではないことをどう扱うか

AC

https://codeforces.com/contest/396/submission/65574597

解法

• まずは「npca2015年部誌_木に対する一般的なテク達.pdf」p34を読んでください。それでも分からなければ続きを読んでください

補足

• p34を読んでも私は最初理解できなかったのでそこを補足します
• たとえば上の画像のようなサンプルを考えます
• v以下に同じ値を加算するのは、オイラーツアー＋セグメントツリーで可能
• 今回の解法では、まずv以下の子孫にxではなくx+k * depth[v]を足す
• すると、v以下の子孫全てに足しすぎ状態になってしまう

* ノード2の場合、x   を足したいのにx+2kを足したので、2kの余分
* ノード3の場合、x- kを足したいのにx+2kを足したので、3kの余分
* ノード4の場合、x-2kを足したいのにx+2kを足したので、4kの余分

* ★2k, 3k, 4kこの係数 2, 3, 4は木の深さになっている！

• 木の深さは事前計算できる
• 余分な分はQuery2が来た時に借金返済してから答えることにする
• 借金情報は、専用のセグ木で管理する。p34でいうover
• ノード2,3,4,5,6に共通にkを足すことで借金登録ができる。実際の借金額はk * depth[node_id]で求まる
• 以上、補足できていれば幸いです

おまけ

• オイラーツアーで雑にセグ木に範囲加算していると葉っぱでバグる
• この部分

        // v以下にx+depth*kを加算
        ll val = x + depth[v]*k; val %= mod;
        sum.update(tour.L[v], tour.R[v]+1, val);
        // v以下に後で返済するKを記録
        over.update(tour.L[v], tour.R[v]+1, k);

• 最初は下記のようにしていた

        // v以下にx+depth*kを加算
        ll val = x + depth[v]*k; val %= mod;
        sum.update(tour.L[v], tour.R[v], val); // NG
        // v以下に後で返済するKを記録
        over.update(tour.L[v], tour.R[v], k); // NG

• この書き方だと、vが葉の時、tour.L[v] == tour.R[v]なのでセグ木がどこも更新しなくなってしまう

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