レッドハンドの特定(微生物学実習)

  • 入力

1行目 n(人数)
次の2*n行 握手した2名の番号(1-index)が空白スペースで区切って与えられる
次の行([n/5]個の数) 1周目の検査で陽性なら1,陰性なら0
次の行(n個の数) 2週目の検査で陽性なら1,陰性なら0

  • 出力

i番目(1-index)が初期感染者である可能性が全く無いとき、すなわち感染可能性のない人間に感染している場合は、1周目でそれが判明すれば"NO_1st_round"、2周目で判明すれば"NO_2nd_round".
初期感染者である可能性があるが、下流の感染可能性のある人間すべてが発症しているわけではない場合、"possible".
初期感染者である可能性があり、かつ下流の感染可能性のある人間すべてが発症している場合、"YES"
(possible or YES の場合、感染可能性のある人間すべてを列挙する)

#include <bits/stdc++.h> 

using namespace std;

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

int a[2][50], b[2][50];

bool result[2][50];

bool infect[50];

signed main() {
    cin >> n;
    rep(i, 2) {
        rep(j, n) {
            cin >> a[i][j] >> b[i][j];
            a[i][j]--;b[i][j]--;
        }
    }
    for (int i = 4;i < n;i += 5) {
        cin >> result[0][i];
    }
    rep(i, n) {
        cin >> result[1][i];
    }

    rep(i, n) {
        cout << endl << i + 1 << "番目がレッドハンドか" << endl;
        int f = 1, g = 1;
        memset(infect, 0, sizeof(infect));//infect[]を0で初期化
        infect[i] = 1;

        rep(j, n) {
            infect[a[0][j]] |= infect[b[0][j]];
            infect[b[0][j]] |= infect[a[0][j]];
        }
        for (int j = 4;j < n;j += 5) {
            f &= (infect[j] >= result[0][j]);
            g &= (infect[j] == result[0][j]);
        }
        if (!f) {
            cout << "NO_1st_round" << endl;
            continue;
        }
        rep(j, n) {
            infect[a[1][j]] |= infect[b[1][j]];
            infect[b[1][j]] |= infect[a[1][j]];
        }
        rep(j, n) {
            f &= (infect[j] >= result[1][j]);
            g &= (infect[j] == result[1][j]);

        }
        if (!f) {
            cout << "NO_2nd_round" << endl;
        }
        else {
            if (!g)cout << "possible" << endl;
            else cout << "YES" << endl;
            rep(j, n)if (infect[j])cout << j + 1 << " ";
            cout << endl;
        }
    }
}

サンプル1

4
1 3
2 4
3 1
4 2
1 3
2 4
3 1
4 2
0 1 0 1
1番目がレッドハンドか
NO_2nd_round

2番目がレッドハンドか
YES
2 4 

3番目がレッドハンドか
NO_2nd_round

4番目がレッドハンドか
YES
2 4 

サンプル2

5
1 2
2 3
3 1 
4 5
5 4
1 5
2 3
3 5
4 5
5 5
1
1 0 1 1 1
1番目がレッドハンドか
NO_1st_round

2番目がレッドハンドか
NO_1st_round

3番目がレッドハンドか
NO_1st_round

4番目がレッドハンドか
YES
1 3 4 5 

5番目がレッドハンドか
YES
1 3 4 5 

サンプル3

5
1 2
2 3
3 1 
4 5
5 4
1 5
2 3
3 5
4 5
5 5
1
0 0 1 1 1
1番目がレッドハンドか
NO_1st_round

2番目がレッドハンドか
NO_1st_round

3番目がレッドハンドか
NO_1st_round

4番目がレッドハンドか
possible
1 3 4 5 

5番目がレッドハンドか
possible
1 3 4 5 

サンプル4

28
1 18
2 6
3 19
4 10
5 24
6 16
7 28
8 13
9 12
10 27
11 8
12 3
13 24
14 25
15 5
16 22
17 28
18 26
19 23
20 7
21 25
22 2
23 1
24 15
25 5
26 28
27 15
28 3
1 26
2 28
3 9
4 14
5 7
6 13
7 20
8 12
9 25
10 24
11 1
12 17
13 2
14 27
15 25
16 8
17 20
18 5
19 5
20 13
21 27
22 24
23 8
24 4
25 10
26 28
27 3
28 27
0 0 0 0 0

0 1 1 0 1
0 0 0 1 0
0 1 0 0 0
0 0 0 1 0
0 0 1 0 0
1 0 1
1番目がレッドハンドか
NO_2nd_round

2番目がレッドハンドか
NO_2nd_round

3番目がレッドハンドか
possible
1 2 3 5 8 9 10 11 12 13 15 16 17 19 20 23 25 26 27 28 

4番目がレッドハンドか
NO_2nd_round

5番目がレッドハンドか
NO_2nd_round

6番目がレッドハンドか
NO_2nd_round

7番目がレッドハンドか
NO_2nd_round

8番目がレッドハンドか
NO_2nd_round

9番目がレッドハンドか
NO_2nd_round

10番目がレッドハンドか
NO_2nd_round

11番目がレッドハンドか
NO_2nd_round

12番目がレッドハンドか
NO_2nd_round

13番目がレッドハンドか
NO_2nd_round

14番目がレッドハンドか
NO_2nd_round

15番目がレッドハンドか
NO_2nd_round

16番目がレッドハンドか
NO_2nd_round

17番目がレッドハンドか
NO_2nd_round

18番目がレッドハンドか
NO_2nd_round

19番目がレッドハンドか
possible
1 2 3 5 8 9 10 11 12 13 15 16 17 19 20 23 25 26 27 28 

20番目がレッドハンドか
NO_2nd_round

21番目がレッドハンドか
NO_2nd_round

22番目がレッドハンドか
NO_2nd_round

23番目がレッドハンドか
NO_2nd_round

24番目がレッドハンドか
NO_2nd_round

25番目がレッドハンドか
NO_2nd_round

26番目がレッドハンドか
NO_2nd_round

27番目がレッドハンドか
NO_2nd_round

28番目がレッドハンドか
NO_2nd_round

AtCoder Regular Contest 098

D - Xor Sum 2

  • 問題概要

長さnの数列がある。
A[l] xor A[l+1] xor ... xor A[r] = A[l] +A[l+1] + ... + A[r]となるl,r(1<=l<=r<=n)の組の数を求めよ。

  • 解法

l,rを自由に動かすとO(N^2)でTLE。
ここで 各bitで a xor b <= a + b であることに注目すると、lを固定したとき組(l,r)が条件をみたすならばr=l,l+1,...,rも条件を満たすことがわかる。
よって各lについて二分探索か尺取法でrの最大値を求めていけばいい。
xor も + も Monoidなので、区間xorと区間sumはセグメント木を使ってO(logN)で求められる。
二分探索で求めていくと計算量はO(N(logN)^2)で、厳し目だが一応通る(以下のコード)


冷静になってみると、区間xorは累積xorを、区間sumは累積和を用いることでO(1)で求められる。
xorの問題はbitごとに考えるという基本が何もできてなかったのと、segment木の理解が足りず手間取ってしまった。
本番では累積xorとBITを使った結果、前者がクエリに対して(l,r]、後者が[l,r)であることで混乱してバグを埋め込むことに。

#include <bits/stdc++.h> 

using namespace std;
typedef long long ll;

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

template< typename Monoid >
struct SegmentTree
{
    using F = function< Monoid(Monoid, Monoid) >;

    int sz;
    vector< Monoid > seg;

    const F f;
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1)
    {
        sz = 1;
        while (sz < n) sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x)
    {
        seg[k + sz] = x;
    }

    void build()
    {
        for (int k = sz - 1; k > 0; k--) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    void update(int k, const Monoid &x)
    {
        k += sz;
        seg[k] = x;
        while (k >>= 1) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    Monoid query(int a, int b)
    {
        Monoid L = M1, R = M1;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) L = f(L, seg[a++]);
            if (b & 1) R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const
    {
        return seg[k + sz];
    }
};

const int N = 200010;
int n;
ll ret;
SegmentTree< ll > seg1(N, [](ll a, ll b) { return a + b; }, 0);
SegmentTree< ll > seg2(N, [](ll a, ll b) { return a ^ b; }, 0);

int main() {
    cin >> n;
    rep(i, n) {
        ll x;cin >> x;
        seg1.set(i, x);
        seg2.set(i, x);
    }
    seg1.build();
    seg2.build();
    rep(i, n) {
        ll ok = i, ng = n;
        while (abs(ng - ok) > 1) {
            ll mi = (ng + ok) / 2;
            if (seg1.query(i, mi + 1) == seg2.query(i, mi + 1)) ok = mi;
            else ng = mi;
        }
        ret += ok - i + 1;
    }
    cout << ret << endl;
}

更新なし区間クエリを、構築O(NlogN),クエリO(1)でできる Disjoint Sparse Table というデータ構造があるので、それを使うのもいいかもしれない。disjoint...

Codeforces Round #480 div2-C Posterized

  • 問題概要

[0,255]を連続する数字ごとにいくつかのグループに分ける。各グループの大きさはk以下である。
各グループに対してそのグループに属する1つの数がkeyとして扱われる。
n個の数字v_i(0≦v_i≦255)が与えられ、返されるn個のkeyが辞書順最小になるようにグループを作るとする。
このときの各keyを求めよ。

  • 解法

まずkeyは各グループ内の最小値としていい。辞書順最小だから前から順に貪欲に考えていけばよく、あるv_iに対してkeyが最小になるのはグループのsizeをk以下に保ったままグループを左に拡大していくときである。
(例 v_i=5,k=3のときグループは{5}→{4,5}→{3,4,5})と拡大していく。)
この操作はグループ内の最小値iに対してuf.unite(i,i-1)を順次行っていけばいい。
sizeをk以下に保つことはuf.size(i)+uf.size(i-1)<=kが対応する。

struct uf_tree {
    std::vector<int> parent;
    int __size;
    uf_tree(int size_) : parent(size_, -1), __size(size_) {}
    void unite(int x, int y) {
        if ((x = find(x)) != (y = find(y))) {
            if (parent[y] < parent[x]) std::swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            __size--;
        }
    }
    bool is_same(int x, int y) { return find(x) == find(y); }
    int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
    int size(int x) { return -parent[find(x)]; }
    int size() { return __size; }
};

int a[256];
int n;
int main() {
    cin>>n>>k;
    vector<int> v(n);
    for(auto &x : v)cin>>x;
    uf_tree uf(256);
    for(auto &x : v) {
        int i = x;
        while (1) {
            if (i == 0)break;
            else if (uf.find(i) == uf.find(i - 1))i--;
            else if (uf.size(i) + uf.size(i - 1) <= k)uf.unite(i, i - 1);
            else break;
        }
    }
    MEMINF(a);//aを大きい値で初期化
    rep(i, 256)chmin(a[uf.find(i)], i);//各グループ内における最小値を記録
    for(auto &x : v)cout << a[uf.find(x)] << " ";
}

Codeforces Round #472 div2-A Tritonic Iridescence

  • 問題概要

長さnのsegmentがあり、C,Y,Mで彩色する。
既に色が決定しているsegmentはs[i]='C'などと入力され、未決定のsegmentはs[i]='?'となっている。
連続する2つのsegmentが同じ色にならないように彩色する方法が2通り以上あるかを調べよ。

  • 解法

場合分けでも出来るが、DPで解いてみる。
a[i][0]:= s[i]='C'のときの0~iまでの彩色の仕方の場合の数とすると、a[i][0] = a[i - 1][1] + a[i - 1][2] であり、
同様にs[i][1]はs[i]='M'のとき,s[i][2]はs[i]='Y'のときの0~iまでの彩色の数とすれば
0~iまでの彩色の仕方はs[i][0]+s[i][1]+s[i][2]通りとなる。
場合の数は高々3^n通りあって簡単にオーバーフローしてしまうが、s[i][j]が2以上のときは2とすることで回避している。

ll ret;
ll a[110][3];
int n;
string s;
int main() {
    cin >> n >> s;
    if (s[0] == 'C')a[0][0] += 1;
    if (s[0] == 'M')a[0][1] += 1;
    if (s[0] == 'Y')a[0][2] += 1;
    if (s[0] == '?') {
        a[0][0] += 1;
        a[0][1] += 1;
        a[0][2] += 1;
    }
    FOR(i, 1, n) {
        if (s[i] == 'C')a[i][0] += a[i - 1][1] + a[i - 1][2];
        if (s[i] == 'M')a[i][1] += a[i - 1][2] + a[i - 1][0];
        if (s[i] == 'Y')a[i][2] += a[i - 1][0] + a[i - 1][1];
        if (s[i] == '?') {
            a[i][0] += a[i - 1][1] + a[i - 1][2];
            a[i][1] += a[i - 1][2] + a[i - 1][0];
            a[i][2] += a[i - 1][0] + a[i - 1][1];
        }
        rep(j, 3)chmin(a[i][j], 2);
    }
    rep(j, 3)ret += a[n - 1][j];
    cout << (ret >= 2 ? "yes" : "no") << endl;
}

ドイツ語差し替え過去問-2017


Es besteht kein Zweifel: E-Mail hat unser Leben verändern.Als die Post noch ausschließlich auf dem Landweg verschickt wurde, bekam man frühestens nach zwei Tagen eine Antwort. Dank E-Mail ist heute die Antwort oft schon nach wenigen Minuten da.Ob sie vom Kollegen kommt, der nur ein paar Zimmer weiter sitzt, oder vom Freund aus der Schweiz - die Entfernung spielt keine Rolle mehr. E-Mail ist zu einer Form der schriftlichen Kommunikation geworden, die aus dem alltag, insbesondere dem Büroalltag, nicht mehr wegzudenken ist und die klassische Form des Briefschreibens in weiten Teilen abgelöst hat.



(a)Der Rhein ist nicht so lang wie die Donau.
(比較級を用いた文に)
(b)Dieser Satz wird von den meisten Lesern nicht richtig verstanden.
(能動文に)
(c)Die Lehrerin bittet die Schüler, die Fenster während des Unterrichts zuzulassen.
Die Lehrerin sagt zu den Schülern, " ".
(下線を引用符の中に入る文に)
(d)私は疲れているが、 試験の準備をしなくてはいけない。
für die Prüfung, ich, ich, müde, müssen, obwohl, sein, sich, vorbereiten
(e)この二つの概念を混同してはならない。
Begriff, beide, dieser, dürfen, man, miteinander, nicht, verwechseln

ドイツ語差し替え過去問-2016


Eine blinde Dame, der von Jahren beide Augen entfernt werden mussten, bestätigte auf meine Frage, dass sie noch in Bildern träume. Sie träume oft das, was sie erst vor kurzem erlebt habe. Was sie durch andere Sinne aufgenommen hat, wird im Traum in Bilder verwandelt. Was sie gehört oder getastet hat, wird verbildlicht, allerdings im Traum. Obwohl sie seit Jahren nichts mehr sehen kann, ist ihr die bildliche Welt also nicht vershlossen. Das bedeutet, dass einzelnen Systeme unseres Gehirns eng miteinander verbunden sind, denn sonst könnte aus dem Gehörten oder Getasteten nichts Gesehenes werden.


(a)Peter stand gestern um sechs Uhr auf.
(現在完了で)

(b)Franz sagte mir, er wolle sich meine Arbeit genau ansehen.
(直接話法で)

(c)Der Koffer ist für mich zu shuwer zu tragen.
(ichを主語に)

(d)明日の日の出は何時ですか。
aufgehen, die, morgen, Sonne, wann

(e)彼が家を出たあと、雨が降り出した。
beginnen, das Haus, er, es, haben, nachdem, regnen, verlassen, zu

ドイツ語差し替え過去問-2015


Selten war ich von einer Ausstellung so beeindruckt wie von der, die ich gestern im Staatlichen Museum gesehen habe. Es wurde alte chinesische Kunst gezeigt. Man bekam einen tiefen Einblick in die jahrtausendealte Geshichte der chinesischen Kultur. Als die Menschen in unserem Land noch mit primitiven Werkzeugen einfachste Arbeiten verrichteten, blühte in China bereits eine hohe Schriftkultur, und auch die Gegenstände des täglichen Gebrauchs zeigen nicht nur einen feinen Sinn fur Ästhetik, sondern auch die Anwendung hochentwickelter Techniken. Ich möchte gerne einmal nach China reisen, um die historischen Stätten an Ort und Stelle bewunden zu können.


(a)Sie hat keine Wort gesagt. Sie ist weggegangen.
(ohne...zuで一つの文に)

(b)Ich bin nicht reich.Ich kann nicht Amerika reisen.
(接続法Ⅱで一つの文に)

(c)Das Parlament wählte einen neuen Präsidenten.Danach wollte jeder ihm gratulieren.
(一番目のの文を過去完了の副文にして全体を一つの文に)

(d)この古代のコインは考古学者ではなく, 子供によって見つけられた。
antik,
(e)ドイツに長く暮らせば暮らすほど, ドイツ語がうまく話せるようになる。
desto, Deutsch, in Deutschland, gut, je, lang, je, leben, man, man, sprechen