裏紙

ほぼ競プロ、たまに日記

2016/9 solved(2)

9/16

最近簡単な問題を意識してPythonで解いている。

9/17

imulan.hatenablog.jp

9/18

ただシミュレーションしていく。

9/19

文字列sの中から長さ26の部分文字列を取り出し1つでもその部分文字列がアルファベット1回ずつ現れるようなものを構成できるかを調べる問題。全ての部分文字列について眺めていけば良いが、まず?以外をながめて現れるものをカウントし、?を埋めていくような流れにするとよい。

9/20

確実な方法として、レベルkの時は(k * (k+1))^2になるようにすれば必ず最後までうまくいくようにすすめることが出来る。C++だとオーバーフローするので、Pythonで作ったけど時間的にも余裕だった。

9/21

imulan.hatenablog.jp

DPにより解く。dp[現在の頂点][今までに選んだ個数][直前を選んだかどうか][最初を選んだかどうか]で最大値を更新していく(submission)。

9/22

9/23

まず、長さを揃えておく。長さが18に満たないものは上位の桁を全て0埋めしておくことで、集合の管理とクエリの数を一致させることが出来る。集合の管理は個数を数えたいのでmapでやった。

9/24

CODE FESTIVAL 2016 qual Aに参加

ABCの3完。100位に入るにはやはりDを解く必要があった...等差数列っぽそうということまでは考えたけど手付かず。

9/25

9/26

はしごを横に掛けるときに、間の高さが低いことを確認するのを忘れていた。

Editorialを見ながら実装した。ここから二部グラフっぽい構造に落とし込むのが全てのポイントだったという感じ...ただそれができてもつまづくポイントが何個かあって、グラフの問題やっぱりまだあまり得意じゃないなという感じがする(submission)。

9/27

imulan.hatenablog.jp

9/28

setを用意して、左から順番見ていく。そこの値をsetにいれ、その時点での最大値を出す(これがC++std::setだとset.rbegin()で簡単にできる)。その数字の要素が最も右の値だったらその値をsetから削除する。最も右の値かどうかは事前にmapなどに用意しておいた(submission)。

9/29

答えを二分探索する。k-1番目以下かk番目以上かを判定するのはあらかじめ配列をソートしておくことでO(NlogN)で可能になる(submission)。

9/30

CF #374 (Div2)に参加

久しぶりに2完してしまった...Cは多分実装方針があまりよくなかったのか、MLEしてしまった。