G - バラバラ掛け算

f:id:peroon:20190728234420j:plain

Quiz

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

AC Code

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

解法

  • 例えば7なら2x2x3 = 12で最大なので「2に分解していけばいいんやろ?」と思っていたが間違い
  • 6は、2x2x2=8とするより、3x3=9にした方が大きい
  • Nを6で割った余りで場合分けすればいい

感想

  • 脳の中のスキマを埋めてくれた問題

ジグザグ数 zigzag

f:id:peroon:20190728211056j:plain

1 2 1 2 1 => 5
  • となるような関数を作った。再利用することがあるかも
  • ジグザグ数と名付けた
  • 冗長に書いてある

使用例 (to verify)

Code

// 1 2 1 2 1 => 5
ll zigzag(vector<ll>& A){
    // イコール除去
    vector<ll> B;
    B.push_back(A[0]);
    ll prev = A[0];
    FOR(i, 1, A.size()){
        if(A[i]!=prev){
            B.push_back(A[i]);
            prev = A[i];
        }
    }
    if(B.size()==1){
        return 1;
    }

    ll tilt;
    if(B[0]<B[1]){
        tilt = 1;
    }else{
        tilt = -1;
    }
    ll count = 1; // 始点
    ll current = B[1];
    FOR(i, 2, B.size()){
        if(current<B[i]){
            if(tilt==1){
                //
            }else if(tilt==-1){
                // 折れ
                count++;
                tilt = 1;
            }
        }
        // 今回下がる
        else if(current>B[i]){
            if(tilt==1){
                // 折れた
                count++;
                tilt = -1;
            }
            else if(tilt==-1){
                //
            }

        }
        current = B[i];
    }
    return count+1; // 終点を足す
}

D - Digits Parade ~右からDP, 左からDP~

Quiz

https://atcoder.jp/contests/abc135/tasks/abc135_d

内容

  • 解法というか、左からDP, 右からDPのどちらでも解けますというメモです

解法

解法2

f:id:peroon:20190728182823p:plain

  • 上記に書いてあるとおりに実装し、bitsetも使って高速化したところACした

学び

  • 大きな数字(文字列で表すレベル)のmodは左から1桁ずつ処理していくと楽

コードの背景色は黒でしょ!CSSを変更しました。

CSS generator

変更後

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

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

    // input
    ll N;
    cin >> N;

    vector<ll> A(N);
    FOR(i, 0, N){
        cin >> A.at(i);
    }

    vector<ll> L;
    L.push_back(A[0]);

    FOR(i, 1, N){
        ll a = A[i];
        if(L.back()<a){
            L.push_back(a);
        }else{
            auto it = lower_bound(ALL(L), a);
            *it = a;
        }
    }

    ll ans = L.size();
    p(ans);
    
    return 0;
}

CSS

.entry-content pre.code {
    background-color: #282a36;
    color: #ffffff;
    font-size: 14px;
    line-height: 1em;
}
.synComment { color: #6272a4; }
.synConstant { color: #f1fa8c; }
.synIdentifier { color: #bd93f9; }
.synPreProc { color: #a199c8; }
.synSpecial { color: #c000c0; }
.synStatement { color: #50fa7b; }
.synType { color: #ff79c6; }

スマホ対応

記事一覧対応

記事一覧をスマートに

  • デザインによってはダサい一覧表示になってしまう
  • 本文テキストも不要
  • テーマを「インストールしたテーマ」から「Minimalism」に設定。一覧表示をいい感じにしてくれる

なぜ色々対応した?

  • スマホでの体験向上
  • TOPページに行った時にいきなり最新記事の内容がすべて表示されるのはつらい
  • コンパクトに記事一覧を表示したほうがいいため

最長増加部分列 LIS(Longest Increase Subsequence)

LIS

  • 最長増加部分列のこと
  • 部分列において、狭義単調増加(a1 < a2 < a3 ... )
    • 広義VERもある(下記)

解説

verify✅

感想

  • 配列Lは単調増加
    • なので後端だけ見る or 二分探索で高速に更新箇所を決められる
  • ※配列LはLISではないことに注意

関連問題

関数化

ll LIS(VI& A){
  ll N = A.size();
  VI L;
  L.push_back(A[0]);
  FOR(i, 1, N){
    ll a = A[i];
    if(L.back()<a){
      L.push_back(a);
    }else{
      auto it = lower_bound(ALL(L), a);
      *it = a;
    }
  }
  return L.size();
}

LIS復元

// sortedな列から検索。0-indexed
// xの書き込み先を返す
ll index_of(VI& A, ll x){
  return distance(A.begin(), lower_bound(A.begin(), A.end(), x));
}
// 復元可能
// http://www.prefield.com/algorithm/dp/lis_fast.html
VI LIS(VI& a) {
  const int n = a.size();
  VI A(n, inf);
  VI id(n); // Aのどこに挿入したかの情報
  rep(i,n){
    id[i] = index_of(A, a[i]);
    A[ id[i] ] = a[i];
  }
  int m = *max_element(id.begin(), id.end());
  VI b(m+1);
  // 後ろから
  for (int i = n-1; i >= 0; --i)
    if (id[i] == m){
      b[m] = a[i];
      m--;
    }
  return b;
}
int main(){
    VI A = {5,3,7,4,1};
    auto a = LIS(A);
    debug(a);
    return 0;
}

出力

{3, 4}
  • 参考先のを自分用に書き換えたもの。補助配列idを使うことで正しく復元できている
  • TODO verify用問題

広義単調LIS

  • a1 <= a2 <= a3 ... とイコールを許す
ll LIS2(VI& A){
  ll N = A.size();
  VI V;
  V.push_back(A[0]);
  FOR(i, 1, N){
    ll a = A[i];
    if(V.back()<=a){
    //if(V.back()<a){
      V.push_back(a);
    }else{
      // auto it = lower_bound(ALL(V), a);
      auto it = upper_bound(ALL(V), a);
      *it = a;
    }
  }
  debug(V);
  return V.size();
}

関連問題