簡単な説明

主に競技プログラミングの問題について、自分のコードの記録などの記事を掲載していきます。「問題概要」「解答・解説」「自分の思考過程のメモ」あたりをベースに記事を書いていきます。

ARC080 D - Grid Coloring

問題

HWのグリッドに色1〜Nのマスがある。各々a_i個ずつ存在し、\sum_{i=1}^{N}a_i = HWである。 同じ色同士のマスは上下左右の移動のみによって、他の色のマスを踏まずに任意のマス到達できなければならない。 そのような塗り分け方を一つ出力せよ。

解法

1行しか存在しない場合、小さい番号の色から順にマスを埋めていけば良い。 グリッドの場合においても、うなぎ上に折り返していけば1行と同等に考えることが出来る。

>------------->v
v<-------------<
>------------->v
...

こんな感じに進めば良い。 例えば、以下のような出力になる。

122333444455
777666666555
7777...

ARC080 - C: 4-adjacent

問題

正の整数列が与えられる。数列を並び替えて隣り合う値を全て4の倍数にすることは出来るか


解答

数列の値について、興味あるのは2の因数の数のみである。 また、2の因数が2つ以上ある場合は、両隣の値に対して2の因数が2つの場合と同等なので、 値の状態は2の因数が0, 1, 2個の3つのうち何れかとなる。順に、(0)(1)(2)の値と表現する。

(0)の値は、隣接する値が(2)であるような制約の厳しい値であるので、(0)の扱いから考える。 はじめに(0)を置いた時、次に(2)を置くしかない。(0)をできるだけ消費してしまいたいので、これを繰り返すと以下のようなケースが考えられる。

  1. (0)(2)(0)(2)…(0)
  2. (0)(2)(0)(2)…(2)

1のケースは、(0)(2)を繰り返した結果末尾が(0)で終わるものである。このとき(1)は0個である必要がある。 2のケースは、(0)より(2)の数のほうが多かった場合である。この場合末尾の(2)の後に、任意回数(1)または(2)を置いて良い。(1)は(1)または(2)を両隣に置くことが出来るからである。

よって、以下の3パターンが答えとなる。

  1. (0)(2)(0)(2)…(0) -> Yes
  2. (0)(2)(0)(2)…(2) + 末尾に(1)または(2)が並ぶ -> Yes
  3. それ以外 -> No

AGC 012 - A: AtCoder Group Contest

問題

agc012.contest.atcoder.jp

続きを読む

AOJ2709 Dark Room

問題

N個の部屋があり、そのうちM個が暗い部屋である。 各部屋には[tex1]〜Kに番号付けされたドアがある。 順に進むべきドアの番号を指示する列を与える。一度明るい部屋に到達したら、その続きの指示は無視される。 部屋のどこからスタートしても明るい部屋に到達できるようにしたい。 ドアの列の最小の長さを求めよ。

  • 2 \le N \le 100
  •  1 \le M \le min(16, N - 1)
  •  1 \le K \le N
続きを読む

AGC005 A - STring

問題

'S'と'T'からなる文字列Xがある。文字列のうち左から"ST"があればそれを繰り返し削除する。最後に残る文字数を答えよ。

  • 2\le |X| \le 200000
続きを読む

AGC007 A - Shik and Stone

問題

グリッドを左上から右下まで移動した。移動したマスは'#'であり、そうでないマスは'.'である。何度も同じ場所を行き来することもある。右または下にだけ移動した可能性のある場合は"Possible"、そうでない場合は"Impossible"を出力せよ。

続きを読む