2019-02-20

Codeforces Round #540 C Palindromic Matrix 〜証明編①〜

Codeforces

前回示した解法（貪欲法）の証明をしたいと思う。

解法のポイントは、箱の方は小さい方から埋めていき、ブロックは大きい方から使っていくという点である。箱を小さい方から埋めるのは、大きい箱を埋めるのに小さいブロックを先に使ってしまって後で困らないようにするためであり、大きいブロックから使うのは、同じ大きさならば分割できないブロック一個より分かれているブロック複数個を残しておく方が後々有利だからである。

さて、示すべきことは、

「もし解が存在するならば、貪欲法で解の一つを構築できる」

であり、対偶を取れば

「貪欲法で解が構築できないならば、解は存在しない」

である。

ここで、「貪欲法で解が構築できない場合」というのはどういう場合だろうか？それは、前回の手順3.で条件を満たすjが見つからない場合である。

このとき、解が存在しないというのは何故言えるのだろう。それは、貪欲法で構築した状態が「最善」の状態だからである。最善の状態から最善を尽くして解を探したのに見つからなかったということは、解はない、というわけである。

従って、ちゃんとした証明のためにはこの「最善」の状態というのを定義すれば良さそうだ。そのためには、２つの状態に対して優劣をつける基準が必要だ。

状態A,Bがあるとしよう。これらは、残っているブロックの数が互いに同じだとする。このとき、状態Aが状態Bより優れているとは、次のような状態だと定義する。

状態A、Bにおいて、箱の埋まっていないスペースで連続しているものの大きさをそれぞれ $k_i, k'_i$ とする。また状態Aにおいて、残っているブロックjの個数を $m_j$ 、状態Bにおいて残っているブロックjの個数を $m'_j$ とする。さらに、「AがBより優れている」をA>Bと書くことにすると、

$\min_i k_i > \min_i k'_i$ ならばA>B. 逆も同じ
$\min_i k_i = \min_i k'_i$ のとき、 $(m_1, m_2, m_3) > (m'_1, m'_2, m'_3)$ ならばA>B.逆も同じ
$\min_i k_i = \min_i k'_i$ かつ $(m_1, m_2, m_3) = (m'_1, m'_2, m'_3)$ のとき $A \simeq B$ と定義する

すなわち、箱の空きスペースの最小値が大きい方が優れているとする。さらに、 $\min_i k_i$ が等しいときには $m_j$ ベクトルの（辞書順での）大小で優劣を決める。ただし、 $m_j$ ベクトルの辞書順での大小は次のように定義する：

$m_1 > m'_1$ ならば $(m_1, m_2, m_3) > (m'_1, m'_2, m'_3)$ . 逆も同じ
$m_1 = m'_1$ のとき、 $m_2 > m'_2$ ならば $(m_1, m_2, m_3) > (m'_1, m'_2, m'_3)$ . 逆も同じ
$m_1 = m'_1$ かつ $m_2 = m'_2$ のとき、 $m_3 > m'_3$ ならば $(m_1, m_2, m_3) > (m'_1, m'_2, m'_3)$ . 逆も同じ

$A>B$ または $A \simeq B$ のいずれかが成り立つとき、 $A \geq B$ と書く。

[なお、こうして定義された状態空間上の順序<は（残っているブロックの数を固定しても）全順序を成さない。しかし、関係 $A \simeq B$ による同値類を考えれば、その商空間では全順序を成す。]

そして、「Aが最善の状態である」とは、「任意の（残っているブロック数が同じ）状態Bに対して $A \geq B$ が成り立つ」ことと定義する。

以下で示すべきことは、

貪欲法で構築された状態は、常に最善の状態であること
最善の状態において $k_i \geq d_j$ となるブロックjが残っていなければ、解は存在しない

である。これらを次回以降で示していこう。

2019-02-20

Codeforces Round #540 C Palindromic Matrix 〜解法編〜

Codeforces

問題概要

n²個の数 $a_1, ... a_{n^2}$ が与えられる。それらの数をちょうど一度ずつ使って、上下左右に対称な正方行列を作れるか判定し、作れるならばそのような行列を出力せよ。

いろはすの解法

まず、行列が作れるとして、そのような行列では同じ数がいくつずつ必要なのかを考える。

nが偶数の場合、明らかに、行列に現れる全ての要素は４つずつセットになっている。すなわち、 $(n/2)^2$ 種類の数（重複があっても良い）がそれぞれ４個ずつ必要になる。

問題はnが奇数の場合で、こっちは少しだけややこしい。サイズが奇数ということは、行と列にそれぞれ「真ん中」が存在する。真ん中の行と真ん中の列が。よって、

真ん中の行にも真ん中の列にも属さない要素： $(\lfloor n/2 \rfloor)^2$ 種類×4個
真ん中の行、もしくは真ん中の列のいずれか一方のみに属する要素： $2\lfloor n/2 \rfloor$ 種類×2個
真ん中の行と真ん中の列の両方に属する要素： 1種類×1個

もちろん、これらを合計するとn²になることが確かめられる。

一々偶数奇数で分けるのも煩わしいので、まとめて「 $m_j$ 種類の数（重複があっても良い）が $d_j$ 個ずつ必要」と書く(j=1,2,3)。ただし、

$d_1=1, d_2=2, d_3=4$

である。

あとは、与えられた数の列を適切に分配してやればよい。数 $c_i$ が $k_i$ 個ずつ与えられている(i=1,...,r)とすると、問題は次のように変形できる：

「大きさ $d_j$ のブロックが $m_j$ 個ずつ(j=1,...,3)と、各々の大きさが $k_i$ の箱i=1,...,rがある。全てのブロックを隙間なく箱に収めることは出来るか、できるならその収め方を示せ」

もとの問題を見るとブロックと箱が逆のように見えるが、こちらの方が理にかなっている。数jは必ず $d_j$ 個ずつないと駄目で、 $d_j$ 個でワンセットだから「ブロック」なのである。また与えられた数 $c_i$ は必ずしも $k_i$ 個ずつでまとめる必要はなく、別々のところに分配することが可能であるから、むしろこちらが「箱」と考える方が筋が良い。

さて、この問題は、次のアルゴリズムで貪欲的に解くことができる。

$(c_i, k_i) (i=1,...,r)$ を優先度付きキューに入れる
大きさ $k_i$ が最も小さい箱 $(c_i, k_i)$ をキューから取り出す
$k_i \geq d_j$ かつ（箱に入らず）残っている最大のブロック $j=j^*$ を探す。無ければ終了
ブロック $j^*$ を箱iに入れる
$k_i > d_j$ ならば $(c_i, k_i-d_i)$ をキューに入れる
キューが空でないなら1.に戻る。空なら終了

これを実装したのが以下のコードになる。

Submission #50215161 - Codeforces

今回はここまで。次回は証明編。

2019-02-13

【今日の反省会】ABC 114: C – 755

今日の一句

桁DP　000に　気をつけろ

問題： C - 755

（解説）上記の問題を桁DPで解こうとしたら、探している数値の桁数が上限値のより少ないパターン（N=3600に対する735とか）を見落としていた。気をつけよう。

2019-02-08

【今日の反省会】Codeforces Global Round1（C問題解説付き）

反省会数学

今日も元気に反省しよう!!

ということで、今回の反省会は昨日のCodeforces Global Round1についてである。結果は2完で、A,B問題を最初の40分ぐらいで解いたのだが、その後C問題に残り全ての時間を費やしても全く解けなかった。なので、今回のテーマはそのC問題である。

Problem - C - Codeforces

この問題のキーポイントは、次の定理である。

A^B = A+B - 2(A&B)

ここに^はビットごとのXOR演算、&はビットごとのAND演算である（はてなブログのtex記法ではアンパサンドが使えないので普通に書いた。見苦しくてごめんなさい）。

まあ反省と言えば、いろはすがこの定理を知らなかったことであろうか。今覚えた。

あと考察力が足りなかった部分もあるが、これはもう演習で鍛えていくしかないであろう。

そんなわけで、今回は珍しく反省が短く終わってしまったので、残りは誰得のC問題の解説でもしようかと思う。 [まあ一番は自分のためだが、ひょっとしたら誰かの役に立つかもしれないので。]

C問題解説

まずは、先程の定理を証明しようと思う。

〜上の定理の証明〜

$A=\sum_{i=0}^\infty a_i 2^i$

$B=\sum_{i=0}^\infty b_i 2^i$

とする。ここで、

A&B = $\sum_{i=0}^\infty ((a_i + b_i)/2)2^i$

A^B = $\sum_{i=0}^\infty ((a_i + b_i)\%2)2^i$

[ただし、%は剰余、/は商の小数点以下を切り捨てたものを表す]であるから、

2(A&B) + A^B = $\sum_{i=0}^\infty (2(a_i + b_i)/2 + (a_i + b_i)\%2)2^i$

商と剰余の定義から、

2(A&B) + A^B = $\sum_{i=0}^\infty (a_i + b_i)2^i$ = A+B.

これより定理を得る。

〜証明終〜

さて、これを使って問題を解いていこう。まず、Aを2進数表記したときの桁数をnとおこう。ここで、(i)1桁目〜n桁目までのどこかに0がある場合、(ii)そうでない場合で場合分けする。

(i)1桁目〜n桁目までのどこかに0がある場合

Aをビット反転したものをBとすれば、場合分けの条件より0<B<Aであり、

A^B = 11...1

A&B = 00...0

であるから、

gcd(A^B, A&B) = 11...1.

(ii)そうでない場合

この場合は、Aをビット反転したものは0だから、条件0<B<Aを満たさないためこれは解にならないことに注意する。

このとき、任意のB<Aについて、

A&B = B

である。また、先程の定理を用いれば

A^B = A+B - 2B = A-B

と分かる。そこで、問題は

$gcd(A-B,B)$

の最大値を求めることになるが、

$gcd(A-B,B)=gcd(A,B)$

なので、結局 $gcd(A,B)$ を最大化する問題になる。 0<B<Aなので、最大値は明らかにAの二番目に大きな（つまり、Aの次に大きな）約数である。これは、単純な線形探索でAの二番目に小さな（つまり、1の次に小さな）約数を求めてそれでAを割ればよい。 Aの上界は10⁷程度のオーダーなので、1からAまで全て走査していたのでは間に合わないが、実際には $\sqrt{A}$ まで走査すればよいので間に合う（ $\sqrt{A}$ まで走査して見つからなければAは素数）。

以上、今回はこの辺でお開き！

2019-02-07

拡張ユークリッドの互除法を解説してみた

アルゴリズム数学蟻本

先日、こんな記事を書いた。

拡張ユークリッドの互除法を自己流で実装してみた。 - いろはすの競プロ反省会

これだけではあまりに不親切なので、ここに書いたコードの解説をしていこうと思う。

※上の記事に書いたコードは自己流で書いたものなので、蟻本に載っている拡張ユークリッドの互除法のコードとは異なります。予めご了承ください。また、ユークリッドの互除法については既知とします。

まず、拡張ユークリッドの互除法とは何かというと、0でない整数a,bに対して次の式を満たす整数x,yの組を求めるアルゴリズムである。

$xa+yb=gcd(a,b)$ ・・・(1)

ここで、 $gcd(a,b)$ はa,bの最大公約数である。これはベズーの等式として知られる式であり、整数解が必ず存在する。

アルゴリズムの説明に入ろう。まず、上の式において $a=a_0, b=b_0, x=x_0, y=y_0$ とおく。

$x_0a_0+y_0b_0=gcd(a_0,b_0)$ ・・・(2)

ここで、

$a_0=(a_0/b_0)b_0+a_0\%b_0$ ・・・（３）

（便宜上、剰余の記号として'%'を用いた）であるから、(3)を(2)に代入し、

$(x_0(a_0/b_0)+y_0)b_0+x_0(a_0\%b_0)=gcd(a_0,b_0)$ ・・・(4)

を得る。ここで、

$x_1=x_0(a_0/b_0)+y_0,$ ・・・(5)

$y_1=x_0,$ ・・・(6)

$a_1=b_0,$ ・・・(7)

$b_1=a_0\%b_0$ ・・・(8)

とすると、式(4)は

$x_1a_1+y_1b_1=gcd(a_0,b_0)$ ・・・(9)

となる。ここで、式(7),(8)の変換をよく見ると、これはユークリッドの互除法で用いる変換と全く同じ変換である。従って、

$gcd(a_0,b_0)=gcd(a_1,b_1)$ ・・・(10)

これを(9)に代入し、

$x_1a_1+y_1b_1=gcd(a_1,b_1)$ ・・・(11)

を得る。

式(11)と式(2)を見比べると、何と全く同じ形をしている！　以下、同様に

$x_{i+1}=x_i(a_i/b_i)+y_i,$ ・・・(12)

$y_{i+1}=x_i,$ ・・・(13)

$a_{i+1}=b_i,$ ・・・(14)

$b_{i+1}=a_i\%b_i$ ・・・(15)

とすれば、次々に変換を続けていくことができる。

式(14),(15)の変換がユークリッドの互除法の変換と同じであることに注意すると、この操作はあるi=nで終了し、

$b_n=0,$

$a_n=gcd(a_n, b_n)$

となる。このとき、i=nに対応する等式は

$x_na_n=gcd(a_n, b_n)=a_n$

であるから、その解は（例えば）、

$x_n=1,$ ・・・(16)

$y_n=0$ ・・・(17)

である。あとは、ここから(12),(13)の逆変換

$x_i=y_{i+1},$ ・・・(18)

$y_i=x_{i+1}-y_{i+1}(a_i/b_i)$ ・・・(19)

を用いてこれまでの変換を逆に辿れば、元の式(2)の解が求まる。この変換式(18),(19)こそがアルゴリズムの肝であり、それを実装したのが以下のコードである。

//xa+yb=gcd(a,b)の整数解を求める
typedef pair<int,int> P;
P extgcd(int a, int b){
  if(b==0)
    return P(1, 0);

  P p = extgcd(b, a%b);
  int x = p.first;
  int y = p.second;

  return P(y, x - y*(a/b)); //逆変換(18),(19)
}

2019-02-07

重複組み合わせ問題と勘違いして死んだ件（ABC 089: C – March）

反省会

今日の反省。

最近、問題の意味を勘違いして時間溶かすパターンが多い気がする。表題に上げたこの問題（ABC 089: C – March）がその最たる例である。

この問題文を読んで、いろはすはこう考えた。まず、重要なのは'M','A','R','C','H'それぞれの文字を頭文字とする文字列がいくつずつあるかである。これらを数えて配列に格納したら、あとはその中から３つの文字列を選び取る場合の数を数えればいい。

これは蟻本で見た気がするなあ・・・・・・そうだ、あれだ、重複組み合わせ問題だ。そう思って、蟻本に載ってる漸化式を使ってDPを書いた。

サンプルの入力で試してみると、何故か一つだけ出力が合わない。どこが間違っているかとソースコードを見直したり、ログを仕込んでみたりしたが一向に間違いは見つからず、そのまま１時間近く経過してしまった。

実は、この問題は重複組み合わせ問題ではなかったのである。気づいたきっかけは、ログに吐き出された中に明らかにおかしい値が混じっていたことだった。そもそもサンプルもそうだったが、手計算してもおかしいと分かる。しかしDPの漸化式は何度見直しても蟻本のそれと同じだったし、その式は自分で確かめたことがある式だから、誤植ということもありえない。

そこで初めて、「あれ、これって本当に重複組み合わせ問題か・・・・・・？」という疑念が湧いた。そしてよくよく今回の問題と、蟻本の例題を見比べてみて、疑念は確信に変わったのだった。

いろはすは、重複組み合わせ問題の意味を勘違いしていたのである。今解くべき問題は、

n種類のボールが、それぞれa_1,...,a_n個ずつある。このn種類の中からm種類を選んで、その各種類から一個ずつボールを取り出すときの取り出し方はいくつか。

であるのに対して、重複組み合わせ問題とは、

n種類のボールが、それぞれa_1,...,a_n個ずつある。同じ種類のボールを区別しないとき、これらの中からm個のボールを取り出す取り出し方はいくつか。

という問題である。こうしてきちんとステートメントを書き下してみると、両者は全く違う問題であることがわかる。

というわけで、今回の教訓は

問題設定を正しく理解せよ。アルゴリズムを使うときも、その背景となる設定が本当に今の状況に適用できる設定なのか確かめよ

である。

〜おまけ〜

あと、配列の要素の型をint型にしていたらWAになってしまった。確かに要素の大きさとしては10⁵なのでintで十分なのだが、後にこの要素を３つ掛け算するところがあり、そのときにキャストをしていなかったせいでオーバーフローが起きたものと思われる。 [式の代入先の変数がlong long型だったので、勝手にキャストしてくれるから大丈夫だと思っていたのだが、そうでもなかったようである。式の途中でオーバーフローしてたら駄目ということだろうか。] 最終的に、配列の要素の型もlong long型にしたら通った。

Submission #4187839 - AtCoder Beginner Contest 089

こういう気づきにくいミスにも気をつけなければと思った。

2019-02-07

拡張ユークリッドの互除法を自己流で実装してみた。

蟻本のやつがあまりに難しくて理解できなかったのと、何か使いにくそうだったので自分で実装してみた。こっちのほうが素直で分かりやすいと思う。

#include<cstdio>
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

//solution of xa+yb=gcd(a,b)
P extgcd(int a, int b){
  if(b==0)
    return P(1, 0);

  P p = extgcd(b, a%b);
  int x = p.first;
  int y = p.second;

  return P(y, x - y*(a/b));
}

int main(){
  int a=15, b=12;
  P p = extgcd(a,b);
  cout << p.first << " " << p.second << endl;

  return 0;
}