【BBC】Mexico suffering world’s highest Covid death rate as cases surge
grant: 許可する、与える
grant reports: 報告を与える。報告する?ride out: 切り抜ける
I think we just need to ride out this slump in the economy and then we will be okay.
この経済スランプを乗り越えたらあとは大丈夫だと思う。
He tried to ride out the virus at home: 自宅でウイルスを乗り切ろうとした。grapple: 突掴み合いをする(with), 課題に取り組む(with)
We grappled with the problem.
grapple with grief: 悲しみと向き合う？(悲しみに頭を悩ませる)
grapple with the thorny issues of: ~の扱いに頭を悩ませる。
thorny: 棘の多い、困難な、苦しいstaggering: 千鳥足の、驚くべき、驚異的な
a staggering piece of news: 唖然とするニュースmunicipality: 地方自治体、市当局
The municipality has closed the hospital.afloat: 海上に、破産せずに、広まって
The company is still float: その会社はまだ破産しなでいる。
set a rumor afloat: 噂を立てる。
Keeping tourist afloat has had deadly consequences: 観光産業を破産させないでいると致命的な結果になっている。
【BBC】AstraZeneca Covid vaccine: What do we know about the risks?
- setback: 停滞、妨げ
He had(suffered) a setback in his business.
It's the latest setback for the AstraZeneca vaccine.
jab: ワクチン接種
bloom clot: 血栓
cerebral: 大脳の
- venous: 静脈の
- sinus: 曲がり
thrombosis: 血栓症
hemorrhage: 出血、(資材・人材の)大量損失
cerebral hemorrhage: 脳出血
a hemorrhage of scientific brain: 科学者の頭脳流出substantial: 実在する、頑丈な、たくさんの
have a substantial meal
a substantial building: 頑丈な建物
a men of substantial means: かなりの資産家take away: 取り除く
take away from: ~の価値を落とす、減ずる、損なう
You shouldn't take away from the message that you shouldn't get vaccinated.
ワクチン接種すべきでないというメッセージを見落とすべきではない。
リスクは必ずしもあるよという意味？ramp up: 一定の割合で増やす、増加する The latest controversy ramped up.
predicate: (真実・現実と)断言する
The theory predicates the Big Bang theory of the universe: この話は宇宙のビッグバン説を正しいと説いている。rollout: 市場への投入、導入、運用開始
The Netherlands paused its Astrazeneca rollout for under 60s.err: 間違いをする、過ぎる(on)、それる(from)
err in one's judgement
err on the side of severity: 厳格に失する(on the side of で失する)
【ABC136】D - Gathering Children【ダブリング】
今回はダブリングと呼ばれる手法を使って解いて見ます。
上のブログでも解説されているようにnext[i][v]を定義します。
next[i][v]: vから$2^{i}$ステップで到達できる場所
まずは$i=0$の場合を考えてnext[0][v]を初期化します。
それぞれの場所vに記されたL, Rに従ってLならv-1、Rならv+1をnext[0][v]に格納します。
これ以降は
next[i+1][v] = next[i][next[i][v]](vから$2^{i}$ステップで行ける場所からさらに$2^{i}$ステップ移動する。)
に従って更新していきます。
なぜ2の乗数になっているかは漸化式に値を代入してみれば確認できます。
next[0][v]: vから1ステップで行ける場所(総ステップ数：1)next[1][v] = next[0][next[0][v]]: vから1ステップで行ける場所からさらに1ステップで行ける場所(総ステップ数：2)next[2][v] = next[1][next[1][v]]: vから2ステップで行ける場所からさらに2ステップで行ける場所(総ステップ数：4)
next[1][v]の総ステップ数が2であることを利用しました。
せっかくなのでさらに計算を進めると、
next[3][v] = next[2][next[2][v]]: vから4ステップで行ける場所からさらに4ステップで行ける場所(総ステップ数：8)next[4][v] = next[3][next[3][v]]: vから8ステップで行ける場所からさらに8ステップで行ける場所(総ステップ数：16)next[n+1][v] = next[n][next[3][v]]: vから$2^{n}$ステップで行ける場所からさらに$2^{n}$ステップで行ける場所(総ステップ数：$2^{n+1}$)
以上のようにダブリングしていることが分かりました。
next[i][v]を参照することでvから$2^{i}$ステップ進んだ場所がどこなのかを知ることが出来ました。
では$2^{i}$以外のステップ数進んだ場合を知るにはどうしたらいいのでしょうか？
整数$x$を2進数で展開して下位のビットから走査し1であればnext[i][v]を使って場所を更新していきます。
コードは以下のようになります。
int s = 0; int step = 5; rep(d, MAX-1) { if (step & (1<<d)) s = next[d][s]; } cout << s << " " << S[s] << endl;
上の例では場所0から5ステップ進んだ後の場所を求めています。
5は2進数で表すと101です。一番下位の0ビット目を見ると1なのでまずは1ステップだけ進みます。
そうするとnext[0][0] = aに到達しました。(この場所をaとしました。)
次の1ビット目は0なので無視します。2ビット目が1なのでaから$2^{2}$ステップだけ進みます。
最終地点はnext[2][a]となります。
コード全体は以下にUpしました。
powの計算などにもダブリングが使えるみたいですね。
【C++】ダイクストラ法の実装の注意点
【5.1公開鍵暗号】暗号文から元のメッセージを復元する時の計算
「量子コンピュータ入門(古澤明著)」の5.1章で暗号文から元のメッセージを復元する時の途中計算(p71)のメモになります。
https://www.amazon.co.jp/量子コンピュータ入門-第2版-宮野-健次郎/dp/4535788057
以下の途中計算になります。
数式の番号は適当に降りました。
問題となるのが(4)から(5)の式変形だと思います。
本の中ではフェルマーの小定理を使うように指示されています。
ただこの形のままではそのまま使うことが出来ません。
- pが素数でgとpが互いに素の場合、$g^{p-1} \equiv 1\;(\text{mod}\;p)$が成り立つ。
(4)から(5)では$P^{k(p-1)(q-1)} = nM + 1$(nは整数)が成り立てばいいことが分かります。
$p, q$それぞれ単独で見ていきましょう。
まずは$p$だけに注目すると$P, p$は互いに素なので、
さらに両辺を$k(q-1)$乗すると、
よって、$P^{k(p-1)(q-1)} = xp + 1$($x$は整数)と表すことが出来ます。
$q$についても同様にして、$P^{k(p-1)(q-1)} = yq + 1$($y$は整数)と表せます。
これらが等しいので$xp = yq$となります。
ここで$p, q$が互いに素なので$x=qz, y=pz$となる整数$z$が存在します。
以上より$P^{k(p-1)(q-1)} = zpq + 1$と表せることが出来ました。
これを利用すると(4)から(5)の式変形が可能になります。
【ABC194】D - Journey【幾何分布の期待値】
幾何分布の期待値に対応しているようです。
幾何分布の期待値の計算は以下を参照して下さい。
幾何分布の確率関数からの期待値と分散の導出 | AVILEN AI Trend
k回目で初めて成功する期待値を求めてNまで合計すれば計算できます。
コードは以下にUpしました。
似たように幾何分布の期待値を用いて計算する問題：
ガチャ問題とも呼ばれているようです。
【JOI2016】D - ぬいぐるみの整理 (Plush Toys)
公式の解説
参考にした解説
上の解説を自分なりに咀嚼してみました。
$O(M!)$の解法
ぬいぐるみの初期配置が「1232132」の場合で考えてみます。
まずは計算量が$O(M!)$の解法について考えます。
左から順番に連続するぬいぐるみの種類の詰め方を列挙します。
今は3種類のぬいぐるみが存在するので、「123, 132, 213, 231, 312, 321」の6(=3!)通り存在します。
例えば「123」の詰め方の場合、並び替えた後の配置は「1122233」となります。
他にも「312」の場合は「3311222」となります。
ここから入れ替えるぬいぐるみの個数を数えていきます。
下の表を作ります。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 123の配置 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
| 一致 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
「元の配置」が最初に絵耐えられた配置。
「123」の配置が左から順番に連続する種類を決めたときの配置。
「一致」は「元の配置」と「123」の配置で数字が同じなら1, 違う場合は0。
「一致」の中の0の個数が場所を入れ替えるぬいぐるみの個数になります。
上の例では4個になります。
これを全ての「123, 132, 213, 231, 312, 321」について調べて最も個数の少ない配置が答えになります。
ただ、問題の制約で種類$M $が$M\le 20$なので$M!$がものすごく大きな数になり間に合いません。
$O(2^{M})$の解法
次に計算量が$O(2^{M})$の解法について考えます。
動的計画法(DP)を使います。
種類Mの部分集合をSとして、DPテーブルを以下のように定義します。
- DP[S] := Sに含まれる種類のぬいぐるみを左から順番に詰めるまでに必要な入れ替え数。
例えばS={1,2}の場合は左から順番に12(あるいは21)と連続して同じ種類のぬいぐるみを配置した時に必要な入れ替え数になります。
Sはあくまでも左に詰めることが決まった種類の組み合わせだけを表しており、実際の順番は分からない。
上の例では順番としては「12」か「21」が考えられますがどちらになったかは分かりません。
これを知ろうとすると結局$O(M!)$と同じ計算量が必要になります。
あくまでも左から連続することが確定した集合にしか過ぎません。
なので計算量を$O(2^{M})$まで落とすことが出来ます。
次にSに含まれていない種類iを新たにSに加えてDPを更新していきます。
更新にはiを加えたときに必要な入れ替え個数を数える必要があります。
それが計算できたとしてその数がx[i]とすると更新式は以下のようになります。
- DP[S U i] = min(DP[S U i], DP[S]+x[i])
「S U i」は集合Sに新しい要素iを加えた集合を表します。
では最後にx[i]の計算方法について考えていきましょう。
これを計算するには種類毎の累積和が必要になります。
種類毎に配列accumを準備してある位置iまでに登場した種類の累積和を管理します。
accum[m][i]は場所iまでに存在する種類mのぬいぐるみの累積和を表します。
またaccum[m][0]=0と定義します。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 1の累積和 | 1 | 1 | 1 | 1 | 2 | 2 | 2 |
| 2の累積和 | 0 | 1 | 1 | 2 | 2 | 2 | 3 |
| 3の累積和 | 0 | 0 | 1 | 1 | 1 | 2 | 2 |
場所rからlまでに含まれる種類mのぬいぐるみの数はaccum[m][r] - accum[m][l]で計算できます。
(r-l == accum[m][r] - accum[m][l]ならその区間は同じ種類のぬいぐるみが連続しているとも言える。)
例えばm=2のr=6からl=2に含まれる同じ種類のぬいぐるみの数はaccum[m][r] - accum[m][l]=3-1=2になります。
実際に場所3と場所6に種類2のぬいぐるみが存在しています。
ある位置tまで既に連続する種類で整理されておりそこからLだけ別の種類mのぬいぐるみを連続して配置したい場合を考えます。
cnt[m]が種類mのぬいぐるみの総数と定義すると、tは今までに調べた部分集合Sに含まれる種類についてcntの和を取れば計算できます。($t=\sum_{i\in S}cnt[i]$)
次にこのxからx+Lの区間に既に配置されている種類mのぬいぐるみの個数を調べます。
これはaccum[m][x+L]-accum[m][L]から計算できます。
既に種類mのぬいぐるみが配置されていれば入れ替える必要はないためx[m]は以下のように計算できます。
- x[m] = cnt[m] - (accum[m][x+L]-accum[m][L])
以上で解法が整備できました。
実際に上の例で計算してみましょう。
DP[0] = 0、それ以外はINFで初期化しておきます。
S = {1}の場合について計算してみます。
種類1のぬいぐるみの個数は2個なのでcnt[1]=2になります。
場所2までを種類1のぬいぐるみで連続させるときに必要な入れ替え数について考えます。
これはcnt[1] - (accum[1][2]-accum[1][0]) = 2 - (1 - 0) = 1になります。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 確定した配置 | 1 | 1 |
ここでDP[{1}] = 1に更新されます。
次に種類2を加える場合について考えます。
cnt[2] = 3です。始まりの位置はt=cnt[1]=2になります。
これより場所2から場所5までに存在する2の数を計算して見ます。
accum[2][5]-accum[2][2] = 2 - 1 = 1になります。
よって種類2について入れ替える個数はcnt[2] - (accum[2][5]-accum[2][2]) = 3-1 = 2になります。
これよりDP[{1, 2}] = DP[{1}] + 2 = 3に更新されます。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 確定した配置 | 1 | 1 | 2 | 2 | 2 |
最後に種類3を加える場合について考えます。
cnt[3]=2です。始まりの位置はt=cnt[1]+cnt[2]=2+3=5になります。
これより場所5から場所7までに存在する3の数を計算して見ます。
accum[3][7]-accum[3][5] = 2 - 1 = 1になります。
よって種類3について入れ替える個数はcnt[3] - (accum[3][7]-accum[3][5]) = 2-1 = 1になります。
これよりDP[{1, 2, 3}] = DP[{1, 2}] + 1 = 3+1=4に更新されます。
この結果は$O(M!)$の例で計算した結果と一致しています。
以上をS={0}, {1}, {2}, {3}, {1,2}, {2, 3}, {3, 1}, {1,2,3}それぞれについて更新していきS={1,2,3}となった時のコストの最小値を求めれば良いです。
$O(M!)$の時は3つの数字の並びについて全列挙していました。
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)の6通り。
今回は$2^{M}$通りの部分集合(冪集合)に対して状態を遷移させていき最終的には1種類のS={1,2,3}に到達した時の個数の最小値を求めています。
((1,2,3)なのか(3,2,1)なのかは区別していない。)
$M=3$では$2^{M}$の方が計算量は大きくなりますがさらに$M$が大きい場合は$2^{M}$の方が計算量は減ります。
$M=20$では$2^{M}=1048576$なのに対して$20!=10^{18}$になってしまいます。
C++で実装したコードを以下ににUpしました。
