2017-03-08

ABC017 C ハイスコア

自力で満点解法思いついたの嬉しかったのでその記念。

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder

問題概要

$N$ 個の遺跡があり、遺跡を探索すると宝石と得点が得られる。
$i$ 番目の遺跡を探索したときに、得点 $s_i$ 点を獲得し、 $M$ 種類ある宝石のうち $l_i$ 番目から $r_i$ 番目までの宝石を得られる。
すべての種類の宝石を1つ以上獲得すると魔王が復活してしまうので、魔王が復活しないように遺跡を探索したときの得点の合計の最大値を求める。

制約

$1 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le l_i \le r_i \le M$
$1 \le s_i \le 5000$

部分点

30点…… $N \le 8$ , $M \le 8$ を満たすテストケース
100点…… $N \le 5000$ , $M \le 5000$ を満たすテストケース
101点……すべてのテストケース

TLE解法

100点解法*1。
魔王が復活しないとき、少なくともどれか1つの宝石は獲得していない。獲得してはいけない宝石を1つ決めると、各遺跡について、その宝石を獲得できるかどうかで、その遺跡で得点を獲得できるかがわかる(最大の得点について考えているので、獲得してはいけない宝石をその遺跡で取ることができないならば、その遺跡を探索して得点を得た方がよい)。
つまり、獲得してはいけない宝石を1つ決めたとき、そのときに取りうる最大の得点は一意に決まる。

獲得してはいけない宝石を順番に試すのに $O(M)$ 。獲得してはいけない宝石を決めた後、各遺跡でその宝石を獲得できるかを調べるのに $O(N)$ かかる。よって、全体の計算量は $O(NM)$ 。

Submission #948966 - AtCoder Beginner Contest 017 | AtCoder

満点解法

(私が解法を考えていたときの脳内をだいぶ忠実に再現してみる)

「すべての宝石を獲得してはいけない」というのが最大の制約なので、獲得してはいけない宝石を一つ定めるという方針はそのままでよさそう。……TLE解法のとおり、獲得してはいけない宝石を決めたときに、その宝石を獲得してしまう遺跡の得点は得られない。……「得られない」ということは、「獲得してはいけない宝石を決めたときに、各遺跡で何点得られないか」というふうに全体からの引き算で考えることができる。もちろん、得られない点数が一番小さくなる宝石を、獲得してはいけない宝石として選べば良い。

試しに、サンプル1を表に書いてみる。

f:id:wk1080id:20170308022800p:plain

はじめに各遺跡について、獲得してはいけない宝石の欄にその遺跡で得られる得点をマイナス表記する。
その後、獲得してはいけない宝石を1つ決めると、その宝石の列さえ見れば最終的な得点が求まることがわかる。
そこまでわかって、いもす法*2を使えばこの表を圧縮して、計算量も落とすことができる！と気付いた。やったね！たえちゃ(ry

いもす法を使うことで、獲得してはいけない宝石を1つ決めると、そのときの最大の得点は $O(1)$ で求まる。
よって計算量は、いもす法の前処理(記録＋シミュレート)に $O(N+M)$ 、各宝石を獲得しない場合について計算するのに $O(M)$ かかるので、全体で $O(max(N,M))$ 。

Submission #1150134 - AtCoder Beginner Contest 017 | AtCoder

ソースコードでは、さっきの表と違い、各遺跡で取ることができない点数を負数ではなく正数で計算している(ので最後に総得点から引き算している)。あと、宝石のindexに注意する。

感想

得点が0点の状態から考えて何点獲得できるか、ではなく、得点がMAXのときから考えて何点獲得できないか、に思考をシフトさせるのが面白かった。
例示は理解の試金石*3だ！！！！と再確認させられた。サンプル試すの大事。

いもすの入力の際に+=じゃなくて=にしていたせいで30分くらい溶かした
— りか (@wk1080id) 2017年3月7日

↑悲しい……

あと、いもす法は好きです(なら間違えるな

*1:30点解法は考えてないので知らない。たぶんすべての遺跡について、探索するかしないかを全探するんじゃないかな。……と思ったけど、制約が8だしnext_permutationを使ってシミュレートするのか。

*2:いもす法知らない人はこちらを参照してください->いもす法 - いもす研 (imos laboratory)

*3:数学ガールの主人公「僕」がよく言う台詞

2017-02-23

ABC054 D Mixing Experiment

競技プログラミング AtCoder

頑張って実装したので記事にするぞ。最近更新頻度高いし競プロ頑張ってる感がある*1。

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder

問題概要

N種類の薬品のうちいくつかの薬品を購入する。薬品iにはタイプAの物質を $a_i$ グラム、タイプBの物質を $b_i$ グラム含んでおり、価格 $c_i$ 円で売られている。
タイプAの物質とタイプBの物質の混合比が $M_a : M_b$ となるのに必要な最小予算を求めよ。

制約

$1 \le N \le 40$
$1 \le a_i, b_i \le 10$
$1 \le c_i \le 100$
$1 \le M_a, M_b \le 10$

DP解法1

求めるものは「物質の重さの比が $M_a : M_b$ となるのに必要な最小予算」なので、購入するそれぞれの物質の重さが最終的にわかればよい。よって、

dp[i][j][k]:=薬品 i まで見たときに、購入するタイプAの物質が合計 j グラム、タイプBの物質が合計 k グラムとなる最小費用

という配列をつくる。
j : k = $M_a : M_b$ となるdp[n][j][k]の最小値が求める最小費用。

計算量は $O(N^3 (max( a_i, b_i ))^2 )$ 。

Submission #1123367 - AtCoder Beginner Contest 054 | AtCoder

DP解法2

さっきのDP解法よりさらに計算量を落とすことができる。

(タイプAの物質の合計の重さ)：(タイプBの物質の合計の重さ)＝ $M_a$ ： $M_b$

となれば良いので、

(タイプAの物質の合計の重さ) * $M_b$ - (タイプBの物質の合計の重さ) * $M_a$ = 0

となる最小費用をもとめればよい。よって、

dp[i][j]:=薬品 i まで見たときに、「購入するタイプAの物質の合計の重さと $M_b$ の積」と「購入するタイプBの物質の合計の重さと $M_a$ の積」の差が j のときの最小費用

という配列を作り、dp[n][0]が答えとなる(ただし、このままだとjは負の値をとることがあるので、jの値はずらす必要がある)。

計算量は $O(N^2 max( a_i , b_i ) max( M_a, M_b ))$ *2。

Submission #1121081 - AtCoder Beginner Contest 054 | AtCoder

DP解法3

もう一つ別の解法があるのを見つけたので紹介だけ(参考サイト：ABC054-D「Mixing Experiment」 | クリエイティヴなヴログ)。
計算量はさっきのDP解法2と変わらないけど、やりかたが違う。

各薬品 i について、

d[i]:= $a_i$ * $M_b$ - $b_i$ * $M_a$

を最初に求めておく。そのあと、

①d[i]=0となる $c_i$ の最小値を求める
②d[i]<0となるものとd[i]>0となるものをいくつか選び、和が0になるものの最小予算を求める(ここでDPを使う)

①と②のうち小さいほうが答えとなる(詳しい解き方はリンク先をみてください)。

半分全列挙

半分全列挙は昔に一度だけやったことがあるけど*3、復習しないので覚えてなかった(ので昔のコードを見ながら思い出しつつやった)。

半分全列挙は、まず半分にわけて、それぞれでありえる組み合わせを全列挙して、うまくmergeして答えを求める方法。名前そのまま。
計算量は、半分にわけて全列挙するところが $O( 2^{ \frac{N}{2}} )$ で、mergeするところが $O( \frac{N}{2})$ なので全体で $O( \frac{N}{2} \times 2^{ \frac{N}{2}})$ *4。

Submission #1128677 - AtCoder Beginner Contest 054 | AtCoder

感想

コンテスト中に通したかった……(そもそも全探でしようとしてたのでダメ)

ひとつの問題でいろいろな解き方ができるのは本当におもしろいし楽しいなあ。

同じ問題をずっと解いてるからsolvedが増えない><
でもいろいろな解法で考察することで実力がつくと信じてる！
— リサさんになりたいbot (@wk1080id) 2017年2月19日

*1:と書き始めた当初は思っていたが、記事が完成するのに1週間近くかかったのでダメ

*2:配列の大きさで考えると $O(N^2 max( a_i , b_i ) ( M_a + M_b ) )$ になる

*3:C: 無駄なものが嫌いな人 - AtCoder Regular Contest 017 | AtCoder

*4:この書き方だと某警察につかまりそう。 $O(N \times 2^{ \frac{N}{2} })$ が正しいのだと思うけど、それでは $N=40$ でうまくいくことがわからないし…。

2017-02-19

ABC054 C One-stroke Path

競技プログラミング AtCoder

頑張って実装したやつは記事にしようという試み。

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

問題概要

自己ループと二重辺を含まないN頂点M辺の重み無し無向グラフが与えられるので、頂点1を始点として、全ての頂点を1度だけ訪れるパスは何通りあるかを求める。

制約

$2 \le N \le 8$
$0 \le M \le \frac{N(N-1)}{2}$

再帰を使った解法

コンテスト中に解いた解法はこれ。とりあえずDFSで探索して、行った頂点を記憶しておく。頂点1からN-1回移動したときにすべての頂点に行っていれば、一つの経路として数える。「DFSで行ったところを記憶する」のがとても面倒だった(引き返すときにマイナスしないといけないので)。

Submission #1105966 - AtCoder Beginner Contest 054 | AtCoder

next_permutationを使った解法

すべての頂点を1回しか通らないなら、1からNまでの数字からなる数列の並ぶ順番と頂点をたどる経路を同一視して考えられるよね。ってとこまでわかったけど、N桁の数列の並び替えとかがわからなかった。
next_permutationという関数があるらしいので(知らなかった)、調べて実装してみた~~(ニコニコ動画とかに実装してみたとかいうジャンルありそう)~~。
next_permutationは、受け取った配列を、辞書順で次の並べ方に並べ替える関数。最初は配列を昇順になるようにしておかないと、うまく全部まわってくれないので注意が必要。次の順列が存在する場合はtrueを返し、存在しない場合はfalseを返す。

配列の要素をi番目にいる頂点とすると、毎回頂点iと頂点i+1の間に辺が張られているかを調べ、辺がすべて張られている並べ方の数を出力する。
N頂点の並べ替えと隣り合う頂点間に辺が張られているかそれぞれ調べるので、計算量は $O(N! \times N)$ 。Nが小さいから間に合う。

Submission #1113580 - AtCoder Beginner Contest 054 | AtCoder

next_permutation関数は辞書順で次の並べ方を表示するので、配列のはじめの要素が1以上のときにnext_permutation関数に配列を渡しても、配列のはじめの要素が0になることはない。よって、配列のはじめの要素が0でなくなったときには今後始点が0になることがないのでdo-while文を抜けても大丈夫。

感想

next_permutaion関数すごすぎる。なにこの便利な関数。
実はコンテスト中は、Cの実装&&バグ取りに50分くらいかけてて(コンテストの前にsetとか使ってたせいで余計なことを考えてた)、next_permutationの解法書くのに10分くらいしかかかってないから、コンテストで使えてたらもっと順位が良かったのになと思った。まあレートには関係ないけど。
りんごさんが解説放送で余裕があればnext_permutationを自作してみてね！と言っていたけど私には無理だった。

2017-02-16

ABC013 C 節制

競技プログラミング AtCoder

先日 AtCoder Virtual Contest でやっていたABCのC埋めに出てきて、コンテスト中には解けなかったのでゆっくり解いていたが、満点解法がわからなかった&&時間がかかったので書く。

C: 節制 - AtCoder Beginner Contest 013 | AtCoder

問題概要

N日間の食事を次の3つから選ぶ。

・普通の食事 ( 出費A円、満腹度 +B )
・質素な食事 ( 出費C円、満腹度 +D )
・食事抜き　 ( 出費なし、満腹度 -E )

最初の満腹度がHで、一度も満腹度が0以下にならないとき、最低何円でN日間乗り切れるか。

制約
$1 \le N \le 5 \times 10^5$
$1 \le H \le 10^9$
$1 \le C < A \le 10^6$
$1 \le D < B \le 10^6$
$1 \le E \le 10^6$

部分点

10点…… $N \le 10$ を満たすテストケース
40点…… $N \le 50, H \le 50, B \le 50, D \le 50$ を満たすテストケース
100点…… $N \le 10^3$ を満たすテストケース
101点…… すべてのテストケース

部分点解法その1

$N \le 50 , H \le 50 , B \le 50 , D \le 50$ の解法。問題を見た時にまずこれが浮かんだ。

日にちと満足度が決まればそのときの最小の食費は一意に定まるので、
dp[i][j]:=i日目に満足度がjであるときにかかる最小の食費
という配列をもつDPで解ける。
満足度の上限はH+NBより
計算量は $O(N(H+NB))$ つまり $O(BN^2)$ 。

部分点解法その2

$N \le 10^3$ の解法。DPが思いついたあと、100点解法では満足度の上限がないため、満足度を使わずに食費が一意に定まるものは他にないかと考えて、「それぞれの食事をした回数が決まれば、満足度も食費も求めることができる！」と気づいた。
普通の食事の日数と質素な食事の日数が決まれば、食事抜きの日は「 n - (普通の食事の日数) - (質素な食事の日数) 」に決まるから、計算量は $O(N^2)$ 。

Submission #1111965 - AtCoder Beginner Contest 013 | AtCoder

普通の食事の日数をi日、質素な食事の日数をj日とすると、食事を抜く日数はn-i-j日である。
このとき、n日目の満足度は「 $H + Bi + Dj - E(n-i-j)$ 」であるから、これが0より大きければ満足度が一度も0以下になることがないような食事の順番が存在する*1。よって、このときの合計の食費「 $Ai+Cj$ 」が今までの暫定の最小の食費よりも小さければ暫定値を更新する。

満点解法

$N \le 5 \times 10^5$ の解法。思いつかなかったので解説を見たら頭が良かった(それはそう)。

制約より、満腹度が大きくなるほど合計の食費も大きくなるので、合計の食費をできるだけ小さくするには満腹度が(一度も0以下にならないという制約を満たしつつ)できるだけ小さくなるようにすればいい。

つまり、普通の食事の日数をi日、質素な食事の日数をj日、食事を抜く日数はn-i-j日としたとき、 $H + Bi + Dj - E(n-i-j) > 0$ を満たすようなiとjのうち、iとjが最小になるものを考える。

2変数であるから、計算しやすいように片方の変数iを固定して考える*2。
iを固定したとき

$H + Bi + Dj - E(n-i-j) > 0$

$H + Bi + (D+E)j - E(n-i) > 0$

$j > \frac{E(n-i)-H-Bi}{D+E}$

となる最小の整数jは $O(1)$ で求まる。
これを $0 \le i \le n$ についてそれぞれ調べるので、全体の計算量は $O(N)$ 。

Submission #1112041 - AtCoder Beginner Contest 013 | AtCoder

普通の食事の日数がi日のとき、質素な食事の日数が0日かそうでないかで場合分けをする*3。
$H + (B+E)i - En > 0$ のときは質素な食事の日数が0日で良いため、合計の食費は $Ai$ となる。
$H + (B+E)i - En \ge 0$ のときは、最小となるjを求めて、 $i+j \le n$ のとき(普通の食事の日数と質素な食事の日数の合計がn日以下のとき)は、合計の食費は $Ai+Cj$ となる。 ~~合計がn日より大きい場合は、なかったことにする。~~

感想

ABCのCなのに難しい問題が多くてつらい(人権がない)

*1:たとえば、はじめの1日目からi日目までは普通の食事をとり、i+1日目からi+j日目は質素な食事をとり、i+j+1日目からn日目は食事を抜くとき、満足度は一度も0以下にならない

*2:「予選決勝法」を思い出して懐かしい気持ちになった

*3:この場合分けをせずに、 $0 \le j$ かつ $i+j \le n$ にしていたらWAで、このWAが取れずにずっと悩んでいた

2017-02-11

AGC005 B Minimum Sum

競技プログラミング AtCoder

昨日解いていて、解説を見ても理解するのに手こずったので、考え方を書いてみる(一応この問題について書いてるブログはあったけど、解法が違ったので、自分用に)。

B: Minimum Sum - AtCoder Grand Contest 005 | AtCoder

問題概要

$1$ から $N$ までの数字を並べ替えた長さ $N$ の数列 $a_1, a_2, … , a_N$ が与えられるので
$\sum_{l=1}^{N} \sum_{r=l}^{N} min(a_{l}, a_{l+1}, … , a_{r})$ を求める。

つまり、長さ $N$ の数列の $_N C _2$ 個の区間それぞれについて最小値を求め、それの合計を求める。

制約は $N <= 2 \times 10^5$ のため、計算量は高々 $O(N)$ か $O(N log N)$ 。

TLE解法

自力で思いついたのは全区間の最小値を順番に足していく $O(N^2)$ の解法。
調べる区間の幅をだんだん大きくしていくという考え方。

Submission #1101992 - AtCoder Grand Contest 005 | AtCoder

ansの初期値に代入している $\frac{n(n+1)}{2}$ は、隣り合う1項の最小値(つまりその項自身)の合計値。数列には $1$ から $N$ までの数がそれぞれ1回ずつ出てきているので、等差数列の和と考えて計算する。

repの中では、隣り合う $N-i+1$ 項の最小値を計算してansに足していく。

区間(部分数列)でいうと
{ $a_0, a_1$ } { $a_1 , a_2$ } … { $a_{N-2} , a_{N-1}$ }
{ $a_0 , a_1 , a_ 2$ } { $a_1 , a_2 , a_3$ } … { $a_{N-3} , a_{N-2} , a_{N-1}$ }
…
{ $a_0 , … , a_{N-2}$ } { $a_1 , … , a_{N-1}$ }
{ $a_0 , … , a_{N-1}$ }
の最小値を順番に求めている。

setを使った解法

$O(N log N)$ の解法は「最小値が $a_i$ となる区間がいくつあるかを計算し、その区間数と $a_i$ の積の合計を求める」。

$a_i$ が最小値となる区間は、数列の $a_i$ より前の部分で $a_i$ に一番近いところにある $a_i$ よりも小さな値との距離、数列の $a_i$ より後ろの部分で $a_i$ に一番近いところにある $a_i$ よりも小さな値との距離がわかれば求めることができる。

たとえば、{5, 4, 9, 2, 1, 8, 6, 7, 3}という数列の6が最小値となる区間を考える。
6が最小値になる区間は6より小さな値が存在しないので、もとの数列の6より小さい値にだけ色をつけると
{5, 4, 9, 2, 1, 8, 6, 7, 3}
となり、6より小さな値(赤色の数字)が存在しないような区間(部分数列)は{8,6}{8,6,7}{6}{6,7}の4つとなる。
ここで、6が最小値となる区間の左端は、はじめの数列の「6より左にあって6より小さな一番6に近い値(=1)」よりも右で、6よりも右ではない数字になっていることがわかるので、6が最小値となる区間の左端は8,6のどちらかであり、この8,6という左端の候補の数(=2)は「6より左にあって6より小さな一番6に近い値(=1)」と6との距離である。
同様に、6が最小値となる区間の右端は6,7のどちらかであり、右端の候補の数(=2)は「6より右にあって一番6に近い6より小さな値(=3)」と6との距離である。
そして、6が最小値となる区間の数は(左端の候補の数)*(右端の候補の数)より2*2=4個と求めることができる。

今見ている数字 $a_i$ が最小値となる区間の数を求めるためには、 $a_i$ の左右それぞれで、 $a_i$ より小さく $a_i$ に一番近い数との距離が必要になる。よって、要素を自動的にsortしてくれるsetに、 $a_i$ より小さな値の添字を入れておき、 $a_i$ の添字iに一番近い数をlower_boundを使って高速に調べればよい。

$a_i$ が最小値となる区間を調べる際に必要な情報は「 $a_i$ よりも小さな値がどこにあるのか」なので、できるだけ小さな $a_i$ 、つまり1から順番に調べていくと、区間数を調べた後にsetに $a_i$ をそのまま入れることができるので、効率よく求めることができる。

setの要素の挿入に $O(logN)$ 、set内のlower_boundに $O(logN)$ かかるので、 $a_i$ それぞれに対して行っても $O(N log N )$ 。

Submission #1102173 - AtCoder Grand Contest 005 | AtCoder

入力を配列aで受け取り、配列orderには、区間数を調べる $a_i$ の順番になるように、 $a_i$ の添字iを格納する。つまり、a[order[0]]=1, a[order[1]]=2, … , a[order[N-1]]=Nとなるように格納する。

はじめにsetに入れた-1とNは番兵の役割をする。 $a_i$ の前に $a_i$ より小さな値が存在しないときは-1が返され、 $a_i$ の後ろに $a_i$ より小さな値が存在しないときはNが返される。

あとは最小値が1となる区間、最小値が2となる区間、…と順番に区間の数を計算してtmpに入れて、ansに足していく。

その他の解法

pekempeyさんがUnion-Findを使った解法を解説しています。

AtCoder Grand Contest 005: B. Minimum Sum - pekempeyのブログ

また、standingsで他の人のソースコードを見てみると、stackを使った解法などもあるようです(私にはよくわからなかったのですが……)。

最後に

この問題が400点なんて嘘ですよね？(500はありそうだと思った)

2017-02-07

エクセルでの乱数発生のメモ

この春休みは計算力を上げることを目標として頑張っているので、さまざまなことに取り組んでいる。その一環として使うプリントを作成した。その際の「１から１００までの整数をランダムに（重複なしで）表示させる方法」をメモしておく。難しくはなく、簡単にできるので大量にプリントを作ることができた。

以下その方法。

①エクセルを起動させる

ここは気合いでなんとかなる。

②A1に「=RAND()」を入力する

RAND関数は0以上1未満の小数の乱数を作る関数である。

③A100までコピーする

これで、0以上1未満の小数の乱数がA1からA100まで100個作成できた。

④B1に「=RANK(A1,$A$1:$A$100,0)」を入力

RANK関数はRANK(数値,参照範囲,順序)で入力すると、[数値]が[参照範囲]の中で[順序]で何番目かを返す。[順序]は0か1を入力でき、0ならば降順（大きい数字の方が順位が高い）、1ならば昇順（小さい数字の方が順位が高い）である。

あとでこの式をコピーするので、[数値]は相対参照、[参照範囲]は絶対参照(「＄」をつける)にしておく。

⑤B100までコピーする

これで、A1からA100に書いてある数字の順位がB1からB100に表示される。乱数の順番を表示させているので、重複を避けることができる。

2017-01-20

証明を書いていたら循環論法になってしまいましたよという話

数学証明

簡単なはずの証明問題にやたら時間がかかっていたことの弁明をしたいと思います(弁明にはならない)。

今日の夕方に投稿した記事の証明問題の話です。

「aのn乗がpの倍数であること」と「aがpの倍数であること」は同値である - 足跡-sokuseki-

これの⑵の証明の際に、対偶を帰納法ではなくそのまま証明できないかと奮闘していました。

以下がその証明部分です。

『 $a^n$ が $p$ の倍数 $\Longrightarrow a$ が $p$ の倍数』を示すために、その対偶である

『 $a$ が $p$ の倍数でない $\Longrightarrow a^n$ が $p$ の倍数でない』を示すことにします。

$t,q$ を正の整数として、 $a=pt+q$ とおきます。

ただし、 $q$ については $0 < q < p$ とします。

このとき

$a^n = (pt+q)^n$

となりますが、ここで二項定理を使います。二項定理は

$(x+y)^n = \sum_{k=0}^{n} {}_n C _{k} x^k y^{n-k}$

というものです。これを利用すると

$(pt+q)^n = \sum_{k=0}^{n} {}_n C _{k} (pt)^k q^{n-k} = \sum_{k=1}^{n} {}_n C _{k} p^k t^k q^{n-k} + q^n$

となります。ここで、 $k>0$ のとき ${}_n C _{k} p^k t^k q^{n-k}$ は $p$ の倍数であり、