# 競プロ講習会第10回 Web資料
## ヒント・解説補足
### 今回の解説について
基本的には、公式解説( https://icpc.iisf.or.jp/past-icpc/domestic2021/commentaries.html ) を参照してください。
ここでは、ヒント・公式解説では説明されていない箇所について、補助的に説明を付け加えたいと思います。
今回は、全体的にかなり高難易度のこともあり、E問題までの対応となります。
---
### ◎A.
:::spoiler **◎ヒント**
愚直が通りますが、頭のいい方法があります。
:::
:::spoiler **◎補助解説**
実は、4つの整数の最大公約数が答えとなります。
証明は公式解説に書いてあります。
正直この問題に関しては、公式解説で十分だと思うので、実装を以下に置いておきます。
:::
:::spoiler **◎pythonでの実装例**
```python=
# 最大公約数解
import sys
from sys import stdin
import math
while True:
a = list(map(int,stdin.readline().split()))
if sum(a) == 0:
break
g = a[0]
for i in a:
g = math.gcd(g,i)
print (g)
```
:::
:::spoiler **◎C++での実装例**
```cpp=
//最大公約数解
#include <bits/stdc++.h>
using namespace std;
int main(){
while (true){
int a1,a2,a3,a4;
cin >> a1 >> a2 >> a3 >> a4;
if (a1+a2+a3+a4 == 0) break;
int ans = gcd(gcd(gcd(a1,a2),a3),a4);
cout << ans << '\n';
}
}
```
:::
---
### ◎B. Hundred-Cell Calculation Puzzles
:::spoiler **◎ヒント1**
上端の $w$ 個の数字を $A_1,A_2,...,A_w$
左端の $h$ この数字を $B_1,B_2,...,B_h$ とします。
答が一意に定まる ⇔ これら $w+h$ 個の数字が一意に定まる
です。
:::
:::spoiler **◎ヒント2**
$x_i\ y_i\ n_i$ の条件は、$A_{x_i} + B_{y_i} = n_i$ であると言い換えることができます。
また、$A_1 = 0$ であると問題文に書かれています。
つまり、 $w+h$ 個の変数について、これら $w+h$ 元一次連立方程式 が与えられるので、解が一意に定まるかを答える問題となります。
:::
:::spoiler **◎ヒント3**
$k$ 個の変数がある場合、少なくとも $k$ 個の一次方程式がないと解が一意に定まらないと聞いたことがある人は多いでしょう。
しかし、$k$ 個の一次方程式がある場合、必ず答が一意に定まるわけではありません。例えば、$a,b,c,d$ の4変数について、以下の4元連立方程式が与えられた場合が考えられます。
* $a + b = 2$
* $b + a = 2$
* $c + d = 10$
* $a = 0$
この場合、 $a = 0, b = 2$ と定まりますが、$c,d$ は $(c,d)=(5,5),(3,7),(-1,11)$ など、多数の値を取る事ができます。
では、答えが一意に定まる条件は何なのでしょうか…？
:::
:::spoiler **◎補助解説1**
まず、この問題に登場する2種類の一次方程式を以下のように言い換えましょう。
1. $A_1 = 0$ タイプ (これ1つしかありませんが…)
→ 変数の値を、一意に定める。
2. $A_{x_i} + B_{y_i} = n_i$ タイプ
→ $A_{x_i}$ が一意に定まれば、$B_{y_i}$ が一意に定まる。逆も成立。
さて、$w+h$ 個の変数を頂点と見立てたグラフ(https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96)を考えます。
すると、この問題は以下のように言い換えられます。
* $A_1$ に対応する頂点に、印をつける。(値が一意である印)
また、$A_{x_i} + B_{y_i} = n_i$ に対応する各式について、$A_{x_i}$ に対応する頂点と、 $B_{y_i}$ に対応する頂点の間に辺を引く。
印が付いている頂点と直接辺でつながっている、印の無い頂点があった場合、その頂点にも印をつける。この操作をもう操作ができなくなるまで繰り返す。
操作が終了したとき、全ての頂点に印が付いているか？
※あることに気が付くと本当にそれでいいの？と思う方もいるかもしれませんが、それについては以下で補足します。
:::
:::spoiler **◎補助解説2**
結論として、全ての頂点が $A_1$ に対応する頂点と、直接的・間接的につながっていれば、全ての頂点に印が付きます。
全ての頂点がつながっていることを、グラフ理論では「連結」と呼びます。
あとは、グラフが連結かどうかを判定できれば解けます。
:::
:::spoiler **◎補助解説3**
グラフが連結かどうかは、深さ優先探索や、Union-Find を利用することで判定することができます。
:::
:::spoiler **◎補足1**
ここでは、ここまでの説明で感じそうな違和感その1「$n_i$ は使わないのか」について説明します。
問題文には、答えは必ず1つ存在すると書かれていました。そのため、条件間で矛盾が起こることはあり得ません。そのため、条件の内容である $n_i$ は不要で、条件がどの変数に関連しているのか $x_i,y_i$ だけが必要となります。
:::
:::spoiler **◎補足2-1**
ここでは、ここまでの説明で感じそうな違和感その2「$A_1$ と繋がっていなくても、値が一意になることはあるのでは？」について説明します。
正直これに気が付いた人はかなり鋭いと思います。
例えば、以下のような場合を考えてみましょう。
* $a = 0$
* $b + c = 3$
* $c + d = 4$
* $d + b = 3$
4つの変数 $a,b,c,d$ があり、4つの一次方程式があります。そして、1つだけ値が一意に定められています。
これは先述した本問題の状況と非常に似ています。
さて、この連立方程式のグラフを考えてみると以下のようになります。
上で説明したこの問題の解法に従うと、グラフが連結ではないので、この連立方程式は解が一意ではないことになります。
しかし！！なんとこの問題は解が一意に定まってしまいます。
普通に解けばわかるのですが、$a = 0,b = 1,c = 2,d = 2$ が答えです。
これ以外に答えはありません。なぜこのような事になったのでしょうか…？
__実は、長さが奇数の閉路(輪っか)があるとその閉路に属す頂点の数字が一意に定まるのです。__
上の図では、 $b \rightarrow c \rightarrow d \rightarrow b$ は長さ3の閉路なので、これに該当し、$b,c,d$ の値が一意に定まります。
なお、長さが偶数の閉路はあったとしても値が一意に定まりません。
ちゃんと証明するのは難しいので、直感的な説明を置いておきましょう。
上のような場合を考えましょう。$b,c,d,e$ の答えを1つ見つけたとします。
問題では辺の条件は $A_{x_i}+B_{y_i} = n_i$ の形式で与えられていたので、 $b$ の値に1を加えたとき、$c,d$ の値を1減らし、$e$ の値を1増やすことで、別の答えを作ることができます。よって、解が一意ではありません。
では、上の3つの場合はなぜ解が一意なのか。それは、$b$ を1増やしたとき、$c,d$ の値をどう変えたとしても、$b+c,b+d,c+d$ の値を全て維持することはできないからです。
:::
:::spoiler **◎補足2-2**
上の説明を読んで
「奇数長の閉路があったならば、$A_1$ と繋がっていなくても、答が一意になる場合があるじゃないか！！！」と思って頂けたらokです。
実はこの問題の条件下では、奇数長の閉路は存在しません。
なぜなら、この問題においてグラフは2部グラフ(https://ja.wikipedia.org/wiki/2%E9%83%A8%E3%82%B0%E3%83%A9%E3%83%95)になるからです。
グラフにおいて奇数長さの閉路は以下の条件を満たすときのみ、存在します。
* ある頂点から、奇数回の移動を行って、元の頂点に戻ってくる事ができる。
しかし、2部グラフにおいては奇数回移動すると必ず、元の頂点とは別のグループの頂点にいることになります。そのため奇数長の閉路は存在しえないのです。
よって、ここまでの説明から、この問題の条件下で奇数長の閉路は存在しないので、解が一意に定まる条件は、$A_0$ と繋がっていることのみであることが分かります。
:::
:::spoiler **◎実装について**
union-findでの実装が簡単ですので、こちらを紹介します。
union-findに関しては、[アルゴ式のこのページ](https://algo-method.com/courses/24) の10章を見れば理解できると思います。
練習問題を [Q2](https://algo-method.com/tasks/431) までやりましょう。
この問題の処理は、Q2とほぼ同じで、連結成分の個数が1個であるかを判定すればよいです。
:::
---
### C
:::spoiler **◎ヒント1**
この問題は、与えられた文字列を問題中にある画像のようなグラフに変換するパートと、そのグラフを元に最大値を求めるパートからなります。
構文解析については、次の記事がわかりやすく解説しています。
https://gist.github.com/draftcode/1357281
この記事に則って与えられる文字列のBNFを表現すると、次のようになります。
```
<根> ::= <部分木> (+ or -) <部分木> (+ or -) <部分木>
<部分木> ::= <数> or (<部分木> (+ or -) <部分木>)
<数> ::= ...
```
実装する際には、グラフに頂点を追加していくことになるので、部分木の根の頂点番号を返すような実装にすると楽かもしれません。
:::
:::spoiler **◎ヒント2**
演算子に対応する頂点は全て次数が3で、操作を繰り返すことで根にすることができます。
根を決めると、残りは各演算子の子の順番を決めるだけで、子の左右も操作で自由に入れ替えられます。
:::
:::spoiler **◎解説1(ヒント2に関する部分)**
各部分木について、子の順番を決めたときの最大値と最小値を求められるとします。
すると、演算子が `+` のときは各子の最大値を足せば部分木の最大値になり、最小値を足せば部分木の最小値になります。
演算子が `-` のときは、最左に最大値、残りを最小値にすると部分木の最大値になり、逆にすることで最小値になります。
ただし、このときにはどの子を最左に持ってくるかも考える必要があります。
実装する際には、場合分けをするのが面倒くさいので、子の順番、最大値と最小値のどちらを使うかで全探索をしてその最大値と最小値を取るようにすると楽かもしれません。
根にする頂点を一つ決めたときには、DFS(木DP)をすることで頂点数を $N$ として $O(N)$ で求めることができます。
しかし、このままだと $N$ 頂点すべてを根にしたときについて探索する必要があるので $O(N^2)$ になってしまいます。
:::
:::spoiler **◎ヒント3**
木のすべての頂点について、根にしたときの木DPを行いたいとき、全方位木DPと呼ばれる手法をつかうことで $O(N)$ で解くことができます。
:::
:::spoiler **◎解説2(ヒント3に関する部分)**
例えば、赤い頂点を根にして木DPをすると、色付きの四角で囲った部分木についての最小値と最大値は求められます。
次に、根を別の頂点に変えて木DPをすることを考えると、次のように辺の方向が一部変わり、右側の青い四角についての最小値と最大値を新しく求めることになります。
しかし、緑色の四角については既に求めているので値を再利用できます。
値を既に求めた部分木は、根に対する辺の方向に対応しているので、`(頂点、親)` を key にしてメモ化することで適切に再利用できます。
本来、再利用する際にある頂点に接続する辺をすべて見ると間に合わないケースもあるので累積和などを利用する必要がありますが、今回はすべての頂点の次数が 3 なので一つずつ見ても間に合います。
:::
---
### D
:::spoiler **◎ヒント1**
公式解説にありますが、1人が3つのポールから取るのではなく、Aさん、Bさん、Cさんの3人がそれぞれ担当するポールから1つ風船を取って渡すと考えるとわかりやすいです。
:::
:::spoiler **◎ヒント2**
3人の担当するポールを、$B_A, B_B, B_C$ とするとき、$\min \{\sum B_A, \sum B_B, \sum B_C\}$ を最大化したいという問題です。
:::
:::spoiler **◎ヒント3**
適当にポールの順番を決めたとき、3人のうちの誰がどのポールを担当することになるでしょうか。
逆に、どのポールを担当するか決めたとき、それぞれがそのポールを担当するようにポールの順番を決めることはできるでしょうか。
:::
:::spoiler **◎ヒント4**
常にそのように順番を決めることはできません。
例えば、`b = (1, 2, 3, 4, 5)` の場合、$B_A = {1}, B_B = {2, 3}, B_C = {4, 5}$ のように分けることはできません。
:::
:::spoiler **◎ヒント5**
ただし、最大値を達成する $B_A, B_B, B_C$ については、和が平均的になるのでポールを並び替えて担当するポールが $B_A, B_B, B_C$ になるようにできます。
:::
:::spoiler **◎ヒント6**
DPによって答えを求めることができます。
:::
:::spoiler **◎解説**
和の最小値を最大化するようにポールを分割することができるかを求めればいいので、それぞれの担当ポールの和が $x, y, z$ になるように分割できるかをDPで求めればよいです。
つまり、$k$ 本目のポールまでを見て、3人が今まで担当したポールに結ばれた風船の数の和が $x, y, z$ になるようにできるかを `dp[k][x][y][z]` とすれば良いです。
このままだと間に合わないので、ここで `sum[k] = b_1 + b_2 + ... + b_k` とすると `z = sum[k] - x - y` と求められるため DP の情報から消すことができ、`dp[k][x][y]` という形にできます。
計算量は $O(n^3 b_{\max}^2)$ となります。
python唯一の正解コードです。
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6749119#1
:::
---
### E
:::spoiler **◎ヒント1**
ABCで頻出の、頂点倍加系ダイクストラ問題です。
まず、ダイクストラ法を知らない人は、
https://qiita.com/Kept1994/items/0b185def44fca1aa64ed
これと、その中で紹介されている記事を見るといいかもしれません。
さて、グラフを2層に分けましょう。
下の層は、徒歩移動の層です。
上の層は、タクシー移動の層です。
徒歩の層 → タクシーの層 への移動は「タクシーに乗り込んだ」と考えます。
徒歩の層 ← タクシーの層 への移動は「タクシーから降りた」と考えます。
徒歩の層から、タクシーの層への辺は、毎回コストが変わるので難しいポイントです。
一方で、タクシーの層の頂点 $v$ から徒歩の層の頂点 $v$ へは、コスト0で移動できます。
:::
:::spoiler **◎ヒント2**
また、タクシーを非常に多くの回数使用した場合、コストの値が膨大な値になる問題を解決しなくてはいけません。
:::
:::spoiler **◎ヒント3**
一定回数(35くらい)以上タクシーに乗る場合、乗車にかかるコストが、移動コストに比べて非常に大きくなり、乗車回数の大小によってコストの総和がわかるようになります。
:::
:::spoiler **◎補助解説1**
基本的なアイデアは公式解説に書いてあるので、そちらを参照してください。
さて、ここでは実装方針について述べていきます。
まず、タクシー使用回数が35回以下の場合を考えます。
単純にグラフを71層に増やしてもいいのですが、定数倍が大きすぎてpythonなどの言語ではTLEすると思われます。
そこで、以下の方針を取ります。
1. 徒歩層・タクシー層の2層のグラフを構築しておく。それぞれの層には、それぞれに移動方法で利用できる辺を引いておく。また、タクシー層の頂点$v$ → 徒歩層の頂点$v$ にはコスト0の辺を引いておく。徒歩層 → タクシー層の辺は、グラフには含まないでおく。
3. 距離を格納する配列 $d$ を用意、$inf$(非常に大きい数) で初期化しておく。徒歩層の頂点 $1$ の距離を0で初期化、0を始点として普通にダイクストラ法を行う。
4. 以下の操作を35回繰り返す。
* ダイクストラ法の始点を格納する優先度付きキュー $q$ を空で初期化する。
* 全ての街 $v$ を見ていく。 現在の繰り返し回数を $i$ としたとき、$d_{タクシー層のv} > d_{徒歩層のv} + 2^i$ ならば、$d_{タクシー層のv} \leftarrow d_{徒歩層のv} + 2^i$ で更新する。その時、$q$ に $v$ を push する。
* $q$ 内の頂点を複数始点として、ダイクストラ法を行う。
この手法を用いると、無駄な推移を極限まで減らすことができます。これで、pythonでも余裕をもって通すことができました。
pythonでの回答例: https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6753381#1
:::
:::spoiler **◎補助解説2**
さて、補助解説1の処理を行った後、$d_{徒歩層のv}$ が $inf$ であるような頂点 $v$ に関しては、35回のタクシー乗車でたどり着けないことになります。
そこで、この補助解説2の手法でダイクストラ法を行う必要があります。
1. 徒歩層・タクシー層の2層のグラフを構築する。この時、エッジのコストは (タクシー乗車回数増加,移動コスト増加) というタプルで表すことにする。普通の移動辺は、(0,移動コスト) と表される。また、徒歩層の$v$ → タクシー層の$v$ に (1,0) の辺を、タクシー層の$v$ → 徒歩層の$v$ に (0,0) の辺を張る。
2. 距離を保持する配列 $d$ を用意する。$d$ の値も、タプルで表し、($inf,inf$) で初期化しておく。
3. $d_{徒歩層の1}$ = (0,0) で初期化し、ダイクストラを行う。距離として、タプルをそのまま使用する。距離の足し算はタプルをそのまま足し算し、タプル同士の比較は、1項目を優先的に比較する。
:::
Sign in with Wallet
Connect another wallet