予鈴

競プロとか備忘録とか…

D - Number of Amidakuji

問題

atcoder.jp

考えていたこと

dpまではすぐにたどりつけたが、「正しいあみだくじ」の本数を求める方法がわからず。
(i,j)から(i,j+1),(i+1,j+1),(i-1,j+1)に推移できる。

解法

(i,j)番目にいるときの、あり得るあみだくじの場合の数を計算する。
・当たり前だけど、あみだくじの状態が決まれば推移先は一つに決まる。(条件が厳しくなっている。)
・なんちゃってdynamic_bitsetを作りました。

#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); }
int MOD = 1000000007;
class dynamic_bitset {
private:
    long long bit;
    string sbit                = "";
    unsigned long long bitsize = 0;
    
public:
    dynamic_bitset(int _bit) : bit{_bit} {
        for (int t = 1, mask = 2; bitsize == 0; t++, mask *= 2) {
            if (mask - 1 >= bit) bitsize = t;
        }
        for (int i = 0; i < bitsize; i++) {
            sbit = ((bit >> i & 1) == 1 ? "1" : "0") + sbit;
        }
    }
    dynamic_bitset(int _bit, int bitrange) : bit{_bit}, sbit{} {
        for (int t = 1, mask = 2; bitsize == 0; t++, mask *= 2) {
            if (mask - 1 >= bit) bitsize = t;
        }
        for (int i = 0; i < bitrange; i++) {
            sbit = (i < bitsize and ((bit >> i & 1) == 1) ? "1" : "0") + sbit;
        }
    }
    auto test(int _idx) {
        assert(_idx < sbit.size() && "index  out of range");
        return sbit[_idx] == '1';
    }
    void set(int _idx) {
        assert(_idx < sbit.size() && "findex out of range");
        sbit[_idx] = '1';
    }
    auto size() { return sbit.size(); }
    bool isAll() {
        return accumulate(sbit.begin(), sbit.end(), true,
                          [](bool r, char c) { return r && c == '1'; });
    }
    bool none() {
        return accumulate(sbit.begin(), sbit.end(), true,
                          [](bool r, char c) { return r && c == '0'; });
    }
    auto to_string() { return sbit; }
};
signed main(){
    int h,w,k;
    cin >> h >> w >> k;
    auto dp = vectors(300, 300,0LL);
    dp[1][1] = 1;
    for(int j = 1; j <= h; j++){
        for(int i = 1; i <= w; i++){
            for(int bit = 0; bit < (1 << (w - 1));bit++){
                auto db = dynamic_bitset(bit,w-1);
                bool isValid = true;
                rep(i,(int)db.size() - 1){
                    if(db.test(i) and db.test(i+1))
                        isValid = false;
                }
                if(!isValid)continue;
                if(i+1 <= w and db.test(i-1)){
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD;
                } else if(i-1 >= 1 and db.test(i-2)){
                    dp[i-1][j+1] = (dp[i-1][j+1] + dp[i][j]) % MOD;
                } else {
                    dp[i][j+1]   = (dp[i][j+1]   + dp[i][j]) % MOD;
                }
            }
        }
    }
    cout << dp[k][h+1] << endl;
}

D - Christmas

問題

非負整数 N,Xが与えられる。2つの文字P,Bに対して、N番目の文字列を
S_N := B + S_{N-1} + P +S_{N-1} + Bとする。
下からX文字に含まれる文字Pの数を求めよ。
beta.atcoder.jp

解法

・各nに対してPの数と含まれるすべての文字の数を定義に従って前計算する。
再帰関数で含まれる文字数を計算することができる。イメージとしては
 x > S_{n-1} + 2のとき、S_{n}のうち下半分のS_{n-1}と中間のPは完全に答えに含まれる。
・そうでない場合、↑の状態になるまで投げる。ただし、xが0のときはこれ以上関数を下げることができないので直ちに0を返す
・これすき、今度はコンテスト中にときたい。

#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;
signed main(){
    vector<int>dp(51,0LL),dp2(51,0LL);
    int n,x; cin >> n >> x;
    rep(i,51){
        if(i == 0){
            dp[0] = dp2[0] = 1LL;
        } else {
            dp[i] = dp[i-1] + dp[i-1] + 3;
            dp2[i] = dp2[i-1] + dp2[i-1] + 1;
        }
    }
    function<int(int,int)>cal = [&](int i,int x) -> int{
        if(x == 0LL) return 0LL; if(i ==0 )return dp2[0];
        return (dp[i-1] + 2 > x ? cal(i-1,x-1) :cal(i-1,x - dp[i-1] - 2) + dp2[i-1] + 1);
    };
    cout << cal(n,x) << endl;
}

B - Neutralize

問題概要

N個の数列が与えられる。K個の連続する数字を選んで0にできる。\sum_{k = 1}^N A_{k}の最大値を求めよ。
B - Neutralize

解法

動的計画法
A_iが最大値となる数列に含まれるか、あるいは0になるか二通り存在するので、
dp[0][i] :=i番目の数字を使った時までの最大値
dp[1][i]  :=i番目の数字を使わない場合の最大値
とする。
更新は
A_i番目の数字を使うとすると、直前まで0になった場合が存在するので
dp[0][i] = max(dp[0][i-1],dp[1][i-1]) + A_i
同様に、A_{i-1}使わなかった場合と、A_iの数字を含めてちょうどK個の数字を使った場合があるので
dp[1][i] = max(dp[1][i-1],dp[0][i-k])

最初状態が3通り(使う、0になる列に含まれる、使わない)だと思ってたんですが、使う場合と使われない場合だけで漸化式を書けてしまってアって感じでした。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#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); }
signed main(){
    int n; int k;
    cin >> n >> k;
    auto dp = vectors(2,n,-INF);
    vector<int>v(n);
    for(auto & e : v) cin >> e;
    dp[0][0] = v[0]; dp[1][k-1] = 0LL;
    rep(x,n){
        if(x){
            dp[0][x] = max(dp[0][x-1], dp[1][x-1]) + v[x] ;
            if(x-k>=0)dp[1][x] = max(dp[1][x-1],dp[0][x-k]);
        }
    }
    cout << max(dp[0][n-1],dp[1][n-1]) << endl;
}

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;
}