PCK2017本選参加記

パソコン甲子園本選に地域枠として行ってこれたので参加記的なのをホント適当に

一日目

朝起きたら東京駅に向かう
新幹線が8:45分発ぐらいなのに7:45ぐらいについて時間が有り余る

新幹線に久しぶりにのったけどすごいですね
とても快適だった

郡山についてそこから普通の電車でまた一時間ぐらいで会津若松にいく
ここらへんで師匠を拝見することができて徳を高めた気分になる
バスの場所に行くとすでにたくさんの人々がいた
競プロ界隈と関わりのない相方がいるので交流をとても控える（コミュ障なだけ）

会津大学に着く

開会式が堅苦しくてマジかってなる

本選開始

1問目2問目3問目とやるだけを処理するマンになる
4問目は相方が考察してくれたのでうぇい
5問目も相方が考察してくれたのでうぇい
6問目も相方が考察してくれたのでうぇい
7問目も相方が考察してくれたのになんか実行時間間に合わない気分になって実装せず死
8問目も相方が考察してくれたけどbeetさんの幾何ライブラリのEPSがアレだったらしく死
9問目以降は絶望なので終了

どう考えても7問目は解けたね（時間有り余ってるんだから実装するべきだった）
本戦系実力が出るのでとてつもなく苦手
よく見なくてもぼくほとんど何もしてないので悲しいね

交流会で開会式みたいなのが堅苦しすぎて誰か貧血で倒れて早く終わらせてくれという気持ちになる
情報系高校生の貧弱さを考えてほしい

ここらへんで相方を放って適当に交流し始める
WA_TLEさんを初めてしっかり認識しました

夜
みんなとおしゃべりしたい気持ちがあったけど眠さとかに負けてねてしまった

2日目

起床AC
朝ごはんAC
荷造りAC
集合AC
忘れ物AC

会津大学から歩いてホテルまで取りに行く
おもったより遠くてつらくなった

途中で会津バス(5)北柳原(7)「ラーメンの広告みたいなものがここに入る」(100)の写真をとった
音の響きが和を感じさせる五七百で素晴らしいと思った

ついたら暇なのでVRゴーグルを作る
後にこれがいたるところでかさばり邪魔となる

豚汁とおにぎりをどうせちょっとだろと思いもらう
普通に多くておなかがたぷたぷになったたぷ

解説を聞きに行く
相方の考察大体合っててこれ完全に俺戦犯なのではみたいな気分になり始める
終わった後ヅ大生が集まってたので話そうと思ったがコミュ力の欠如により無理だった
おそらくここで話しとけば今日のARC-Dがとけたんでしょうか

記念撮影して閉会式になる

思ってたより開会の偉い人たちの言葉が短くてやるじゃんとなる
入賞者全員が前に出て表彰されるので長くて眠くてやばになる
なんかみんな1万円以上もらってるのではみたいな気分になり悲しくなる

終了する

beetさんと少しだけ話す
コドフェスパーカー黒だと思ってたのでそりゃ見つけられねえわとなる
なんか思い描いていたbeetさんとなんか違った

かえる

帰りにラーメンを相方と食べる

帰宅

強連結成分分解とARC030C-有向グラフ

強連結成分分解

パソコン甲子園予選お疲れ様でした
僕は7問目で詰まって時間を溶かした結果、解けたであろう9問目を解けず7問目すら解けず終了しました
会津オフ会楽しんできてください

ところで10問目が強連結成分分解でしたね
強連結成分分解ということはわかったのですがライブラリ持ってないからと諦めたのでやりました

基本的にはうしさんのを参考にしました
それに、強連結成分をまとめた後のグラフ、それぞれの強連結成分に含まれる頂点の番号を返せるようにしたものがこちらです

class SCC{
private:
    vector<vector<int> > gg, rg;
    vector<int> order, comp;
    vector<bool> used;
    vector<vector<int> > ng, vs;

    int n, nn;
public:
    SCC(){}
    SCC(int v) : gg(v), rg(v), comp(v, -1), used(v, 0), n(v){}

    void add_edge(int x, int y){
        gg[x].push_back(y);
        rg[y].push_back(x);
    }

    int operator[](int k){
        return comp[k];
    }

    void dfs(int v){
        used[v] = true;
        REP(i, gg[v].size()){
            if(!used[gg[v][i]]) dfs(gg[v][i]);
        }
        order.push_back(v);
    }

    void rdfs(int v, int k){
        used[v] = true;
        comp[v] = k;
        REP(i, rg[v].size()){
            if(!used[rg[v][i]]) rdfs(rg[v][i], k);
        }
    }

    int build(){
        REP(i, n){
            if(!used[i]) dfs(i);
        }
        fill(all(used), 0);
        int k = 0;
        for(int i = order.size()-1;i >= 0;i--){
            if(!used[order[i]]) rdfs(order[i], k++);
        }
        nn = k;

        //---------それぞれの強連結成分に含まれる頂点の番号----------
        vs.resize(k, vector<int>());

        REP(i, n)
            vs[comp[i]].push_back(i);
        //-----------------------------------------------------------

        //---------強連結成分をまとめた後のNew Graph!----------------
        ng.resize(k, vector<int>());
        REP(i, n){
            REP(j, gg[i].size()){
                if(comp[i] != comp[gg[i][j]])
                    ng[comp[i]].push_back(comp[gg[i][j]]);
            }
        }
        REP(i, nn){
            sort(all(ng[i]));
            ng[i].erase(unique(all(ng[i])), ng[i].end());
        }
        //------------------------------------------------------------
        return k;
    }
    
    int size(){
        return nn;
    }

    vector<vector<int> > graph(){
        return ng;
    }

    vector<int> vertices(int v){
        return vs[v];
    }
};

長いですね
おそらく変数名とか把握できてないので書き換えはもうできません
とりあえず某でverify的なのもしたところ(もとがうしさんのなのでもちろん通りましたが) 某氏に、ARC030Cを解けと薦められたので苦労の末ときました

ARC030C 有向グラフ

ARC-Eの何かしらを解けと言われた後、AtCoderProblemsでこれかな？って開いた後、難しそうだからいっか！みたいに閉じました
後からしっかりこの問題を名指しされたのではいってなって解くことにしました

明らかにSCCなのはわかり、することもわかり、実装も順調に進んでました
大体1時間ぐらいで最初の提出は出来ましたね
その後WAの原因がわからず死んでました
ときにはSCCの部分が間違ってるのではと思うこともありましたが気づきました

dfsの始点を最初に与えられた辺で入次数が0の頂点にしてたんですが、強連結成分が始点になるべきときに死んでました
強連結成分分解後に入次数0の頂点を始点として行えば成功しました(いえい)

解法

• SCC
• 入次数が0の頂点を始点にして以下のDFSをする
  • dp[i][j] := 頂点iまでの文字から作ったj文字での辞書順最小の文字列 を持つ
  • 各強連結成分ごとに含まれる文字をソートしたものを持つ
    • ここで各強連結成分に含まれる頂点の番号を返すやつが役に立ちます
  • あとはDAGを辿り一つ前の頂点の情報を元に貰うDPっぽいのをします
  • うまく結果を返す方法が思いつかなかったから適当にやってます
  • 始点の時はあからさまな例外処理をしてるね
• なんか通る

int n, m, k;
char c[310];
SCC scc;
vector<vector<int> > G;
string dp[310][310] = {};
string res;

void dfs(int v, int p){
    vector<int> vs = scc.vertices(v);
    string s = "";
    REP(i, vs.size())
        s = s+c[vs[i]];
    sort(all(s));

    if(p != -1){
        REP(i, 310){
            REP(j, min(i, (int)s.size())+1){
                dp[v][i] = min(dp[p][i], min(dp[v][i], dp[p][i-j]+s.substr(0, j)));
            }
        }
    }else{
        REP(i, s.size()+1)
            dp[v][i] = s.substr(0, i);
    }
    REP(i, G[v].size()){
        dfs(G[v][i], v);
    }
    res = min(res, dp[v][k]);
}

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

    cin >> n >> m >> k;
    REP(i, n)
        cin >> c[i];
    scc = SCC(n);
    REP(i, m){
        int a, b;
        cin >> a >> b;
        scc.add_edge(a-1, b-1);
    }
    scc.build();
    G = scc.graph();

    REP(i, 310)
        fill(dp[i], dp[i]+310, string(400, 'z'));
    res = string(400, 'z');
    vector<int> v(scc.size(), 0);

    REP(i, G.size()){
        REP(j, G[i].size()){
            v[G[i][j]]++;
        }
    }
    REP(i, v.size()){
        if(v[i] == 0){
            dfs(i, -1);
        }
    }

    if(res == string(400, 'z'))
        cout << -1 << endl;
    else
        cout << res << endl;
}

とても長かった
SCCつらいね

次は2SAT解いた後HL分解やります

JOI夏季セミナー2017参加記

情報オリンピック夏季セミナー参加してきました

それぞれの日ごとにうぇい(日にちは広義であり、朝4時とかは夜)

1日目

組合せゲーム理論入門か劣モジュラがいいな〜みたいなことを考えながら向かう
新宿で、座るために各駅乗るか〜！ｗとかやったら1時間半ぐらいかかった😢

北野につく
バスに乗る
猿野峠みたいなところで爆発音とともに降りる
タイヤがどうかなったのかな

めっちゃ参加者っぽい人が多かったので適当についていく
つく

スーツケースもって登山きつい
集合場所すでにわりといる
座ってSRMのDiv1Easy読む
不可能

自己紹介する
本を選ぶ
とりあえず全部適当に見る
劣モジュラと深層学習、数式数式しすぎでは？→諦め
関数型面白そう,Canvasは候補から外れている(すいません)
やっぱ組合せゲーム理論入門！
じゃんけん無しでゲット、機械学習形がとても人気だった

序章と0章読む、わかる

夕飯食べる

1章を読み章末問題をとこうとする
なんか地頭が必要そうな雰囲気を感じ始める

AGCがあるので少し早めに終わり、2完してシャワー浴びながらC考察戦略を使おうとする
2完割とかかってしまう
C問題、コーナーに微妙に気づかず終了

まあテトリスをする
60戦ぐらいして4時近くなる、深いなぁ

ねね

2日目

朝食AC
2章を読み進める、ここでじっくりしたのがちょっと悪かった

昼食食べる

講義だね
四時まで起きちゃったね
目が悪くて式が見えないね
そもそも難しいね
だけど真後ろに事務局の人がいるな…

寝よ！ｗ(最悪)

休憩が入るので起きて、頑張れば起きれそうな気分になる
とりあえず聞く
何もわからない

寝よ！ｗ

おはようございます

2章の章末問題をじっくり解く(これが本当にダメ)
流石に章末問題飛ばすべきだった感じがある
少し3章も読む

夕食食べる

3章読み進める
大体読める
章末問題を性懲りもなくやる

CSA出る、E解けたので4完出来て青脱却できる、ダイナミックスコアリング？許さん
まあその後はテトリスですね

pic.twitter.com/igwuuUcXfr

— 迷路 (@pazzle1230) 2017年8月27日

確か3時半ぐらいにねね

3日目

朝食AC、WAする人が出始める
よく考えたら読むの今日が最後じゃん！ｗ
4章早めに読む
ムズイが…

昼食

章末は流石にね
5章読む
マイニータイニーわからず〜！ｗ 進まなすぎて基礎を説明するだけの内容に決定する
手のかかる生徒でそーとりゅーさんに申し訳なくて申し訳ないです…
一番やりたかった感のある不偏ゲームまで届かず悲しかった
進捗班で一番悪かったが…

夕食
最初の夕食で感じてたんですが量多くないですか？
情報系の人が普通に全完出来る量じゃなくない？みたいなこと思いながら全完してたんですが

交流らしい
プロ集団と挙手選手権優勝者達がやり始める
あぶれたのでコヨーテやる
楽しいね

はい pic.twitter.com/YK0z2dkZ6q

— 迷路 (@pazzle1230) 2017年8月28日

テトリスかな〜
334フライングした

ねね

4日目

朝食ACやが
やっぱWAする人いるね

スライド作るが
スライド作成能力低くて時間が無限にかかるが
図を作るのが下手すぎる
双子のスライド作成能力と実装力高すぎでは

昼食

講義だね
眠いね
講義の内容が…
普通にわかるし面白いから起きるね
レールパズル異常に難しいが

スライド作成継続
3,4章と5章の超序盤やることになるが3章が終わるぐらい

夕食

スライド作る
余裕で終わるわけがなく終わらないが
徹夜決定

全体で2回絵しりとりしたが、りゅーさん😢ってなった(すいません)(ぼくはわかりましたよ)

うーん…テトリス！ｗ
CF出るかとなったがもやし先輩と相談した結果、D解けなかったら撤退することにする
解けない
撤退
スタバ

写真忘れたやが

頑張る
終わらない
レッドブルか〜！
スタバを「ｷｬｰ!ｺｺﾆｵﾕｱﾙｰ!ｷｬｰ」とスタバの様にしている女子大生二人を見かける
まあ明商井かなとなる

おわらない
ねねせず
終わる

5日目

どこで日付区切るか悩みました

朝食だが…
まあAC

帰宅の準備する

発表順、組合せゲーム理論入門最初やんけ
てことは2番目じゃん
はい
スライドが謎の遷移したり喋るの難しかったりする
TLE
後の人々に申し訳ない気持ちになる

劣モジュラ、わからず！ｗ
深層学習、わからず！ｗ
Canvas、すごーい！
関数型、微妙にわからず！ｗ最後に純粋関数型ほぼ関係ない人がいましたね…

終了
まあ貫徹だからね、帰ってすぐ寝るかな

新宿着く
カラオケマジ？となる
行く
各位歌うますぎでは？となり辛くなる

pic.twitter.com/PgmROwkuPL

— 迷路 (@pazzle1230) 2017年8月30日

帰り道がほんとに地獄
眠すぎて数m歩くのすら辛くなるし寝る
運悪ければ寝ながら車道に歩いて死んでたのでは？
家つく
即寝

まとめ

おそらく初日と最終日に徹夜を持ってくるテクが最適だと思う
あと、交流後はだいたい徹夜することになりそう
2日目の夜、まあ徹夜したほうが楽しめるからすべき
帰宅時死ぬけどね
自動スタバ販売機最高
実質読む時間少ない気がするしもう一日ぐらい欲しさ
発表時間も殆どの人TLEしてたしもうすこし欲しさ
来年も行きたいけど同学年の人受験とかで少なそうで悲しみ

平方分割とみんプロ本選C

平方分割

蟻本を読んでいて、遅延セグ木や平方分割のところで止まっていたのでやった
平方分割の部分は枠組みとなる部分がちゃんと書かれていなくて読み解けなかったので別のサイトを読んだ。
ただ他人のコードを読む力がないだけなんですけどね

みんなのプロコン本選C問題

本番はオープンコンテストにでてたんですが、Bの貪欲部分がO(N²)になっててダメだった
Cもみましたがデータ構造で殴るやつだと察してBやってた
終了後にCは平方分割だとか†clangのベクトル化†みたいなのを見たので平方分割の練習としてときました

これはどうでもいいんですが、テンプレートとして色々なデータ構造をclassとして実装しようと思ってるので平方分割もしました
一応処理はみんプロC用に変えてます
他の人のコードみたら平方分割はこんなことしてる人がほぼいなくて悲しくなった
速度もめっちゃ遅かったです
範囲更新なので伝播必要だと思ってevalありますが、使いませんでした
セグメント木をあきらめた人のための平方分割を完全に参考にしました
ありがとうございます！
おりさの先輩に教えてもらった方法は範囲加算時ははみ出した部分lazyの更新が面倒くさくないか…と思い使わなかったのですが（すいません） 今回の問題では更新しないのでそっちの方が確実に楽だったことに気づきました
解いてからようやく分かるプロの技でしたね、すいませんでした

class Bucket{
private:
    int n, bs, bn; // 要素数、バケットサイズ、バケットの数
    int m;
    vector<ll> data;
    vector<ll> lazy;
    vector<bool> lazyFlag;
    vector<vector<int> > bucket;
public:
    Bucket(vector<ll> v, int sz, int M){
        data = v; m = M;
        n = v.size();
        bs = sz;
        bn = (n + bs - 1) / bs;
        data.resize(bn*bs, INF_LL);
        lazy.assign(bn, 0);
        lazyFlag.assign(bn, 0);
        bucket = vector< vector<int> >(bn, vector<int>(m, 0));
        REP(i, bn){
            REP(j, bs){
                bucket[i][data[i*bs+j]%m]++;
            }
        }
    }

    void eval(int k){
        if(lazyFlag[k]){
            lazyFlag[k] = false;
            FOR(i, bs*k, bs*(k+1)){
                data[i] = lazy[k];
            }
            lazy[k] = 0;
        }
    }

    void update(int s, int t, int x){
        REP(k, bn){
            int l = k*bs, r = (k+1)*bs;
            if(r <= s || t <= l) continue;
            if(s <= l && r <= t){
                lazyFlag[k] = true;
                lazy[k] = (lazy[k]+x)%m;
            }else{
                FOR(i, max(s, l), min(t, r)){
                    bucket[k][data[i]%m]--;
                    data[i] += x;
                    bucket[k][data[i]%m]++;
                }
            }
        }
    }

    ll query(int s, int t, int d){
        ll res = 0;
        REP(k, bn){
            int l = k*bs, r = (k+1)*bs;
            if(r <= s || t <= l) continue;
            if(s <= l && r <= t){
                res += bucket[k][(m-(lazy[k]%m))%m];
            }else{
                FOR(i, max(s, l), min(t, r)){
                    if((data[i]+lazy[k])%m == 0)
                        res++;
                }
            }
        }
        return res;
    }

};

それぞれのバケットごとに、Mで割った余りがある数である要素がいくつあるかそれぞれ持っておきます。
バケット全体にたされたらlazyに、中途半端なら要素だけに加算
要素に加算した場合はそのバケットでの加算前%Mを1引いて加算後%Mを1足してます。
そしたらなんかやるだけ（終了）

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, Q;
    vector<ll> a;
    cin >> N >> M >> Q;
    REP(i, N){
        int A;
        cin >> A; a.push_back(A);
    }
    Bucket bc(a, sqrt(N), M);
    REP(i, Q){
        int l, r, d;
        cin >> l >> r >> d;
        bc.update(l-1, r, d);
        cout << bc.query(l-1, r, d) << endl;
    }
}

こんな感じです
精進の結果NieR:Automata1周目終わったので2周目も精進していきます。
投稿時にはEエンドまで終わりました。データは消さなかったのでエミール頑張ります

Codeforces #402 (Div.2)

Codeforces Round #402 (Div. 2)

Codeforces#402に出たので、なんとなく眠気もないしつける
最近レートが下がってばっかで悲しみ界のtouristになってたんですが、またさがったのでもうダメ
とりあえず前回のコドフォでYESとYesを間違えたり、JOI本選でllにし忘れたりとかそういうの多いのだめ

ちゃんと精進して地力付けていこうな👊

A問題

なんか2つの数列が与えられるからスワップして各数字が含まれる数を等しくしなさいみたいな
スワップ回数の最小値を求めなさい、等しく出来なければ-1を出力
等しく出来ないのは自明で全体である数字が奇数個しかなかったとき
等しくできるときは、その数字がある個数/2-数列Aにある個数の絶対値をそれぞれの数字でやる
そして半分にすればOK

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

    int N;
    int a[114], b[114], numA[5] = {}, numB[5] = {}, num[5] = {};
    int res = 0;
    cin >> N;
    REP(i, N){
        cin >> a[i];
        numA[a[i]-1]++;
        num[a[i]-1]++;
    }
    REP(i, N){
        cin >> b[i];
        numB[b[i]-1]++;
        num[b[i]-1]++;
    }
    REP(i, 5){
        if(num[i] % 2 != 0){
            cout << -1 << endl;
            return 0;
        }
    }
    REP(i, 5){
        res += abs(num[i]/2-numA[i]);
    }
    cout << res/2 << endl;
}

B問題

正の整数Nから好きなだけ桁を取り除いて10^kで割り切れるようにしなさい
下から貪欲
もしも0の個数が足りなければ0にするためにNの桁数-1が答えになる
絶対に0は存在するからね（答えが必ず存在するため）

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

    string num;
    int k;
    cin >> num >> k;
    int zero = 0;
    reverse(all(num));
    REP(i, num.size()){
        if(num[i] == '0')
            zero++;
        if(zero >= k){
            cout << i+1-zero << endl;
            return 0;
        }
    }
    if(zero < k){
        cout << num.size()-1 << endl;
    }
    return 0;
}

C問題

セールしてるよ、セール中にk個は少なくとも買ってね
セール後の方がやすくなってる商品もあるからそっちで買ってもいいよ
できるだけ総額を安くしてくれ

セール中とセール後の差でソートして貪欲
a[i]-b[i]をfirstにしたpairでやるとうまくいくはず
実装は汚い

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    int a[214514], b[214514], dif[214514];
    PII pd[214514];
    ll res = 0;
    cin >> n >> k;
    REP(i, n){
        cin >> a[i];
    }
    REP(i, n){
        cin >> b[i];
        dif[i] = a[i]-b[i];
        pd[i] = {dif[i], i};
    }
    int buy = 0;
    sort(pd, pd+n);
    while(pd[buy].first <= 0 && buy < n){
        res += a[pd[buy].second];
        buy++;
    }
    while(buy < k){
        res += a[pd[buy].second];
        buy++;
    }
    FOR(i, buy, n){
        res += b[pd[i].second];
        
    }
    cout << res << endl;
}

D問題

C問題を解くまでにかかったのが21分でそこから空白の1時間40分を過ごし死んだ
ここまで最高の流れでC問題解き終わった時点では2桁位だったのにな…

文字列TとPがあります。Tから与えられる順番で文字を消していくけど、いくつまでなら消してもPを部分列として含んでいるでしょう

ずっと部分列として含むか判定の高速化を考えてたけど実際はいくつとるかの試行を減らす方向だった
もっと頭を柔軟にできるようにしたい…
にぶたんだった
あたまをなーやわらかくなーできたらなー
部分列として含むかがO(|T|)でできるから全体でO(|T| log |T|)かな？
これからは最大化最小化を見たらすぐにぶたんに結びつけてやるぞ(死亡の音)

実装では消すのではなく逆順にして使える文字を増やしていった（なんか楽そうに見えたから）

string t, p;
vector<int> a;
bool canuse[214514] = {};

bool ok(int tm){
    memset(canuse, 0, sizeof canuse);
    REP(i, tm){
        canuse[a[i]] = true;
    }
    int in = 0;
    REP(i, p.size()){
        while(in < t.size() && (!canuse[in] || t[in] != p[i])) in++;
        if(in == t.size()){
            return false;
        }
        in++;
    }
    return true;
}

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

    cin >> t >> p;
    REP(i, t.size()){
        int A; cin >> A; A--;
        a.push_back(A);
    }
    reverse(all(a));
    int l = 0, r = t.size();
    while(r-l > 1){
        int m = (l+r)/2;
        if(ok(m)){
            r = m;
        }else{
            l = m;
        }
    }
    cout << t.size()-(l+r)/2-1 << endl;
}

もっと精進して解法レパートリー増やそうな

JOI2016/2017本選参加したよ

JOI2016/2017本選

JOIの予選をうまく通れてしまったので、ボーダーぎりぎりで怖いながらも本選に参加してきました。
なんか参加記的なやつです。

1日目

秋葉原で合流してお昼食べよ♥
みたいな感じの流れができあがってたのでプロの提案のもとロイホに向かった
なんかすでに4人ぐらいいたけど✝プロの風格✝みたいなものを出していたので怖かった
座席をUnionFindさせる一般的なテクを使えるプロ店員がいた

TXにのるよ

プロたちが精進してて怖い中テスト勉強してました
おそらくここがコーナーであり、差をつけられたんだと思います

のりました

なんか会場がガラス張りですごかった
プラクティスは全部JOI過去問に合った気がして全完できてうれしかった
もやし先輩がアレでアレだったのでアレだったけどACできててすごーい！

講演会的なものがありました、ちなみに僕は一番前の席に座ってたのですがほぼ寝てました
機械学習とかに興味があったはずなのにおかしいですね

立食パーティーは微妙なコミュ障を発揮することで話にあまり参加しないテクを使った
あっ、これは自己紹介でも言ったんですが最近Twitterをはじめました！
IDはぱずる1230で作ろうとしたのですがすでに存在したのでエルを大文字のアイにしました！
よろしくおねがいします！スペルとかまちがえないようにしてください！

宿舎は独房だった
部屋にはいると光もなくただ闇に包まれていた
スイッチを押し、明かりをつけるとだいたい（ここにはN畳みたいな言葉が入りますが常識がないためわかりません）ぐらいの広さで
ベッドはなんかアレで机はなんかもうアレだった
TsuzuさんとAzさんとあなたのコンビニに買い出しに行った
よっちゃんイカを買ったけど僕はタラタラしてんじゃねーよのつもりで買ったので酸っぱさに耐えてた

ABC全完レース的なのが始まり、こたまねぎさんと丼土さんが普通に全完していってプロみを感じた
僕はわからずひるどだったけどDPって聴いて本選死亡の雰囲気が出始める
この時裏ではけものフレンズが上映されてましたが、あまり集中できず、プロたちがふれんずー！って合唱していたのしか覚えてません

2日目

朝起きてエントランスに向かうと、数人が精進していた
僕はスマホしか持ってなかったのでDeemoでEntranceのフルコンを頑張ったけど無理だった、キレそう

朝ごはんですが、なんとか全問挑戦して全完できたのでよかった、鮭は水で殴った

適当に片付けをして下に降りると着物フレンズが上映されてた
一般にIQを溶かすと言われているけものフレンズだけど、真剣に見ていた人は基本的に本選通過しているっぽそうなので、おそらくIQを上げるアニメ

本選会場
なぜか緊張しない、この時は割りと緊張しないことがうれしかったけど、今思うと眠くて現状を把握できてないだけだった

本選開始
一問目を読む、どう考えてもDPじゃない
imosか？→いや違う→区間加算で殴るか？→どっちにしろ毎回O(N)かかりそう→適当にdiffとっとこｗ（ハム太郎だからね）
ここまで来るのに1時間かかった
この時点である程度絶望してたけどとりあえず実装する
この後も、一回diffが0になるように温度を変更した後に正しいdiffに直せば更新できることに気づくのに時間がかかる
実装する→WA
3分の1ぐらいはACしているように見えたので、絶望の夜明けって感じだった
ここでデバッグしまくるがどう考えても間違ってない
2時間経過ぐらいで愚直で部分点取ろうとする→WA

＞愚直で間違ってるはずがない＜

ここまで考えてもわからないってことは更新の式が間違ってるんだなと思って2問目を見る（もし間違ってたら3分の1ぐらいがACするわけがない）
どうせDPだろ！ｗって思いながら読む
それぞれの急行停車駅ごとに分けてDPすれば行けそう→なんか試行錯誤しまくってサンプルは通るようになるが残りは通らないバグが発生
諦める
この時点で絶望しまくってるので諦めて3問目を読む→解けない

お疲れ様でした！迷路先生の次回作にご期待下さい！！

0点でした、最高ですね、1問目のバグのコナンズヒントは32bit整数です。泣きたくなりました
自分の真の実力を示すことが出来たと思うのでよかった

この後に蒙古タンメンにizryt氏と行っておいしー！ってなって帰宅しました
来年もこの記事を使いまわせるような事態にならないようにしたいです
がんばります

AOJ520 最軽量のモビール

最軽量のモビール

本日2つ目のACなんですが、とくのに時間がかかった自分にキレそうなためブログにします。

コレなんですが、問題の概要としては

木が与えられます。
それぞれの節点には重さw、2つの整数a,bが含まれています。
2つの子の重さをそれぞれとしたときとなるようにします。

根の重さを求めましょう

まともにまとめられていませんが、まあ問題を自分で読めって感じです（は？）
最初は、を満たすにはwはa+bの倍数であるはずということがわかったため,wをa+bの倍数とする
そしたらともわかります。そしたら,の子の重さもわかります。...とすすめていき
どこかで整数では無くなったらそのwでは成り立たない。
もしすべてが整数で成り立った場合はそのwが最小ということになるのでうぇいってやったらTLEでした。
そもそもなぜか途中から答えが合わなくなってたので今度は方針を変えます

w1とw2を仮に定めていた場合、wも仮で定まるのでは無いか？となってもちろん定まります。
なので下から決めていけば根の重さも決められることがわかりますね
ほんとか？って今書きながら思ってますが通ってたのでそうなのでしょう
ここで、葉は重さ1とします。

これで更新していくことが出来ます。
なんで思いついたんでしょうね
今の僕は正当性がよくわからないです
他の人の解説見てきたいと思います

struct stick{
    int l_d, r_d;
    int par, l, r;
};

stick s[101];

ll gcd(ll x, ll y){
    if(y == 0) return x;
    return gcd(y, x%y);
}

ll dfs(ll st){
    if(st == 0) return 1;
    ll l_w = dfs(s[st].l);
    ll r_w = dfs(s[st].r);
    ll res = (l_w*r_w*s[st].l_d*s[st].r_d)/gcd(l_w*s[st].l_d, r_w*s[st].r_d);
    res = res/s[st].l_d + res/s[st].r_d;
    return res;
}

int main(void){
    int n;

    while(cin >> n && n){
        memset(s, 0, sizeof s);
        FOR(i, 1, n+1){
            s[i].par = i;
        }
        FOR(i, 1, n+1){
            int a;
            cin >> s[i].l_d >> s[i].r_d >> s[i].l >> s[i].r;
            a = gcd(s[i].l_d, s[i].r_d);
            s[i].l_d /= a; s[s[i].l].par = i;
            s[i].r_d /= a; s[s[i].r].par = i;
        }
        int start = 1;
        while(s[start].par != start){
            start = s[start].par;
        }
        cout << dfs(start) << endl;
    }
}