足跡-sokuseki-

りかの日進月歩の記録

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が取れずにずっと悩んでいた

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はありそうだと思った)

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

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

以下その方法。

 

①エクセルを起動させる

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

 

②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-


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

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

『 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 の倍数であり、

p の倍数を足し合わせたものである \sum_{k=1}^{n} {}_n C _{k} p^k t^k q^{n-k} も

p の倍数になります。

また、 0 < q < p より、 q は p の倍数ではないので、

q^n も p の倍数ではありません。

よって、 a^n = (pt+q)^n は p の倍数ではありません。

以上より、対偶を示すことができたので、十分条件が成り立つことがわかりました。

色を変えたところが循環論法になっています。

これをどうしようか……と悩んでいて時間が経ってしまったわけです。

なお、当該記事では帰納法を使っていますが、これは、どうしてもうまくいかなくて、数学の先生に

「『 a が p の倍数でない \Longrightarrow a^n が p の倍数でない』はどうやって示せばいいですか」

と質問したところ、帰納法を使えばいいよというアドバイスをいただいたので、帰納法でやってみた次第です。

私が自力で思いついたわけではないです。はい。

(帰納法ということを教えてもらっただけで中身の証明は自分で考えたのですが、そのせいで無駄に長い証明になってしまいました……)

なお、さきほど短いver.を追記しました。


以上、弁明にもならない弁解でした。

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

数学 証明

根号のついた様々な数が無理数であることを示すのが最近の趣味です。
その証明に使う補題(のようなもの)を証明したいと思います。

証明内容はタイトルにも書いた通り、

『 a,n が正の整数、 p が素数のとき、

a^n が p の倍数 \Longleftrightarrow a が p の倍数 』

です。必要条件と十分条件に分けて証明していきたいと思います。


⑴『 a^n が p の倍数 \Longleftarrow a が p の倍数 』を示す

t を整数として、 a=pt とおきます。このとき

a^n = (pt)^n = p^n t^n

p^n t^n は p の倍数なので、 a^n が p の倍数であることがわかります。


よって必要条件は示すことができました。





⑵『 a^n が p の倍数 \Longrightarrow a が p の倍数 』を示す

これを直接証明することは難しいので、対偶を示すことにします。

『 a^n が p の倍数 \Longrightarrow a が p の倍数 』の対偶は

『 a が p の倍数でない \Longrightarrow a^n が p の倍数でない 』……(＊) です。

なので、(＊)を数学的帰納法を使って示します。



(i) まずは n=1 のとき

「 a が p の倍数でないならば a が p の倍数でない 」は自明なので(＊)は成り立ちます。



(ii) 次に、 n=k のときに(＊)が成り立つと仮定します。

このとき仮定より、「 a が p の倍数でないならば、 a^k が p の倍数でない」といえます。

またこのとき、

「 p の倍数でない数に、 p の倍数でない数をかけても p の倍数にはならない 」……(A)

ということがいえるならば、

p の倍数でない a^k に、 p の倍数でない a をかけた a^{k+1} も p の倍数ではありません。

よって(A)さえ示すことができれば、 n=k+1 のときも(＊)が成り立つといえます。



ここで(A)を示すために、 p の倍数でない2数の積を p で割ったあまりについて考えます。

(ここでは合同式を使って、整数 a を整数 p で割ったあまりと、整数 b を整数 p で割ったあまりが等しいとき
「 a \equiv b ( mod p ) 」と表すことにします。 )

整数 a, b, c, d を用いて、 p の倍数でない2数を

ap+b、 cp+d 　　(ただし、 0 \leq a, c かつ 0 < b, d < p )

とします。

この2数の積を p で割ったあまりは

(ap+b)(cp+d) \equiv acp^2 + ( ad+bc ) p + bd \equiv bd 　 ( mod p )

と表せます。


ここで、「 bd \equiv 0 　( mod p ) 」と仮定すると、

bd は p の倍数であり、 p は素数なので、

b と d の少なくとも片方が「 0 または p の倍数」である必要があります。

しかし、 0 < b, d < p より、

b と d の両方ともが 0 でも p の倍数でもないので、これは矛盾します。

よって 「 bd \equiv 0 　( mod p ) 」という仮定が間違っていることがわかります。


以上より bd \not\equiv 0 　( mod p ) となります。

よって、 (ap+b)(cp+d) \not\equiv 0 　( mod p ) となり、

p の倍数でない2数の積は p の倍数でないことが示せました。(A)の証明はこれで終了です。



これで、

(i) n=1 のとき(＊)が成り立つ

(ii) n=k のときに(＊)が成り立つならば、 n=k+1 のときに(＊)が成り立つ

を示すことができたので、数学的帰納法より(＊)を証明することができました。



対偶である(＊)を証明することができたので、

『 a^n が p の倍数 \Longrightarrow a が p の倍数 』が成り立つことが証明できたことになります。





よって、必要条件、十分条件ともに成り立つことがわかったので、

『 a,n が正の整数、 p が素数のとき、 a^n が p の倍数 \Longleftrightarrow a が p の倍数 』

を証明することができました。





ところでこの証明、名前ついてたりするんですかね……。有名な気がするんですが……。


参考サイト

合同式の意味とよく使う６つの性質 | 高校数学の美しい物語





追記

この記事を投稿した後に、@lvbourbakiさんに指摘していただいて気づいたのですが、(A)の証明の部分で合同式を使って式変形をする必要はありませんでした。
ということで、簡潔になった(A)の証明を以下に書きます。



p の倍数でない2つの自然数を a, b とします。

ここで、「 ab が p の倍数である 」と仮定すると、 p は素数なので、

a と b の少なくとも片方が「 0 または p の倍数」である必要があります。

しかし、 a と b の両方ともが 0 でも p の倍数でもないので、これは矛盾します。

よって 「 ab が p の倍数である 」という仮定が間違っていることがわかります。


以上より ab は p の倍数でないということがいえるので、

p の倍数でない2数の積は p の倍数でないことが示せました。

じ、自明だ……

ということで随分と短くなりました。

@lvbourbakiさん、どうもありがとうございました。

競技プログラミング2016総括

競技プログラミング

ということで競技プログラミング1年目のまとめをします。長くて面倒なので箇条書きスタイルでいきます。

 

4月

 

5月

  • RiPProに正式入部
  • AtCoder初AC
  • AtCoderのコンテストに初出場(ABC038)

 

6月

  • 1年3人でチームを組んでICPC国内予選に出る(1完)

 

7月

  •  大学の期末テストで競プロできない日々が続く

 

8月

  • 夏休みだったので毎日AOJを目標にしてた(できたとは言ってない)

 

9月

  • ACPCに参加(初めてのオンサイトコンテスト&&初めての作問)
  • AtCoderで100solved達成！

 

10月

  •  KUPCに参加
  • AOJで100solved達成！
  • AtCoderのレートが1200突破！

 

11月

  • 何してたっけ……？

 

12月

  • 毎日AtCoderを目標にしていた
  • AtCoderで200solved達成！
  • Codefoces初AC

 

 

現在のAC状況(2016/12/30 17:00現在)

 

AOJ……133solved 

 

f:id:wk1080id:20161230165028p:plain

 (解いてるときと解いてないときの差が激しい)

 

AOJ-ICPC……47solved

 

f:id:wk1080id:20161230162354p:plain

 

 

AtCoder……253solved

 

f:id:wk1080id:20161230164102p:plain

(ABCのAB埋めが完了したので解ける問題が少なくなって進捗がなくなってきた)

 

f:id:wk1080id:20161230163753p:plain

 

 

 

最後に……

 

来年も競技プログラミング頑張ります！

たくさんのオンサイトコンテストに行けるといいな〜

 

 

 

今までに詠んだ和歌をまとめた

数学 和歌

 

和歌。それは少ない文字数に景色や心情を詠みこむ日本独自の歌。決まった文字数に様々な、時には二通りにも三通りにも読み取れる意味を込める和歌は、とても素晴らしい文化だと思います。

和歌を詠んだ経験は少ないのですが、イベントに関連してTwitterで和歌を募集していた際などに詠んだいろいろな和歌を一度まとめます。

 

愛と数学の短歌コンテスト

 

4月に理系彼女botさんが考案、横山明日希さん（数学のお兄さん）が主催して行われたコンテスト。

 

短歌も和歌の一種ということで。技法とか何もないのが多いですが。 

 

これは@mass_sawood さんのツイートが元ネタ。すべてローマ字にすると "I love U" になります。

 

 

ロマンティック数学俳句コンテスト

 

7月から8月にかけて、横山明日希さん（数学のお兄さん）主催で行われたコンテスト。

 

このコンテストについては、ツイートしてないのですが、スマホのメモに当時考えたものが残っていたので。 

関数で 君は一意に 僕とペア

「関数はある数を決めるとそれに対応して一つの数が決まる。関数のように、君と僕が一対一で対応する、っていうニュアンス」という解説まで残っていました(笑)

 

 

数学和歌を詠もう

 

8月末から、横山明日希さん（数学のお兄さん）と狡猾な狐さんが企画して行われたイベント。

 イベントまでに詠むことはできなかったのですが、その後行われたツイキャスで詠みました。

 

 

 そしてセルフ解説はこちら。

 

そしてこのハッシュタグを使って、その後もいくつかツイートしてます。

 これはただのネタです(笑)

 

 

古今和歌集の日

 

2016年11月11日の古今和歌集の日を記念して和歌を詠もうという企画（狡猾な狐さん発案）。

 

 これについてはセルフ解説を以下に。

 

 いくつかツイキャスで紹介もしていただいて、本当にありがとうございました！

 

最後に

 

古今和歌集からの良き節目を迎えて、せっかくだから、と今までの分もまとめました。もっと良い和歌を詠めるようになりたいです。