予鈴

競プロとか備忘録とか…

AOJ Sum of Integers Ⅱ

改めてみると解けるようになっていたのでメモ

問題文

Aizu Online Judge

解法

dpをやります。
dp[i][j][k] := 数字iを見ているときに、k個の数字を使っていて、和がjのときの場合の数
でも解けますが、
dp[i][j] := k個の数字を使ってていて、和がjの時の場合の数
としても解けます。dpの更新を後ろから行うと、異なる数字だけを使う数え上げができます。
参考になるかもしれない記事。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
signed main(){
    int n,s;
    auto dp = vectors(11,1001,0LL);

    dp[0][0] = 1;
    for(int num = 0; num <= 100;num++){
        for(int k = 9; k>= 0;--k){
            for(int crt = 0; crt <= 1000;crt++){
                if(dp[k][crt] != 0 and crt + num <= 1000){
                    dp[k+1][crt + num] += dp[k][crt];
                }
            }
        }
    }
    while(cin >> n >> s,n+s){
        cout << dp[n][s] << endl;
    }
}

Macのシステム容量が極端に増えるのをどうにかしたい。

題名通りですが、解決できたので自分用にメモ。 実行は自己責任でお願いします。
結論からいうとビルドファイルのキャッシュやiOSシミュレーターのキャッシュを削除すると40GBほど容量が増えました。

不可視ファイルを目に見えるようにする。

Terminalに貼り付けます。

defaults write com.apple.finder AppleShowAllFiles true; killall Finder

逆の動作(不可視ファイルを見えなくする)場合は

defaults write com.apple.finder AppleShowAllFiles false; killall Finder
FInderでサイズを確認できるようにする。

ファインダーで⌘+Jを押し、[すべてのサイズを計算]にチェックを入れて少し待ちます。
これで具体的にどのディレクトリが容量を消費しているかわかります。
~/Library/Developper に原因があると下の解決策が有効です。

キャッシュを消す
sudo rm -rf ~/Library/Developer/Xcode/DerivedData

これ以外にも、こちらでより詳しく紹介されてます。
visualstudioをダウンロードして削除したことがある方は関連ファイルが残っていることがあります。
docs.microsoft.com


これだけでもかなり容量が増えます。IDEってこんなに重いのか。。。と感じました。

ACPC2018-参加記-

今年も参加しました。

Day 0

 移動中にHaskellをやっていました。関数型言語をやりたい&楽しそうだったのですが意外とむずかしい。。。継続していやっていきたい。

景色は相変わらずど田舎。 晩御飯はマルモ食堂で食べました。美味しかった。

Day1

ジャッジをやりました。大悪魔さんの自己紹介が面白かったです。ヅの食堂がおしゃれで美味しかったのが印象的でした。

Day2

imulanさんとnadareさんとチームを組みました。

AとCを解いてEとFの考察を行いました。

・C問題は足してmodを取れば嬉しいなぁとすぐ気づいたんですが、バグを仕込みそうだったのでimulanさんに確認してもらいながらAC

・F問題は似たような問題を見たことがあったので、nadareさんと相談しながらDijkstraやるだけでは?みたいな気持ちになる。

・imulanさんに↑の概要を伝えると、辺のコストに単調性がないと指摘を受ける。自分の考察力の無さと詰めの甘さを思い知りました。imulanさんが通してAC

・E問題はnadareさんと一緒に数学をやりました。自分一人でやってると詰められないところもnadareさんがしっかり詰めてくださってAC。途中は苦しかったんですが結果オーライ。

Day2 懇親会

・c7c7さんやprdさん、nadareさん、北大*1さん、UTの方と一緒のテーブルになりました。

・お酒を飲む方が多くてびっくりしました。初めてお会いしたとは思えなぐらい喋りました。

・競プロの懇親会だけあって、プログラミングのことが好きな方が多かったので、競プロ以外のプログラミングのことについても話しました。自分より強い方の話を伺う機会は多くないので貴重な体験でした。

 

Day3

tomaさんとshotさんでチームを組みました。

AとDと戦犯を担当しました。

・A問題を通すまで55分4WAをしました。引退案件です。

・DはDPがDijkstraかなぁと思った。DPはバグらせた思い出しかないので、shotさんに方針を確認してもらって拡張Dijkstraを書くがWA。

・d[0][0]の初期化を忘れていることに気づいてAC。

・shotさんが虐殺としていたBとEをACしてプロ。コーディング力見習いたいです。

・TomaさんはFをこれはA~Fの中で一番簡単といってAC。想定解ではない方法らしいです。

・最後の一時間にD,E,Fがポンポン通ったのが印象的でした。

最後に

三度目の参加となりましたが、とても楽しかったです。2年前と比べると成長しているようなしていないような。。。

チームを組んでくれた皆様、会津大学北海道大学の皆様、ありがとうございました。

後期もしっかり精進していきたいと思います。

*1:実はこのときまで同学年の北大競プロerを一人も知りませんでした。

Mujin Contest D - うほょじご

解く前に考えていたこと

・絶対これ考察するだけでしょwと思ってたら違った。
・規則性を見出すことが全くできなかった。シュミレーションの選択肢を除外した。

正解

・解答を見ると閉路を探し出すような解答になっていたが、わからなかったのでメモ化再起で解いた。
 N \leq 999なので、2次元配列で状態を持てる。
・無限ループに突入する部分の判定が勉強になった。

  if(dp[x][y] != -INF)return dp[x][y];
        if(x == 0 or y == 0) return dp[x][y] = 0;
        dp[x][y] = 1;
        
        int tx = x, ty = y;
        if(tx < ty) tx = rev(x);
        else ty = rev(y);
        if(tx < ty)ty -= tx;
        else tx -= ty;
        
        return dp[x][y] = dfs(tx,ty);

まず、x,yに対し、dp[x][y]に1を一時的に格納する。
x,yに対して操作を行った後、閉路に突入する(つまり、x,yに戻ってくる)と、格納されている1が帰る。
そうでない場合は0が帰る。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(),in.end()
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
using namespace std;
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
auto rev(int t){
    string s = to_string(t);
    reverse(all(s));
    return stoll(s);
}
signed main(){
    int n,m; cin >> n >> m;
    auto dp = vectors(1024,1024,-INF);
    function<int(int,int)>dfs = [&](int x, int y) -> int{
       
        if(dp[x][y] != -INF)return dp[x][y];
        if(x == 0 or y == 0) return dp[x][y] = 0;
        dp[x][y] = 1;
        
        int tx = x, ty = y;
        if(tx < ty) tx = rev(x);
        else ty = rev(y);
        if(tx < ty)ty -= tx;
        else tx -= ty;
        
        return dp[x][y] = dfs(tx,ty);
    };
    int ans = 0;
    rep(i,n+1)rep(j,m+1){
        if(i and j) ans += dfs(i,j);
    }
    cout << ans << endl;
}

ABC106 AtCoder Express 2

解く前に考えていたこと

区間を数える典型なので、解き方は雰囲気で知ってた(実装はしてません)。
実装の際に盛大にバグらせたので戒めとして書きました。

解法

BIT+ クエリ先読みのオフラインアルゴリズムというらしい

#include<bits/stdc++.h>
using ll  = long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define INF (sizeof(int) == 4 ? 1e9:1e18)
using namespace std;
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using pii = pair<int,int>;
using piii = pair<int,pii>;

int bit [1000] = {},n;
int sum(int i){
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add (int i,int x){
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}
signed main(){
    int m,q; cin >> n >> m >> q;
    vector<piii>v( m + q);
    rep(i,m+q) {
        int a,b; cin >> a >> b;
        piii temp;
        temp.first = a, temp.second.first = b;
        temp.second.second = i;
        v[i] = temp;
    }
    sort (all(v),[](auto const x,auto const y) {
        return (
                x.second.first < y.second.first  or
                (x.second.first == y.second.first and x.second.second < y.second.second)
                );
    });
    int ans[100000] = {};
    erep(e,v){
        int left = e.first;
        int right = e.second.first;
        bool isQuery = e.second.second >= m;
        int index = e.second.second - m;
        if (isQuery){
            ans[index] =  sum(right) - sum (left - 1);
        } else {
            add(left, 1);
        }
    }
    rep(i,q) cout << ans[i] << endl;
}

9/6 追記
一応segtreeの解答も載せておこうかな
https://beta.atcoder.jp/contests/abc106/submissions/3096327

ABC038 D - プレゼント

問題概要

D - プレゼント

解く前に考えていたこと

AOJのマトリョーシカと非常に似ている。
・ただし、この問題は制約がN \leq10^5O(N^2)解は部分点しか取れない。
・LISであることは間違えないので、比較関数を書き換えて蟻本にある N log N のLISを書くがWA
・途中でpair型dpを更新していた。

正解

まず前提として、プレゼントaがプレゼントbの中に梱包される条件とは、
 w_b>w_a \land h_b > h_a  が成立する必要がある。
したがって、wを昇順にソートして h に関してLISを考えればうまくいきそう。
ここで、pairでsortすると、同値のwに関して、hは昇順に並ぶこととなる。これが良くない。

i番目の要素でLISの配列を上書きする場合を考える。ただし、上書きされる要素はj番目( j < i)とする。
・このとき、w_i = w_jが成り立っていると、h_i < h_jとなっているため、上書きできない。(直感的に説明すると、j番目の要素の方がi番目の要素より条件が厳しい)

逆に言えば、w_i = w_jのときh_i > h_jとなっていれば、通常通り更新することができる。

#include<bits/stdc++.h>
using ll = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
#define INF (sizeof(int) == 4 ? 1e9:1e18)
using namespace std;
using pii = pair<int,int>;
auto f = [](pii a,pii b){
    return !((a.first == b.first and b.second> a.second) or a.first > b.first);
};
signed main(){
    int n; cin >> n;
    vector<pii>v(n);
    for(auto && e:v)cin >> e.first >> e.second;
    sort(all(v),f);
    vector<int>dp(n,INF),lis;
    for(auto && e:v)lis.emplace_back(e.second);
    rep(i,n){
        *lower_bound(all(dp),lis[i]) = lis[i];
    }
    cout << (int)(lower_bound(all(dp),INF)-dp.begin()) << endl;
}

VimでIndentlineが動かなかった話

VimでIndentlineが動かなったのでメモ。
調べてみると、githubのIssueで報告されていました。
github.com
以下日本語でもメモを残しておきます。
まずターミナルで

vim --version

を実行します。すると、以下のような画面が現れるはずです。

f:id:yebityon:20180707170230p:plain

ここで、-conceal となっているのが問題です*1vimを入れ直しましょう。(画像では+になっています。)

brew install  vim

を実行して新しいVimを入れ直します。後は.bashrcにaliasを貼ると完成です。
以下の記事を参考にしていただけるとわかりやすいと思います。
qiita.com
qiita.com

*1:おそらくOS Xにもとから入ってるVimをお使いの方はほとんど-になっているハズです。