チェック用シェルスクリプトを書いてみた

与えられたテストケース群についての、２つのプログラムの出力が同じかどうかをチェックするシェルスクリプトを書きました。 パラメータの値が小さいところで愚直解と一致するかどうか調べたいときなどに有用です。 出力が違った場合、そのときの入力と、２つのプログラムの出力を見ることが出来ます。 MacやLinuxなど、Bashが動く環境で是非お試しください。

#!/bin/bash

PROGRAM1="$1"
PROGRAM2="$2"

text=""
while read i; do
    if [ "$i" = "" ]; then
        echo -e "$text"
        out1=$(echo -e "$text" | $PROGRAM1)
        echo "out1: $out1"
        out2=$(echo -e "$text" | $PROGRAM2)
        echo "out2: $out2"

        if [ "$out1" != "$out2" ]; then
            echo "different!"
            exit
        fi

        text=""
    fi
    text="${text}${i}\n"
done

echo "finish."

使い方

次のとおりです（シェルスクリプトの名前をcheck.shとしてます）。

./check.sh [プログラム1の実行ファイルパス] [プログラム2の実行ファイルパス] 

入力は標準入力から受け取ります。 以下、使用例です。

cat input.txt | ./check.sh ./program1 ./program2
python input.py | ./check.sh ./program1 ./program2

一行目はテキストファイルから入力する場合です。 入力ケースは複数含めることが出来ます。その場合、入力ケース同士を空行で区切ってください。 二行目の例はプログラムから入力する場合です。パイプを使ってプログラムの出力をチェックスクリプトに渡します。 この場合も、入力ケース同士は空行で区切ってください。

出力例

こんな感じで出ます。

...

3 2
0 0 0

out1: 6
out2: 6

3 2
1 0 0

out1: 7
out2: 7

3 2
2 0 0

out1: 4
out2: 5
different!

ABC117を反省する（主にD問題）

結論から言えば、自分の中ではかなり力が出せたコンテストだったと思う。 少し手間取ったところもあったがA~Cまではほぼ順調にACし、残り５０分強を残してD問題に進むことが出来た。 時間としてはかなりあったが、やはり今の自分の実力では最後のD問題を通すには至らず、３完に終わった。 反省すべき点もあるが、今まで苦戦することも多かったC問題も落ち着いて考察して一発ACすることができたし、タイムも自分の中ではかなり良い方だった。 D問題も、ACには時間的に遠く及ばなかったがキーとなる部分の考察は出来ていたので、自分としては満足な出来であった。

まあ感想はこの辺にして、本題となるD問題の反省に入ろうと思う。 コンテスト終了後、自分こといろはすは書きかけだったD問題のコードを仕上げ、提出した。 するとなんと一発ACで、今日はなんて調子の良い日なんだと小躍りした。 しかし、これでめでたしではなかった。

実は、そのとき自分が通した解法は嘘解法だったのである。 本来は桁DPで解かねばならないところを、自分は貪欲で解いていたのだ。 この「貪欲嘘解法」は、Twitter上でかなり話題に登ったので知っている人（または自分もやったという人）は多いであろう。 自分はこの騒ぎをPCの前で眺めながら、「へえ〜、Dは嘘解法があったのか」などと呑気なことを思っていた。 そして「本来は桁DPで解かねばならない」という文章を見てさえも、「へえ、これ（自分の解法）が桁DPかあ」とか思っていた。 本当にどこまで天然なんだいろはす。[ちなみに、それからしばらくして「あれ、よく考えたらこの（僕の）解法貪欲じゃね！？」と気づいた]

まあそんな訳で、Dについては今日一日がかりで正解法で通したわけだが、そこに至るまでの自分の思考の道筋を初めから記録していこうと思う。

問題文はこちら

コンテスト中〜コンテスト後の考察（貪欲嘘解法）

とりあえず、最初のサンプルで実際に数値を代入してf(1), f(2), f(3),...と計算してみた。 そこから法則性のようなものを掴もうとしたのだが、これ自体にはそれほど意味はなかった。 XORの計算に慣れたところで次に、数列の各項を２進数表記して縦に並べてみた。これがかなり効果的だった。

こうすると、f(X)を最大化する方法がひと目で分かるからである。 XORの性質から、なるべく多くの項を寄与させるためには、２進数表記したときのXの対応する桁において

0が多い→1

1が多い→0

とすればよいことが分かる。

問題は「X≦K」という制約だが、これは左の桁から順番に見ていって、XがKを超えない限りにおいて上の指針に従うという風にすればよいであろう（とそのときのいろはすは考えた）。 これが「貪欲」の部分であり、間違っている部分である。

このような考え方に従って提出したコードが以下のコードである。

https://atcoder.jp/contests/abc117/submissions/4168980

なお、各桁において立っているビットの個数を数えるのにlower_bound()を使うというちょっとテクニカルなことをしているが、これは当時の僕がテンパっていて「ループを回して数えたのでは間に合わない！」（※間に合います）などと思ったせいである。まあかっこいいからいいか。

あと、これを通す前にを1<<iとか書いてハマってた。 iが大きいときは1LL<<iとかしなければならないことを恥ずかしながら初めて知った。 まあ、今後は安全のため自分で実装したpow()関数を使うことにしよう。

さて、上のリンクだが、見れば分かるとおり実際これで全てのテストケースが通っている。 しかし、実際間違った答えを返す簡単な例を作ることができる。例えば、の場合である。 このケースに対し、上のコードが返す答えは4だが、実際の答えは5である。これは一個ずつ手で計算するか、愚直解を実装するかすればすぐに分かるだろう。

このことは、貪欲法が破綻していることを示している。 つまり、ある桁で上の指針に従ってビットを立てることが出来る状況だったとしても、そこを立てずに後に回すことによって、最終的には多くのスコアを稼ぐことができるような場合があるということだ。

正解法（桁DP）

そこで、桁DPである。けんちょんさんの記事を参考にしながら実装した。 考え方はだいたいそのまんまだった。大事なのは、smaller=1からsmaller=1への遷移で上の貪欲法で使った指針を使うことだ。

Submission #4172770 - AtCoder Beginner Contest 117

ただ、慣れてないせいかやたらハマるところが多かった。今後のためにも反省点として残しておこう。

・配列のインデックスオーバーランで結果が２倍に。これはもうアホとしか言いようがない

・初期条件の設定ミス。これは桁DP特有の難しさがある気がする。しっかり演習して慣れる必要がありそうだ

・遷移条件の見落とし。遷移が不可能なところに有限な項が入っていた。これは予め紙にしっかり遷移条件をメモしておくことが大事だと思った。特にわかりやすさが大事

まあこんな感じで一日潰しました。今日の反省終わり！

ABC 075: C – Bridge

今日の反省はこの問題。

https://atcoder.jp/contests/abc075/tasks/abc075_c

まあ色々反省点はあるのだが、一番大きな反省点は時間だろう。 解くのに１時間１７分もかかってしまった。ABC-C問題にこれは掛かりすぎだろう。

何故こんなに掛かってしまったかを見るために、いろはすの思考を辿ってみよう。

考察

まず、考察を初めて数分でいろはすは閃く。任意の辺について、それが

「橋でない⇔ループの一部でない」

という事実に。これはこの問題を解くための最も重要なキーと言えるポイントである。

しかし、ここからいろはすの思考は迷走を始める。

橋の本数を数えるにはどうすればよいだろう。 橋の定義より、グラフ全体から橋となる１辺を取り去ると、グラフは２つの連結成分に分かれる。 そのどちらかに含まれる橋をまた取り去ると、この連結成分がさらに２つの連結成分に分かれる。 こう考えると、次の関係が成り立つことが分かる：

「橋の本数＝全ての橋を取り去ったときの連結成分の個数-1」

ここまではまあいい。結局役に立たない考察ではあったが、間違いではない。 しかし、ここからが酷い。

いろはす「先程の考察から、全ての橋を取り去ったときの連結成分の個数はグラフに含まれるループの個数に等しい」←！？ｗｗｗｗｗ

いろはす「つまり・・・・・・こうだっ！！！」

「橋の本数＝グラフに含まれるループの個数-1」（※違います）

そしてコードをガリガリ書いた。サンプル入力を試す。当然合わない。

いろはす「何故だ！？」

いろはすよ。コード書く前にサンプルで考察が合ってるかぐらい確認しようぜ。 親切に図まで書いてあるじゃないか。見たらひと目で違うと分かるだろう。

ここでようやく考察の間違いに気づいたいろはす。 この時点で30分は経っていたと思う。

ここからようやく思考は正しい方向に軌道修正される。 要は、最初の考察を起点に、真面目にループの一部でないような辺を数えるしかないのだ。 どうすれば数えられるかは、比較的すぐに思いついた。 何せ、先程のクソ間違った考察の際、ループを数えるのにDFSを用いていたからである。 これを応用することで、何とか任意の辺がループの一部か、そうでないかを判定するルーチンが書けた。 [このブログは「正解」を書くことが目的ではないので詳細は本家の解説に譲るが、要は出発ノードを保持した状態でDFSを行い、元のノードに戻ってきたらループに含まれる、という方法で判定できる]

まあそんな感じで気づいたらめっちゃ時間経ってました。

https://atcoder.jp/contests/abc075/submissions/4138916

というわけで、本日の教訓

「実装する前に考察が合ってるかサンプルで確認しよう」

今月の進捗

今月の進捗

ABC 049 D 連結 解説してみた

ABC 049 D 連結が解けたのが嬉しかったので解説してみた(ちなみに43分かかった)。

Union-Find木を使う問題である。 タイトルからして、「ああ、グラフの連結成分求める問題か。Union-Find使えば楽勝じゃん」とか思って取り掛かった。

・・・・・・甘かった。流石にD問題がそこまで単純な問題であるわけがなかった。 詳細はリンクを辿ってほしいのだが、この問題には２種類の「連結」がある。 「道路」による連結と「鉄道」による連結があり、これらは区別されなければならない。 しかし、最終的にこれらの両方で連結になっている相手を求めるという問題である。

連結かどうかの情報を保持するのにUnion-Find木を用いるのは分かる。 道路と鉄道、それぞれに対応する計２つのUnion-Find木を用意する。 ここで問題となるのは、いかにして「両方で連結」になっているかどうかの情報を効率よく抽出するかである。 勿論、最もナイーブなやり方は全てのノードの組み合わせについてループを回して、一つ一つ調べる方法である。 しかし、これではNが大きいときにTLEしてしまう。

Union-Find木の基本的な機能の一つに、「ノードの根を求める」というのがある。 ノードuとvが同じ木に属すということは、これらの根が同じであることと同値である。 このことを用いて、何とか都市をグループ分けできないだろうか。

道路による連結を表すUnion-Find木をuf1, 鉄道による連結を表すUnion-Find木をuf2とする。 都市uとvが道路と鉄道の両方で連結であることは、言い換えればこれらのuf1における根とuf2における根がそれぞれ等しいということである：

    uf1.root(u) == uf1.root(v) && uf2.root(u) == uf2.root(v)

そこで、第一の添字をuf1における根、第二の添字をuf2における根にした二次元配列を考え、配列の要素に都市の数を格納すればいい！！

...では駄目なのである。実際、上の指針に従ってn*nサイズのint型の二次元配列を定義するコードを投げると、サンプルは通るが途中のテストケースでREになってしまう。 理由は、メモリオーバーフローである。配列のサイズが大きすぎて領域が確保できないのだ。 ちなみに、これは配列をグローバル変数にしてヒープ領域に確保するようにしても同じである。ここには載せないが、コンパイル時に何かもう目が痛くなるような大量のエラーメッセージを見ることができる。

ではどうするか。ここは、配列ではなくmapを使うのがうまい方法だ。これなら、存在しないキーの組み合わせについて無駄なメモリを消費することがない。

    #include<cstdio>
    #include<bits/stdc++.h>
    typedef long long int ll;
    #define REP(i, n) for(int i = 0; i < (n); i++)
    #define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
    #define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
    #define BIT(b, i) (((b) >> (i)) & 1)
    #define LOG_F 1
    #define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)
     
    using namespace std;
     
    ll pow(int x, int n){
      return n == 0 ? 1 : x * pow(x, n - 1);
    }
    struct union_find{
      vector<int> par;
      vector<int> rank;
      union_find(int n){
        rank = vector<int>(n,0);
        for(int i=0; i<n; i++){
          par.push_back(i);
        }
      }
     
      int root(int x){
        if(par[x]==x){
          return x;
        } else {
          return par[x] = root(par[x]);
        }
      }
     
      void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
     
        if(rx==ry)
          return;
     
        if(rank[rx]<rank[ry]){
          par[rx] = ry;
        } else {
          par[ry] = rx;
          if(rank[rx]==rank[ry])
            rank[rx]++;
        }
      }
     
      bool equiv(int x, int y){
        return root(x)==root(y);
      }
    };
     
     
    /*
    n k l
    p1 q1
    ...
    pk qk
    r1 s1
    ...
    rl sl
     
    n 2*10^5
    k.l 10^5
    p q r s <= n
    p < q
    r < s
     */
    int n,k,l;
     
    int main(){
      cin>>n>>k>>l;
      union_find uf1(n);
      union_find uf2(n);
      REP(i,k){
        int p,q;
        cin>>p>>q;
        p--;
        q--;
        uf1.unite(p,q);
      }
      REP(j,l){
        int r,s;
        cin>>r>>s;
        r--;
        s--;
        uf2.unite(r,s);
      }
      map<int, map<int, int>> root;
     
      REP(i,n)
        root[uf1.root(i)][uf2.root(i)]++;
     
      REP(i,n)
        cout << root[uf1.root(i)][uf2.root(i)] << " ";
     
      cout << endl;
      return 0;
    }

LISについての備忘録

蟻本を読みながらけんちょんさんの記事に載っている問題を毎日解いているが、LISの項でこの問題が分からず、やむを得ず他の人の解答を見たときに学んだことが多かったのでメモ。

・upper_boundではなくlower_boundを使う

・答えの探し方(lower_bound使う)

・比較する量が２つ（二次元？）になったときのLIS

上２つは蟻本に載ってる知識を再確認しただけなので、メインは３つめです。

upper_boundではなくlower_boundを使う

LISの長さをO(NlogN)で求めるアルゴリズムでは、配列dpの更新時に次の条件を満たすインデックスi(もしくはイテレータ)を探す（a_jは現在ターゲットにしている数列の項）。

dp[i-1] < a_j ≦ dp[i]

これは、lower_bound()を使うと直ちに求めることができる。すなわち、

lower_bound(dp, dp+n, a_j)

で帰ってくるイテレータがそのまま上記の式を満たすiに対応するイテレータになる。

自分は今までupper_bound()を使って、帰ってきたの要素の一個前の要素よりa_jが大きいか判定して・・・と（間違いではないが）無駄なことをしていたので、自戒を込めてメモしておく。

また、更新の式は

*lower_bound(dp, dp+n, a_j) = a_j;

と書けば一行で書ける（蟻本に載っているのに見ないで自己流でやっていた）。

答えの探し方(lower_bound使う)

答え、すなわちLISの長さの出し方。 これも今まで、forループ回して線形探索していたが、lower_bound()で一発で書ける。

lower_bound(dp, dp+n, INF) - dp

ちゃんと蟻本のコード読もう（自戒）

比較する量が２つ（二次元？）になったときのLIS

ABC 038 D プレゼント

こういうの。任意のi<jについて、w_i<w_jかつh_i<h_jとなる最長の部分列を求める問題。 初めに思いついたのが、(w_i, h_i)の組を昇順にソートしておき、その(h_i)の列に関して上記の方法でLISの長さを求めるというもの。 しかしこれだと、w_iが等しい組が存在するケースに対応できなくて死ぬ(w同じでhが異なる組を両方列に含めてしまう可能性があるため)。 その後色々自分で試したが駄目で、諦めて解説を読んだところ、BITとかいう未習得のデータ構造が出てきて絶望。

ここまでが昨日起こった出来事。結局諦めて今日は次の問題を解くことにした。そこでも自力でACできず、解説もなかったので他の人のコードを見ることにしたのだが、そこでこの問題を初等的なLISの知識で解くためのヒントを得たので、ここに記しておく。

実は、上の方法はかなりいい線まで行っていた。(w_i, h_i)の組をソートして通常のLISをするという考え方は基本的に正しかったのだ。 ただ、ソートの仕方が通常の辞書順ソートでは駄目だ。第一成分は昇順に、そして（第一成分が等しい集合の中で）第二成分が降順になるようにソートしておくのがミソである。 こうすると、第二成分でLISの長さを求める際に、wが等しい集合の中では必ず一つのhしか列に含まれないのである（２つ以上含まれると、その時点で増加列ではなくなってしまうため）。 このようにして解いたのが以下のコードである。

https://abc038.contest.atcoder.jp/submissions/4025245

ついでに、その次の問題についても書いておく（他の人の解答を参考にしたやつ）。

TDPC K ターゲット

今度は円になったバージョンだが、これも同様な考え方で解くことができる。 各円C_iについて、半径r_iと位置x_iが与えられているが、ここで

a_i = x_i - r_i

b_i = x_i + r_i

とすれば、これは円の左端と右端の位置を表している。そこで、任意のi<jについてa_i<a_jかつb_i>b_jとなる最長の部分列を求めれば良い。

https://tdpc.contest.atcoder.jp/submissions/4025125

コード自体も参考にさせて頂いた人の丸パクリなのだが、何をしているかというと（そのまんまだが）、

①(a_i, b_i)の組を普通に辞書順ソート

②①の列の順番をreverse

③第二成分(b_i)のLISの長さを求める

である。何故今回は辞書順ソートでいいかというと、第一成分と第二成分の大小関係が元から逆だからである。

クラスカル法の正当性の証明

蟻本を読んでいたら、クラスカル法の正当性の証明が省略されていたので、自分で証明を構築してみた。 誰かの役に立つといいな。

ちなみにTeXで書く元気はなかった。汚くてごめんなさい。

---

クラスカル法の正当性の証明

連結な無向グラフG上のクラスカル法を考える。

X0=∅とし、これに閉路ができないように貪欲的にコスト最小の辺を付け加えていってできるGの部分グラフをX1, X2,..., Xnとする(これ以上辺を付け加えると 必ず閉路ができるグラフがXnである)。 以下、XnがGの最小全域木であることを示す。

まず、

S = {X | Xを部分グラフとするGの最小全域木が存在する}

とする。このとき、Xk∈S(k=0,...,n)を帰納法により示す。

まず、X0∈Sはよい。以下、Xk∈Sを仮定してX(k+1)∈Sを示す(k<nとする)。

帰納法の仮定よりXk∈Sであるから、Xkを部分グラフとするGの最小全域木Tが存在する。 Xkに含まれず、Xkに付け加えても閉路ができないコスト最小の辺をe=(u,v)とする。 e∈Tならば自明にX(k+1)∈Sであるから、e∉Tとする。

Tは木であるから、T'=T∪{e}とすると、T'には閉路ができる。 このとき、閉路に含まれる辺で、Xkに含まれず、eと異なる辺fが存在する。 [もし存在しないならば、閉路に含まれる辺はe以外全てXkに含まれるので、Xkにeを付け加えると閉路ができてしまい矛盾する。] fはXkに含まれず、またf∈TよりXkにfを付け加えても閉路はできないから、eの取り方より

cost(e) ≦ cost(f). ・・・(1)

TはGの全域木であったから、T''=T'-{f}=T∪{e}-{f}もGの全域木である。 さらに式(1)より、cost(T'')≦cost(T).故にT''はGの最小全域木である。すなわちX(k+1)∈S. 以上により、Xk∈S => X(k+1)∈Sが示された。

以上から、数学的帰納法によりXk∈S(k=0,...,n)が、特にXn∈Sが示された。

最後に、XnがGの最小全域木であることを示す。 まず、Xn∈Sであるから、Xnを部分グラフとするGの最小全域木Tが存在する。 このときcost(Xn)≦cost(T)であるから、もしXnがGの全域木であれば、同時に最小全域木でもあることが言える。 故に、XnがGの全域木であることを言えば良い。 すなわち、Xnは閉路のない連結なグラフで、Gの全ての頂点を含んでいることを言えば良い。

○閉路がなく連結であること

閉路がないことは、Xkの取り方からよい。連結であることを示す。 仮にXnが連結でなかったとすると、Xnは最低でも２つの連結成分に分けられる。 Gは連結であるから、それらを結ぶ辺eが存在する。このときXnにeを付け加えても閉路が出来ないが、これはXnの定義に反する。 故にXnは連結である。

○Gの全ての頂点を含んでいること

仮にXnに含まれないGの頂点vが存在したとする。 Gは連結であるから、vとXnを結ぶ辺eが存在する。このときXnにeを付け加えても閉路が出来ないが、これはXnの定義に反する。 故にXnはGの全ての頂点を含んでいる。

以上より、XnがGの全域木であり、したがって最小全域木であることが示された。（証明終）