ABC054 D Mixing Experiment
頑張って実装したので記事にするぞ。最近更新頻度高いし競プロ頑張ってる感がある*1。
D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder
問題概要
N種類の薬品のうちいくつかの薬品を購入する。薬品iにはタイプAの物質を グラム、タイプBの物質を グラム含んでおり、価格 円で売られている。
タイプAの物質とタイプBの物質の混合比が となるのに必要な最小予算を求めよ。
制約
DP解法1
求めるものは「物質の重さの比が となるのに必要な最小予算」なので、購入するそれぞれの物質の重さが最終的にわかればよい。よって、
dp[i][j][k]:=薬品 i まで見たときに、購入するタイプAの物質が合計 j グラム、タイプBの物質が合計 k グラムとなる最小費用
という配列をつくる。
j : k = となるdp[n][j][k]の最小値が求める最小費用。
計算量は。
Submission #1123367 - AtCoder Beginner Contest 054 | AtCoder
DP解法2
さっきのDP解法よりさらに計算量を落とすことができる。
(タイプAの物質の合計の重さ):(タイプBの物質の合計の重さ)=:
となれば良いので、
(タイプAの物質の合計の重さ) * - (タイプBの物質の合計の重さ) * = 0
となる最小費用をもとめればよい。よって、
dp[i][j]:=薬品 i まで見たときに、「購入するタイプAの物質の合計の重さと の積」と「購入するタイプBの物質の合計の重さと の積」の差が j のときの最小費用
という配列を作り、dp[n][0]が答えとなる(ただし、このままだとjは負の値をとることがあるので、jの値はずらす必要がある)。
計算量は *2。
Submission #1121081 - AtCoder Beginner Contest 054 | AtCoder
DP解法3
もう一つ別の解法があるのを見つけたので紹介だけ(参考サイト:ABC054-D「Mixing Experiment」 | クリエイティヴなヴログ)。
計算量はさっきのDP解法2と変わらないけど、やりかたが違う。
各薬品 i について、
d[i]:= * - *
を最初に求めておく。そのあと、
①d[i]=0となる の最小値を求める
②d[i]<0となるものとd[i]>0となるものをいくつか選び、和が0になるものの最小予算を求める(ここでDPを使う)
①と②のうち小さいほうが答えとなる(詳しい解き方はリンク先をみてください)。
半分全列挙
半分全列挙は昔に一度だけやったことがあるけど*3、復習しないので覚えてなかった(ので昔のコードを見ながら思い出しつつやった)。
半分全列挙は、まず半分にわけて、それぞれでありえる組み合わせを全列挙して、うまくmergeして答えを求める方法。名前そのまま。
計算量は、半分にわけて全列挙するところが で、mergeするところが なので全体で *4。
Submission #1128677 - AtCoder Beginner Contest 054 | AtCoder
感想
コンテスト中に通したかった……(そもそも全探でしようとしてたのでダメ)
ひとつの問題でいろいろな解き方ができるのは本当におもしろいし楽しいなあ。
同じ問題をずっと解いてるからsolvedが増えない><
— リサさんになりたいbot (@wk1080id) 2017年2月19日
でもいろいろな解法で考察することで実力がつくと信じてる!
*1:と書き始めた当初は思っていたが、記事が完成するのに1週間近くかかったのでダメ
*2:配列の大きさで考えると になる
*3:C: 無駄なものが嫌いな人 - AtCoder Regular Contest 017 | AtCoder
*4:この書き方だと某警察につかまりそう。 が正しいのだと思うけど、それではでうまくいくことがわからないし…。
ABC054 C One-stroke Path
頑張って実装したやつは記事にしようという試み。
C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder
問題概要
自己ループと二重辺を含まないN頂点M辺の重み無し無向グラフが与えられるので、頂点1を始点として、全ての頂点を1度だけ訪れるパスは何通りあるかを求める。
制約
再帰を使った解法
コンテスト中に解いた解法はこれ。とりあえず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頂点の並べ替えと隣り合う頂点間に辺が張られているかそれぞれ調べるので、計算量は 。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を自作してみてね!と言っていたけど私には無理だった。
ABC013 C 節制
先日 AtCoder Virtual Contest でやっていたABCのC埋めに出てきて、コンテスト中には解けなかったのでゆっくり解いていたが、満点解法がわからなかった&&時間がかかったので書く。
C: 節制 - AtCoder Beginner Contest 013 | AtCoder
問題概要
N日間の食事を次の3つから選ぶ。
・普通の食事 ( 出費A円、満腹度 +B )
・質素な食事 ( 出費C円、満腹度 +D )
・食事抜き ( 出費なし、満腹度 -E )
最初の満腹度がHで、一度も満腹度が0以下にならないとき、最低何円でN日間乗り切れるか。
制約
部分点
10点…… を満たすテストケース
40点…… を満たすテストケース
100点…… を満たすテストケース
101点…… すべてのテストケース
部分点解法その1
の解法。問題を見た時にまずこれが浮かんだ。
日にちと満足度が決まればそのときの最小の食費は一意に定まるので、
dp[i][j]:=i日目に満足度がjであるときにかかる最小の食費
という配列をもつDPで解ける。
満足度の上限はH+NBより
計算量は つまり 。
部分点解法その2
の解法。DPが思いついたあと、100点解法では満足度の上限がないため、満足度を使わずに食費が一意に定まるものは他にないかと考えて、「それぞれの食事をした回数が決まれば、満足度も食費も求めることができる!」と気づいた。
普通の食事の日数と質素な食事の日数が決まれば、食事抜きの日は「 n - (普通の食事の日数) - (質素な食事の日数) 」に決まるから、計算量は 。
Submission #1111965 - AtCoder Beginner Contest 013 | AtCoder
普通の食事の日数をi日、質素な食事の日数をj日とすると、食事を抜く日数はn-i-j日である。
このとき、n日目の満足度は「 」であるから、これが0より大きければ満足度が一度も0以下になることがないような食事の順番が存在する*1。よって、このときの合計の食費「 」が今までの暫定の最小の食費よりも小さければ暫定値を更新する。
満点解法
の解法。思いつかなかったので解説を見たら頭が良かった(それはそう)。
制約より、満腹度が大きくなるほど合計の食費も大きくなるので、合計の食費をできるだけ小さくするには満腹度が(一度も0以下にならないという制約を満たしつつ)できるだけ小さくなるようにすればいい。
つまり、普通の食事の日数をi日、質素な食事の日数をj日、食事を抜く日数はn-i-j日としたとき、 を満たすようなiとjのうち、iとjが最小になるものを考える。
2変数であるから、計算しやすいように片方の変数iを固定して考える*2。
iを固定したとき
となる最小の整数jは で求まる。
これを についてそれぞれ調べるので、全体の計算量は 。
Submission #1112041 - AtCoder Beginner Contest 013 | AtCoder
普通の食事の日数がi日のとき、質素な食事の日数が0日かそうでないかで場合分けをする*3。
のときは質素な食事の日数が0日で良いため、合計の食費は となる。
のときは、最小となるjを求めて、 のとき(普通の食事の日数と質素な食事の日数の合計がn日以下のとき)は、合計の食費は となる。 合計がn日より大きい場合は、なかったことにする。
感想
ABCのCなのに難しい問題が多くてつらい(人権がない)
AGC005 B Minimum Sum
昨日解いていて、解説を見ても理解するのに手こずったので、考え方を書いてみる(一応この問題について書いてるブログはあったけど、解法が違ったので、自分用に)。
B: Minimum Sum - AtCoder Grand Contest 005 | AtCoder
TLE解法
自力で思いついたのは全区間の最小値を順番に足していく の解法。
調べる区間の幅をだんだん大きくしていくという考え方。
Submission #1101992 - AtCoder Grand Contest 005 | AtCoder
ansの初期値に代入している は、隣り合う1項の最小値(つまりその項自身)の合計値。数列には から までの数がそれぞれ1回ずつ出てきているので、等差数列の和と考えて計算する。
repの中では、隣り合う 項の最小値を計算してansに足していく。
区間(部分数列)でいうと
{} {} … {}
{} {} … {}
…
{} {}
{}
の最小値を順番に求めている。
setを使った解法
の解法は「最小値が となる区間がいくつあるかを計算し、その区間数と の積の合計を求める」。
が最小値となる区間は、数列の より前の部分で に一番近いところにある よりも小さな値との距離、数列の より後ろの部分で に一番近いところにある よりも小さな値との距離がわかれば求めることができる。
たとえば、{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個と求めることができる。
今見ている数字 が最小値となる区間の数を求めるためには、 の左右それぞれで、より小さく に一番近い数との距離が必要になる。 よって、要素を自動的にsortしてくれるsetに、 より小さな値の添字を入れておき、 の添字iに一番近い数をlower_boundを使って高速に調べればよい。
が最小値となる区間を調べる際に必要な情報は「 よりも小さな値がどこにあるのか」なので、できるだけ小さな 、つまり1から順番に調べていくと、区間数を調べた後にsetにをそのまま入れることができるので、効率よく求めることができる。
setの要素の挿入に 、set内のlower_boundに かかるので、それぞれに対して行っても 。
Submission #1102173 - AtCoder Grand Contest 005 | AtCoder
入力を配列aで受け取り、配列orderには、区間数を調べる の順番になるように、 の添字iを格納する。つまり、a[order[0]]=1, a[order[1]]=2, … , a[order[N-1]]=Nとなるように格納する。
はじめにsetに入れた-1とNは番兵の役割をする。の前に より小さな値が存在しないときは-1が返され、の後ろに より小さな値が存在しないときはNが返される。
その他の解法
pekempeyさんがUnion-Findを使った解法を解説しています。
AtCoder Grand Contest 005: B. Minimum Sum - pekempeyのブログ
また、standingsで他の人のソースコードを見てみると、stackを使った解法などもあるようです(私にはよくわからなかったのですが……)。
最後に
この問題が400点なんて嘘ですよね?(500はありそうだと思った)
エクセルでの乱数発生のメモ
この春休みは計算力を上げることを目標として頑張っているので、さまざまなことに取り組んでいる。その一環として使うプリントを作成した。その際の「1から100までの整数をランダムに(重複なしで)表示させる方法」をメモしておく。難しくはなく、簡単にできるので大量にプリントを作ることができた。
以下その方法。
①エクセルを起動させる
ここは気合いでなんとかなる。
②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に表示される。乱数の順番を表示させているので、重複を避けることができる。
証明を書いていたら循環論法になってしまいましたよという話
簡単なはずの証明問題にやたら時間がかかっていたことの弁明をしたいと思います(弁明にはならない)。
今日の夕方に投稿した記事の証明問題の話です。
「aのn乗がpの倍数であること」と「aがpの倍数であること」は同値である - 足跡-sokuseki-
これの⑵の証明の際に、対偶を帰納法ではなくそのまま証明できないかと奮闘していました。
以下がその証明部分です。
『 が の倍数 が の倍数 』を示すために、その対偶である
『 が の倍数でない が の倍数でない 』を示すことにします。
を正の整数として、 とおきます。
ただし、については とします。
このとき
となりますが、ここで二項定理を使います。二項定理は
というものです。これを利用すると
となります。ここで、 のとき は の倍数であり、
の倍数を足し合わせたものである も
の倍数になります。
また、 より、 は の倍数ではないので、
もの倍数ではありません。
よって、はの倍数ではありません。
以上より、対偶を示すことができたので、十分条件が成り立つことがわかりました。
色を変えたところが循環論法になっています。
これをどうしようか……と悩んでいて時間が経ってしまったわけです。
なお、当該記事では帰納法を使っていますが、これは、どうしてもうまくいかなくて、数学の先生に
「『 が の倍数でない が の倍数でない』はどうやって示せばいいですか」
と質問したところ、帰納法を使えばいいよというアドバイスをいただいたので、帰納法でやってみた次第です。
私が自力で思いついたわけではないです。はい。
(帰納法ということを教えてもらっただけで中身の証明は自分で考えたのですが、そのせいで無駄に長い証明になってしまいました……)
なお、さきほど短いver.を追記しました。
以上、弁明にもならない弁解でした。
「aのn乗がpの倍数であること」と「aがpの倍数であること」は同値である
根号のついた様々な数が無理数であることを示すのが最近の趣味です。
その証明に使う補題(のようなもの)を証明したいと思います。
証明内容はタイトルにも書いた通り、
『 が正の整数、 が素数のとき、
が の倍数 が の倍数 』
です。必要条件と十分条件に分けて証明していきたいと思います。
⑴『 が の倍数 が の倍数 』を示す
を整数として、 とおきます。このとき
は の倍数なので、 が の倍数であることがわかります。
よって必要条件は示すことができました。
⑵『 が の倍数 が の倍数 』を示す
これを直接証明することは難しいので、対偶を示すことにします。
『 が の倍数 が の倍数 』の対偶は
『 が の倍数でない が の倍数でない 』……(*) です。
なので、(*)を数学的帰納法を使って示します。
(i) まずは のとき
「 が の倍数でないならば が の倍数でない 」は自明なので(*)は成り立ちます。
(ii) 次に、 のときに(*)が成り立つと仮定します。
このとき仮定より、「 が の倍数でないならば、 が の倍数でない」といえます。
またこのとき、
「 の倍数でない数に、 の倍数でない数をかけても の倍数にはならない 」……(A)
ということがいえるならば、
の倍数でない に、 の倍数でない をかけた も の倍数ではありません。
よって(A)さえ示すことができれば、 のときも(*)が成り立つといえます。
ここで(A)を示すために、 の倍数でない2数の積を で割ったあまりについて考えます。
(ここでは合同式を使って、整数 を整数 で割ったあまりと、整数 を整数 で割ったあまりが等しいとき
「 ( mod ) 」と表すことにします。 )
整数 を用いて、 の倍数でない2数を
、 (ただし、 かつ )
とします。
この2数の積を で割ったあまりは
( mod )
と表せます。
ここで、「 ( mod ) 」と仮定すると、
は の倍数であり、 は素数なので、
と の少なくとも片方が「 0 または の倍数」である必要があります。
しかし、 より、
と の両方ともが 0 でも の倍数でもないので、これは矛盾します。
よって 「 ( mod ) 」という仮定が間違っていることがわかります。
以上より ( mod ) となります。
よって、 ( mod ) となり、
の倍数でない2数の積は の倍数でないことが示せました。(A)の証明はこれで終了です。
これで、
(i) のとき(*)が成り立つ
(ii) のときに(*)が成り立つならば、 のときに(*)が成り立つ
を示すことができたので、数学的帰納法より(*)を証明することができました。
対偶である(*)を証明することができたので、
『 が の倍数 が の倍数 』が成り立つことが証明できたことになります。
よって、必要条件、十分条件ともに成り立つことがわかったので、
『 が正の整数、 が素数のとき、 が の倍数 が の倍数 』
を証明することができました。
ところでこの証明、名前ついてたりするんですかね……。有名な気がするんですが……。
参考サイト
追記
この記事を投稿した後に、@lvbourbakiさんに指摘していただいて気づいたのですが、(A)の証明の部分で合同式を使って式変形をする必要はありませんでした。
ということで、簡潔になった(A)の証明を以下に書きます。
の倍数でない2つの自然数を とします。
ここで、「 が の倍数である 」と仮定すると、 は素数なので、
と の少なくとも片方が「 0 または の倍数」である必要があります。
しかし、 と の両方ともが 0 でも の倍数でもないので、これは矛盾します。
よって 「 が の倍数である 」という仮定が間違っていることがわかります。
以上より は の倍数でないということがいえるので、
の倍数でない2数の積は の倍数でないことが示せました。
じ、自明だ……
ということで随分と短くなりました。
@lvbourbakiさん、どうもありがとうございました。