perogram

「別のクラスの人と3人組を作ってきてください」

動機

  • codeforcesでこの問題が解けなかった
  • https://codeforces.com/contest/1201/problem/B
  • 内容:数列Anからどれか2つを選んで-1することを繰り返し、数列を全ゼロにできるか
    • i != j
  • 解答は、max x 2 > sum のときNo, それ以外でYes
  • maxが飛び抜けちゃうとダメということ

f:id:peroon:20190805081441j:plain

一般化

  • これを一般化したのが下のmisteerの記事 & 熨斗袋さんの証明
  • 絵で描くとこういうことだろう

f:id:peroon:20190805082225j:plain

参考

https://misteer.hatenablog.com/entry/stone-cleaner

D - Gathering Children

f:id:peroon:20190805072240j:plain

Quiz

https://atcoder.jp/contests/abc136/tasks/abc136_d

AC Code

https://atcoder.jp/contests/abc136/submissions/6718753

解法

  • ダブリングやDPを使わない方法です
  • 大量に移動した後は、どこかのRLに落ちて振動します
  • 全てのRLの位置を調べておく
  • 各子供について、Rなら右側のRLに落ち、Lなら左側のRLに落ちる
  • lower_boundすれば、行き先のindexが求まるので、移動量の偶奇を見て、RLのどちらかが決まる

Code

    string s; cin >> s;
    ll L = s.size();
 
    set<ll> se;
    // RLなるi
    FOR(i, 0, L-1){
        if(s[i]=='R' && s[i+1]=='L'){
            se.insert(i);
        }
    }
 
    vector<ll> C(L, 0); // 位置ごとに子供をカウント
    FOR(i, 0, L){
        if(s[i]=='R'){
            auto it = se.lower_bound(i);
            ll index = *it; // 最終的に落ちるRLの位置
            ll diff = abs(index - i);
            if(diff%2==0){
                C[index]++;
            }else{
                C[index+1]++;
            }
        }
        else{
            auto it = se.lower_bound(i);
            it--; // 自分より左側のRL
            ll index = *it;
            ll diff = abs(index - i);
            if(diff%2==0){
                C[index]++;
            }else{
                C[index+1]++;
            }
        }
    }
    vprint(C);

トポロジカルソート

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B

AC Code

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

関数化した。Code

VI topological_sort(VV& G){
    ll N = G.size();
    
    // 入次数
    VI IN(N, 0);
    REP(i, N){
        for(ll to : G[i]){
            IN[to]++;
        }
    }

    stack<ll> st; // 入次数0のものを入れる
    REP(i, N){
        if(IN[i]==0) st.push(i);
    }

    VI ret;
    while(!st.empty()){
        ll i = st.top();
        st.pop();
        ret.push_back(i);
        for(ll to : G[i]){
            IN[to]--;
            if(IN[to]==0){
                st.push(to);
            }
        }
    }

    // 成功したか確認
    for(ll in : IN){
        if(in!=0){
            // 失敗(DAGじゃなかった)
            VI empty_vector;
            return empty_vector;
        }
    }
    // 正常の戻り値
    return ret;
}

別の問題

No.269 見栄っ張りの募金活動 ~分割数~

f:id:peroon:20190731072803j:plain

n個の互いに区別できない品物を、m個以下に分割する方法の総数をnのm分割と言い、m=nのとき特にnの分割数と言う。

Quiz

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

AC Code

https://yukicoder.me/submissions/364228

解法

  • 先にK円ずつ増えていく分を徴収する
  • 残ったお金を分割数で分ける

分割数クラス

  • 蟻本v2 p66を参考に自作した
// 分割数 n個のものをm個以下に分割する
// 蟻本v2 p66
struct PartitionFunction{
    vector<vector<ll>> dp; //dp[M][N]
    ll N = -1;
    ll M = -1;
    void init(ll n, ll m){
        N = n;
        M = m;
        // 大きめに確保
        dp.resize(M+5);
        REP(i, M+5){
            dp[i].resize(N+5, 0);
        }
        prepare();
    }
    void prepare(){
        dp[0][0] = 1;
        FOR(i, 1, M+1){
            FOR(j, 0, N+1){
                if(j-i>=0){
                    dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % mod;
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
    }
    ll f(ll n, ll m){
        return dp[m][n];
    }
};

A - Jumping!! ~負値をmodするべからず~

Quiz

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_a

AC Code

https://atcoder.jp/contests/tkppc4-2/submissions/6608047

感想

  • 1WAしてしまった
  • yが0以上の偶数であれば、飛ぶ回数は決まる
  • それがn回、たとえば5だとすると、xとして作れるのは-5, -3, -1, 1, 3, 5
  • nとxのparityを見れば判定できる

負値をmod

cppでは、
-3%2 =-1
となる
x = abs(x)

しておく必要があった。

Code

    ll x, y; cin >> x >> y;
    x = abs(x);
    if(y<0){
        p(-1);
        return 0;
    }

    if(y%2==1){
        p(-1);
        return 0;
    }

    pn(-3%2);

    ll n = y/2;
    if(-n<=x && x<=n){
        if(x%2==n%2){
            p(n);
        }else{
            p(-1);
        }
        return 0;
    }
    else{
        // 範囲外
        p(-1);
        return 0;
    }

学び

  • 負値をmodするべからず

I - school competition 1

Quiz

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i

AC Code

https://atcoder.jp/contests/tkppc4-1/submissions/6601047

解法

学び

  • 1点固定の全探索
  • 事前準備によるさらなる高速化 (D, U, Uの累積和)

Note

手で書くと分かってくる

f:id:peroon:20190729085451j:plain