たれながし

色々雑多に書きます

緑diff精進その2 (1/24)

解いた問題

ABC260 D -Draw Your Cards
ABC075 C - Bridge
ABC191 C - Digital Graffiti
ABC166 E - This Message Will Self-Destruct in 5s
ABC194 D - Journey
CodeFestival 2016 qual A C - Next letter

ABC260 D -Draw Your Cards

感想 (解答中に考えたこと)

愚直にシミュレーションする問題っぽい。場を表す配列を容易したとして、何も考えずに実装すると $O(N^2)$ で間に合わない。
要求されるデータ構造は、場に見えるカードの数を管理していて、ある数 $X$ 以上で最小の数を $O(N)$ よりも速く見つけられるようできるもの。
後者の条件は二分探索でいけそう。つまり、SortedListで場に見えるカードの種類を管理し、実際の束はHashMapで管理するとうまくいきそう。
二分探索はSortedListのbisect_leftを利用する。これによって $O(N\log{N})$ で解ける。
実装したがTLE。というのもhashmap[key] = hashmap[otherkey] + [new_value]としたところが遅いようだった。hashmap[key] = hashmap[otherkey]の後にhashmap[key].append(new_value)をするとACした。
- 以下のように初期化と一緒にappendっぽいことをしようとすると参照渡しじゃなくなる。まぁhashmap[0] + [7]で新しいリストに変わってるのは確かに納得。

hashmapのid変化の確認

提出コード

ABC075 C - Bridge

感想 (解答中に考えたこと)

UnionFindっぽい雰囲気。特定の辺を除いてmergeしたあとにグループの数が2以上かどうかで判定可能。
成約がとても緩いので、各辺を選択してからそれ以外の辺を結んで判定する $O(M(M+N))$ が間に合う。

提出コード

ABC191 C - Digital Graffiti

感想 (解答中に考えたこと)

難読では……？ちょっと調べてみて納得したが、もう少しサンプルほしい……。
辺の向きのベクトル(辺の方向と垂直な向き)が変わるたびにカウントするも、サンプルすら合わない。
解説ACした。辺が生じるときは角が必ず存在するので、zip(range(H-1), range(W-1))の範囲で $2\times 2$ で角かどうか (つまり黒または白のマスが1つだけ)を判定し、その数を出力すれば良い。難しいが、思いつけるようになりたい……。

提出コード

ABC166 E - This Message Will Self-Destruct in 5s

感想 (解答中に考えたこと)

$|i-j|=A_{i} + A_{j}$ の組を見つける問題。前提として $O(N^2)$ は無理。 $i$ と $j$ に分けると、 $i - A_{i} = j + A_{j} \; (i > j), i + A_{i} = j - A_{j} \; (j > i)$
また組の数が分かれば良いので、 $i > j$ のような条件に固定しても問題ない。
以上のことから、 $i + A_{i}$ をkeyにHashMapにその個数を保存し、 $i - A_{i}\; (i = 1, 2, 3, ... N)$ で検索して個数の和を出力すれば良い。

提出コード

ABC194 D - Journey

感想 (解答中に考えたこと)

漸化式をそのまま実装すればできるのでは…？つまり $N$ 個の頂点があって $n$ 個目の頂点をつなげる期待値を $E(N, n)$ として、 $E(N, n+1) = E(N, n) + \frac{N-n}{n}\sum^{\infty}_{i=1}\left(\frac{n}{N}\right)^{i}i = E(N, n) + \frac{N}{N-n}$
開始位置と終わりの位置に気をつけて実装する。

提出コード

CodeFestival 2016 qual A C - Next letter

感想 (解答中に考えたこと)

前から貪欲にaに変えていけば良い。変えられない場合は嬉しくない変形になるのでスルーし、次の文字の変形にトライする。
最後の文字の場合はKになるまで操作を行えば良い。(それ以外の文字で操作すると嬉しくない)

提出コード

なんかめっっっっちゃバグらせた