AtCoder Beginner Contest 107 - seriruの技術屋ブログ

先週行われたAtCoder Beginner Contest 107 の考察と解説です。解けたところまで解説します。

A Train

答えは、 $N - i + 1$ になります。
もしピンとこなかったら図を描いて見てください。

sample code:

実装が重いB問題です。

最初に制約に着目すると、

$1 \leq H, W \leq 100$

とあるので、最大でもマス目は 10⁴ 個になります。
従って、全ての行と列をチェックしても制限時間には間に合いそうです。

次にチェックの仕方を考えます。

様々な方法が考えられますが、私は行列と同じ大きさの配列を用意し、条件を満たした場合フラグを立てるという方法で解答しました。

1つ気をつけなければならないのは、対象の行、列が全て'#'の場合です。
この場合は条件を満たさないので削除する必要がありません。

sample code:

(サンプルではフラグ管理にvectorを利用しています)

数直線上に置かれた $N$ 本のろうそくから $K$ 本に火をつけるときの最短移動距離を求めよ、という問題です。

求め方を考えて見ましょう

n C k個の組み合わせを全て試すのは、 $1 \leq N \leq 10^{5}$ という制約より不可能です。

そのため別の方法を考える必要があります。

単純に考えれば選ぶのは原点から近いろうそくです。
また、選ぶろうそくの間を開けるのは明らかに非効率です。

以上のことからこの問題は、

原点を含む連続したK本のろうそくの選び方のうち、一番短いものはどれか

という問題に読み替えることができます。

連続するK本のうち、正の方向のろうそくがm本あるとき、負の方向のろうそくはK-m本になります。

f:id:ryo_seriru:20180903185010p:plain

これを $0 \leq m \leq K$ について試すことで他の無駄な計算をせずに、1回のループで答えを求めることができます。

ただし、方向転換するときに今まで来た道をもう1回辿らなければならないので、正と負の方向で移動する距離が小さいほうを2倍する必要があります。

実装ですが、正と負の入力を別の配列で管理します。
入力が原点からの距離になっているので、要素 $m-1$ と $K-m-1$ を参照すれば簡単に距離の総和が求まります。

sample code:

Dはまだ無理です＞＜