AtCoder C問題(051,065,066,067,078)

C問題５問解いたのでまとめです。

C - Back and Forth
C - Reconciled?
- 問題概要
- 考察
- 解答例
- 反省
C - pushpush
C - Splitting Pile
C - HSI

C - Back and Forth

問題概要

イルカが $(sx,sy)$ と $(tx,ty)$ を２往復する。最短の経路を求めよ。ただし、同じ座標は通ってはいけない。

考察

なにはともあれお絵描きします。

f:id:guitarjoepass:20180628154956p:plain

黄色は、左下に(sx,sy)右上に(tx,ty)があり、縦の長さ(ty-sy)横の長さ(sx-sy)の長方形で、青色はその長方形の上下左右１ずづ広げたものです。黄色内（辺を含む）を通れば、目的地の逆の方向に進まない限り（例えばSからTに行きたいのに左に行くなど）最短経路になります。ただし、同じ座標を２度通らない経路は往復１回分しかありません。従って２回目は青色の長方形の範囲を通ることになります。

解答例

gist.github.com

（絵に書いたようなクソコード）

もう少し考察

上の考察が雑すぎたので、もう少しちゃんと考えていこうと思います。問題解いたときは上の考察だったので残しておきます。

問題のイメージを変えます。点Sと点Tが伸び縮みができる４本の紐で繋がってるものとして考えます。点Sと点Tの置く場所は決まっています。紐同士を交差させずに、紐の長さを最短になるように、格子にはめて行きましょう。というイメージで考えます。

上記のようなイメージを持つと、点Sのある方向からでた紐は、点Tへ到着する方向は必ず一つに決まりまることがわかります（例えば、点Sの右側からでた紐は必ず点Tの下から到着しなければなりません、そうしないと紐が絡まります）。

以下S→Tに行く２パターンの時のことを考えます。T→Sは、右を左に、上を下に、それぞれ読み替えてください。

必ずSから見てTは、右上にあるので、右に進む、上に進む以外の動作はなるべくしたくありません。しかし、どうしてもしなくては行けない部分があります。先ほどの議論を思い出すと、点Sから右に出た紐は、必ず点Tの下にくっつきます。これと同様に、点Sの下からでた紐は、必ず点Tの左にくっつかねばなりません。この際、進行方向とは逆の方向に２回進まなければなりません。

このような議論を繰り返すと、２往復で合計４マス分進行方向とは逆に進まなければ行けないことがわかります。それ未満では条件を達成できませんし、それより大きいのは経路の無駄です。

反省

順番にやれと言われてる問題は、全部やってから無駄を省くというのは典型では？(exC - ハイスコア)

格子なり座標なりブロックなり、型にはめろって言われてる問題は、型を無視して見るのも典型では？（exC - Chocolate Bar）

C - Reconciled?

問題概要

犬N匹と、猿M匹が必ず隣り合うような並び方は何通りあるか?

制約 $1≦N,M≦10^5$

考察

はじめに犬を並べます。そうすると、犬と犬の間はn-1出来ます。最低でもここに猿が入って貰わないと、犬同士が隣り合ってします。また、猿は、一番右もしくは左の犬の隣にも並べられます。それ以上並ぶと、今度は猿が隣り合ってしまいます。従って、

$N - 1 ≦ M ≦ N + 1$

⇨ $|M - N| ≦１$

⇨ $|M - N| = {0,1}$

が成り立たないならば、条件を満たす並び方は存在しないので、答えは０です。

また、上記の条件を満たすならば、犬の並べ方はN!通り、猿の並べ方はM!通りなので、 $N!*M!$ 通り並べ方がありますが、 $|M - N| = 0$ の時、犬と猿を反転した並び方ができるので、並べ方の数は２倍となります。まとめると

$|M - N| ≧ 2 ならば 0通り$

$|M - N| = 1 ならば M!*N!通り$

$|M - N| = 0 ならば 2*M!*N!通り$

が答えとなります。

解答例

gist.github.com

int と long long int の掛け算ってダメなんでしょうか？謎な挙動をよく示す気がします...。

反省

２種類並べろは１種類先に全部並べる(ex:A - Happy Birthday!)

C - pushpush

問題概要

長さnの数列 $a$ と空の数列 $b$ があり、以下の操作をi=1からi=Nまで繰り返します。

１. $a[i$ ]をbの末尾に加え、 $b$ を逆向きに並びかえる。

N回の操作終了後、 $b$ を求めなさい。

制約 $1 ≦ n ≦ 2 * 10^5$

考察

制約にシュミレーションがきつそうな気がした。

実験すると後ろからaを１個飛ばしに出力して、残りを前から出力すれば良いことがわかる。

ただ、実装方法思いつかない。

上に書いたようにやるとnの偶奇で分けなくちゃならない。めんどくさい。

ということで、出力したものは消して行くことにしました。

解答例

gist.github.com

dequeなるものと使うとシュミレーションできるのかな。

C - Splitting Pile

問題概要

要素数 $N$ の数列があり、 $1$ から $i$ 番目までの和を $x$ 、 $i+1$ から $N$ 番目までの和を $y$ とする。 $|x-y$ |の最小値を求めよ。

考察

見た目が累積和！！からバグらせたつらい。

自分的累積和まとめ

数列の部分和を高速に取り出す方法。

a[0]=b[0]

b[i]=b[i-1]+a[i]

i番目からj番目までの和は

b[j]-b[i-1]

解答例

gist.github.com

C - HSI

問題概要

プログラミングコンテストに出ている高橋くんは、１回目の提出でNケース中MケースでTLEしました。そこでMケースでは1900msかかり、 $1/2$ の確率で正解し、残りのN-Mケースでは100msで必ず正解しするプログラムに書き換えました。高橋くんが全てのケースを正解するのにかかる時間の期待値を求めなさい。