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

提出コード
ABC075 C - Bridge
感想 (解答中に考えたこと)
- UnionFindっぽい雰囲気。特定の辺を除いてmergeしたあとにグループの数が2以上かどうかで判定可能。
- 成約がとても緩いので、各辺を選択してからそれ以外の辺を結んで判定する
が間に合う。
提出コード
ABC191 C - Digital Graffiti
感想 (解答中に考えたこと)
- 難読では……? ちょっと調べてみて納得したが、もう少しサンプルほしい……。
- 辺の向きのベクトル(辺の方向と垂直な向き)が変わるたびにカウントするも、サンプルすら合わない。
- 解説ACした。辺が生じるときは角が必ず存在するので、
zip(range(H-1), range(W-1))の範囲でで角かどうか (つまり黒または白のマスが1つだけ)を判定し、その数を出力すれば良い。難しいが、思いつけるようになりたい……。
提出コード
ABC166 E - This Message Will Self-Destruct in 5s
感想 (解答中に考えたこと)
の組を見つける問題。前提として
は無理。
と
に分けると、
- また組の数が分かれば良いので、
のような条件に固定しても問題ない。
- 以上のことから、
をkeyにHashMapにその個数を保存し、
で検索して個数の和を出力すれば良い。
提出コード
ABC194 D - Journey
感想 (解答中に考えたこと)
- 漸化式をそのまま実装すればできるのでは…?つまり
個の頂点があって
個目の頂点をつなげる期待値を
として、
- 開始位置と終わりの位置に気をつけて実装する。
提出コード
CodeFestival 2016 qual A C - Next letter
感想 (解答中に考えたこと)
- 前から貪欲に
aに変えていけば良い。変えられない場合は嬉しくない変形になるのでスルーし、次の文字の変形にトライする。 - 最後の文字の場合はKになるまで操作を行えば良い。(それ以外の文字で操作すると嬉しくない)
提出コード
なんかめっっっっちゃバグらせた