ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

Codeforces 488 Div2 D Open Communication

Readforces
まず問題文が理解できなかった

問題概要

http://codeforces.com/contest/994/problem/D


A君とB君が数字のペアを持っている。A君とB君の数字のペアは共通する数字をちょうど1個含んでいる。
A君とB君はお互いの持っているペアを知らないので、互いに自分の持っているペアを含んだ数字のペアの集合を送信する。(つまりA君がペア(a,b)を持っていたら{(a,b),(c,d),(e,f)}のような集合を送信する)

A君とB君の送信したペアの集合から第三者C君が二人の保持しているペアに共通する数字を推測できるか?を答えよ。

推測できるならばその共通する数字を出力。
C君には推測できないが、A君とB君は共通する数字を推測できるならば0を出力。
それ以外の場合は-1を出力せよ。

多分こんな感じの問題(uwiさんに教えてもらった)



解法

まずA君の視点に立って「仮に自分がこのペアを持っている場合、相手とはどの数字を共有するか?」を考える。A君のペア(a,b)に対して共通する可能性のある数字が2つ(a,bの両方の場合)はA君がそのペア(a,b)の場合には共通数字がわからないので-1を出力して終了。もし共通数字の可能性がある数字が1つならば、その数字を"共通数字候補A"に入れる。
同様のことをB君に対しても行う。

"共通数字候補A"と"共通数字候補B"が共通する数字を1つしか持っていないならばC君はそれが共通数字であることがわかる。
もし"共通数字候補A,B"が共通する数字を2つ以上もっているならば、C君は推論ができないので0を出力すれば良い。

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

#define rep(i,n) for(int i=0;i<(int)n;i++)

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n,0),b(m,0);
    for(int i=0;i<n;i++){
        int x,y; cin >> x >> y;
        a[i] |= (1<<x);
        a[i] |= (1<<y);
    }
    for(int i=0;i<m;i++){
        int x,y; cin >> x >> y;
        b[i] |= (1<<x);
        b[i] |= (1<<y);
    }

    int ac=0,bc=0;
    rep(i,n){
        int cand = 0;
        rep(j,m) if(__builtin_popcount(a[i]&b[j]) == 1){
            cand |= a[i] & b[j];
        }
        int cnt = __builtin_popcount(cand);
        if(cnt == 0) continue;
        else if(cnt == 1){
            ac |= cand;
        }
        else if(cnt > 1){
            cout << -1 << endl;
            return 0;
        }
    }
    rep(i,m){
        int cand = 0;
        rep(j,n) if(__builtin_popcount(b[i]&a[j]) == 1){
            cand |= b[i] & a[j];
        }
        int cnt = __builtin_popcount(cand);
        if(cnt == 0) continue;
        else if(cnt == 1){
            bc |= cand;
        }
        else if(cnt > 1){
            cout << -1 << endl;
            return 0;
        }
    }

    if(__builtin_popcount(ac & bc) == 1){
        for(int i=0;i<20;i++){
            if((1<<i) & (ac & bc)){
                cout << i << endl;
                return 0;
            }
        }
    }else{
        cout << 0 << endl;
    }
}

感想

なんか難しく感じるけど、直感の優れてる人なら自明で一瞬な気がする。
C君がA君の立場、B君の立場に立って考えたり、A,B君がお互い他方の立場にたって考えたりすればもう少し正確に推測されるような気がしたが、そういう推論で消されるのは「片方から見たら共通数字があるが、もう片方からしたら共通数字がない」パターンだが、2つのペアに対して共通数字がある場合はお互いどちらからしても共通数字があるのでこのタイプのパターンは存在しないってことになかなか気がつけなかった

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

AOJ 1194 バンパイア

バンパイア | Aizu Online Judge

各整数x座標において、どの時間までなら建物があるかを調べればよい。
(このx座標が建物の境界の場合とかに注意。特に座標-r,rとかは危険)

あさがおと加瀬さん。 (ひらり、コミックス)

あさがおと加瀬さん。 (ひらり、コミックス)

void solve(double r,int n){
    vector<int> xl(n),xr(n),h(n);
    map<int,int> H;
    rep(i,n){
        cin >> xl[i] >> xr[i] >> h[i];
        for(int j=xl[i];j<xr[i];j++){
            H[j] = max(h[i],H[j]);
        }
    }

    double ans = 100;
    for(int x=-r;x<=r;x++){
        double y = min(H[x-1],H[x]);
        if(x == -r) y = H[x];
        if(x == r) y = H[x-1];
        double t = y + r - sqrt(r*r-x*x);
        ans = min(ans,t);
    }
    cout << Double(ans) << endl;
}


int main(){
    int r,n;
    int cnt = 0;
    while(1){
        cin >> r >> n;
        if(!r and !n) break;
        solve(r,n);
    }
}

ARC 092 D Two Sequences

これ500は冗談でしょ....僕が解けなかったから多分600か700あるよ

D - Two Sequences

[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識

[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識

問題概要

長さNの数列a,bが与えられる。
この数列aとbに対して全てのa_i+b_jのxorを計算せよ

解説

k-bit目(0-origin)を決める方法を考える。
k-bit目を決めるのにa[i],b[j]の0~k-bitさえ考えれば良いので、mod 2^(k+1)で考える。
a_i+b_jのk-bit目が1になっているものの個数を数える。
a_i+b_jでk-bit目が1になっているものは次の2パターンある01?...?,11?...? (k+1~0-bit目のみ記述)
前者の取りうる値は2^k \sim 2^(k+1)-1
(つまり、010...0 \sim 011...1)
後者の取りうる値は2^(k+1) + 2^k \sim 2^(k+1) + 2^k+ 2^k - 1
(つまり、110...0 \sim 111...1)
となる。
これを満たすようなa_i+b_jを探索すればよいが、aとbについてループを回すとO(N^2)となるのでTLEする。
そこでa_iを固定した上で、bをソートし上の条件を満たすようなbの要素の境界を二分探索で探し個数を数えればよい。

int N;
vector<int> a,b;

int main(){
    cin >> N;
    a.resize(N);
    b.resize(N);
    rep(i,N) cin >> a[i];
    rep(i,N) cin >> b[i];

    int ans = 0;
    rep(k,29){
        int T = (1 << k);
        vector<int> B(N);
        rep(i,N) B[i] = b[i] % (1<<(k+1));
        sort(all(B));
        int cnt = 0;
        rep(i,N){
            int A = a[i] % (1<<(k+1));
            int idx1 = lower_bound(B.begin(),B.end(),T-A) - B.begin();
            int idx2 = lower_bound(B.begin(),B.end(),2*T-A) - B.begin();
            int idx3 = lower_bound(B.begin(),B.end(),3*T-A) - B.begin();
            int idx4 = lower_bound(B.begin(),B.end(),4*T-A) - B.begin();
            cnt += idx2-idx1;
            cnt += idx4-idx3;
        }
        if(cnt%2){
            ans |= (1<<k);
        }
    }
    cout << ans << endl;
}

ARC 088 D Wide Flip

考えるとっかかりがつかめなくてすごぷろさんに教えてもらった問題
忘れないうちにメモ...

D - Wide Flip

問題概要

0と1からなる文字列sが与えられる
ある自然数Kに対して、sの長さK以上の連続部分列の01を反転できる(0を1に、1を0にできる)。
このとき、文字列sを全て0にできるような最小のKを求めよ

解説

Nを文字列sの長さとする。
まず、sが全て1なら全体を反転することで全て0にできるので、「文字列sを全て同じ文字にする」ことを目的としてよい。
長さKの部分文字列を反転させることができるとき、後ろから長さN-Kの部分文字列を全て同じ文字にできる。
これは例えば前からK-1文字が?、K文字目が0、K+1文字目が1、それ以降が?である文字列"?....?01?...?"について考える。後ろN-K文字を0にする場合、まず前K個を反転する("?'...?'11?...?"になる。ここで?'は?の反転)。そして前からK+1個を反転すると"?...?00?...?"になる。これを繰り返せば、後ろから長さK以上の部分文字列を反転できる場合、後ろからN-K文字を全て同じ文字にできる。同様にして前からN-K文字を同じ文字にすることができる。
これを考えると、前から前からN-K文字、後ろからN-K文字を取り除いた文字列が全て同じ文字ならば文字列sは全て同じ文字にできる。
このような最大のKを求めれば良い。

 
int main(){
    string s;
    cin >> s;
    int N = s.size();
    int l,r;
 
    int ans = (N+1)/2;
    if(N%2){
        int l = N/2;
        while(l>=0 and s[l] == s[N/2]){
            l--;
        }
        int r = N/2;
        while(r<N and s[r] == s[N/2]){
            r++;
        }
        ans += min(N/2-l,r-N/2)-1;
    }else{
        const int L = N/2-1;
        const int R = N/2;
        int l = L;
        int r = R;
        if(s[L] == s[R]){
            while(l>=0 and s[l] == s[L]){
                l--;
            }
            while(r<N and s[r] == s[R]){
                r++;
            }
            ans += min(L-l,r-R);
        }
    }
    cout << ans << endl;
}

実装方針が悪い。。。
中心から見るのではなく前と後ろから定数個除いた場合の合計を見たほうがいい....

百合展に行ってきました

百合展 http://yuriten.com/2018/

に行ってきました

 

感情を手に入れました。

購入した百合展カレンダーはラボの机に置いておきます

ARC070 D No Need

問題

D - No Need

[改訂第3版]C++ポケットリファレンス (POCKET REFERENCE)

[改訂第3版]C++ポケットリファレンス (POCKET REFERENCE)

解法

解説のO(NKlogN)解法。

まず、「カードが(不)必要」がどういう状況か?を考える。
「カードが不必要」とは、カードa_iを含む全てのよい集合が、どれもその総和がK+a_iとなる場合である。なぜならこの場合、a_iを引いてもKを超えるのでよい集合のままだからである。
逆に、「カードが必要」というのはa_iを含む良い集合にその総和がK+a_i未満のものが存在するということである。この場合、a_iを引けばその良い集合は良い集合でなくなる。

これをまとめると、a_iを含まない部分集合にその総和x K-a_i \leq x < Kのものがある場合、a_iは必要なカードになる。そうでない場合、不必要なカードになる。

DPの部分については典型的なDPなので省略(このDPはTypical DP contest A問題の簡易版)。

解説PDFの「カードiが不要な時、a_j \leq a_iを満たすカードjも不要である」という部分が個人的に引っかかった。
あまり直感的じゃない。

直感的に捉えるなら、「カードjが必要なときa_j \leq a_iとなるカードiも必要である」と考える。
こう考えると、カードjを含む良い集合のうちカードjを抜くと良い集合でなくなる集合においてカードjをカードiに置き換えることで、カードiが必要な気がする。
(例えば和がK+a_j-1となる良い集合にa_iが入っていればa_i (> a_j)を取り除くと良い集合でなくなるし、a_iがなければa_jのかわりにa_iを使えばa_iが必要であることがわかる)

証明すると次のようになる
命題 :  a_jが必要 \Rightarrow a_iが必要(ただし a_j < a_i)
(証明)
前提 :: a_jが必要であることから、ある集合  A = \{a_{k_1},a_{k_2},...,a_{k_m}\}(Aにa_jは含まれない)が存在しその和xはK-a_j \leq x < Kを満たす。

もし、a_i \not \in Aの場合、Aをそのまま用いれば K-a_i < K-a_j \leq x \leq Kよりa_iも必要であることが示せる。
逆に、a_i \in Aの場合、Aからa_iを取り除き、a_jを追加すればその集合A'の和x'
K-a_i \leq x' < K - a_i + a_j < Kとなるのでa_iが必要なカードであることがわかる。
(証明終了)

この証明は直感的であるが、解説PDFのように「不必要」ベースで考えた場合の証明も載せておく
命題: a_iが不必要 \Rightarrow a_jも不必要 (ただしa_j < a_i)
(証明)
前提 :: a_iが不必要であるので、任意のa_iを含まない集合Aとその和xがx < K-a_iK \leq xのどちらかを満たす。
この前提から「任意のa_jを含まない集合の和がK-a_j未満かK以上である」ことを示せば良い。

a_jを含まない任意の集合のうち、a_iも含まない集合は前提より自明。a_jを含まない任意の集合のうち、a_iを含むものについて考える。a_jを含まず、a_iを含む集合はa_i,a_jを含まない集合にa_iを追加したものである。
ここでa_i,a_jを含まない集合の制約について考える。
まず前提よりx < K-a_iK \leq xを満たす。
もし、xがK-a_i-a_jよりも大きい場合、その集合にa_jを追加した集合はK-a_i <= xになりうる。この集合はa_iを含まない集合なので前提をみたすはずだがK-a_i<=xとなりうることは前提と矛盾する。
従って、a_i,a_jを含まない集合はK-a_i-a_jより小さい。
よって、a_i,a_jを含まない集合はK-a_i-a_j未満かK以上となる。
これにa_iを追加した集合はK-a_j未満かK+a_i>=K以上となる。
故に、a_jを含まない集合はK-a_j未満かK以上となるのでa_jは不要であることがわかる。
(証明終了)

これが証明できればコードは自明

bool need(int index,int N,int K,const vector<ll>& a){
    vector<bool> e(K+1,false);
    e[0] = true;
    for(int i=0;i<N;i++){
        if(i==index) continue;
        for(int j=K;j>=0;j--){
            if(e[j] and j+a[i]<=K) e[j+a[i]]=true;
        }
    }
    for(int i=max<ll>(0,K-a[index]);i<K;i++) if(e[i]) return true;
    return false;
}

int main(){
    int N,K;
    cin >> N >> K;
    vector<ll> a(N);
    rep(i,N) cin >> a[i];
    sort(all(a));

    if(need(0,N,K,a)){
        cout << 0 << endl;
        return 0;
    }
    if(!need(N-1,N,K,a)){
        cout << N << endl;
        return 0;
    }

    int l,r;    // l : NG , r : OK
    l = -1;     // NG
    r = N-1;    // OK
    while(r-l>1){
        int mid=(l+r)/2;
        bool ret = need(mid,N,K,a);
        if(ret){
            r = mid;
        }else{
            l = mid;
        }
    }
    cout << l+1 << endl;
}

大学を卒業しました

2018年3月で東京工業大学を卒業しました

とくに意味もないけど振り返り

1年目

大学

  • 入学前の説明会で会話をした人に競技プログラミングという単語を聞く。すぐ忘れる。
  • 入学式。前日に王将食べたらお腹壊した。王将食べると高確率でお腹壊す。隣にkankou4870氏。
  • 東工大5類入学。Twitterはじめる。

授業

  • CSの授業でTeraPadに耐えられず、Vimと出会う(何故Vimかは多分Tokoroさんの影響)。

学科選択。

  • 情報工学科と電気電子工学科で迷う。どちらでも良かったので適当に決めた。

サークル

  • ロボット技術研究会入部。F3RCにむけてチームペンギンで缶を集めるロボットつくったり、†仲良しコントローラー†ができたり(学内予選敗退)。
  • 回路に興味をもってアンプを作成してみたりしたが、回路驚くほど分からなかった。(回路に触らなくなる)
  • 夏か秋くらいに人がAOJやってるの見て競技プログラミングに興味を持つ。

その他

  • 自動車免許の筆記試験に2回落ちる。

2年目

大学

授業

サークル

  • F3RCの運営した...(タイマーバグらせたりして嫌な記憶)。
  • 工大祭で3次元のboidsを展示

3年目

授業

  • 後期からJKE/Oの区別があんまりなくなる
  • 情報実験第三....得たものが無い。
  • 情報実験第四...信号処理が結構面白かった気がしたが資料が微妙。
  • 集積回路設計無理
  • 関数解析。個人的にはかなり好きな授業。
  • 代数系と符号理論。よくわからなかった。脳が追いつかない。
  • 統計的機械学習。興味はあったが脳が追いつかない。

サークル

  • ICPC国内予選チームnikku。97位。

4年生

大学

  • 研究室所属。
  • 成績で1人殴って8階に行く。
  • ざくろさんの「前の方に座ったほうがいい」というアドバイス、配属会までは意味不明だったけど配属会で確かにって気持ちになる。

授業 (院の授業)

  • プログラム理論、意味論の話とか。面白い。授業外でも勉強したいなって思えるくらい。
  • 並行システム論。これも面白い。
  • 機械学習、授業がゴミ。
  • 大規模計算論、論文読む授業だったけど知見がなさすぎて何もわからんって感じで単位捨てた。

院試

  • A日程
  • 大学の成績では勝ってるのにTOEICでひっくり返されたりしてかなり苦しい
  • ひっくり返した人と大学の成績とTOEICを比べるとTOEICの比重どんだけ大きいねんという気持ちになる
  • 幸運にもお隣の研究室に入れたのでよかった

研究室

  • ラボ乱闘した

卒論

  • 割りと苦しかった。

IQ1

卒業式

  • 入学式隣だったkankou4870氏がまた隣にいて笑った。

その他

  • 入学前の説明会で雑談をした相手がmonman氏と判明したのは4年生になってから。本人に言われてビックリした。

感想

卒業後は同大学の大学院に進学。
進学なので特に感慨深いものもないといったら嘘かもしれんが、思ったほどなにかあるわけでもない。
研究室は隣に移動。そろそろ来年の研究室に顔をだすか....