裏紙

ほぼ競プロ、たまに日記

2016/2 Solved (1)

2/1

2/2

2/3

2/4

2/5

CF AIMTechRound(Div2)に参加

ABCの3完、結構速く解けたので自己最高の96位。

C - Graph and Stringに関して解き方のメモをしておくと、まず、全ての頂点とつながっているならその頂点はbを選ぶことが出来、その時が他の頂点に一番影響が無いのでそれを選ぶ。あとはどれか1つでも繋がっていない頂点がある頂点は、aかcでないといけなくて、その繋がっていない頂点は逆にcかaになる。頂点番号が若い順から、その頂点がbに決まってなければaとcのどちらを選ぶのが良いか決めていく。その頂点よりも少ない番号全てに対し、繋がっているか繋がっていないかで許される頂点は2種類になるので全ての条件に合致する方を選択。どっちでもうまくいかない時は、そこで切り上げてNoと出力。という貪欲みたいな感じでやった。

2/6

ABC033に参加

ABCの3完、Dは偏角でソートするなんて考えつかなかったけど、解説を聞いて終了後に書いてみるとあんまり量的には多くならなくてなるほどってなった。

2/7

SRM 681 Div1に参加

0完...Easyはフローなのかと思ったけどフローほとんどやったこと無いからどういうグラフにすればいいか分かんなかったし実際はそうじゃなくて二分探索+貪欲でいけるらしいので頭が足りない。unratedらしい(助かった)

CF #342 Div2に参加

BCの2完、Aはシンプルに考えられなくてなんかごちゃごちゃしたの書いてたし落ちたしめっちゃ時間かけてしまったし、BCから先に解き始めるべきだった

ABCまではできて、ときどき+αの問題を通せるくらいまで達したいんだけどなあ...練習しよう

2/8~10

yukicoder★2解きまくり週間

2/11

imulan.hatenablog.jp

2/12

★2解きまくり週間がひとまず終わった。

通行可能な辺を累積和を取ることではやく処理しないとTLEになる。

蟻本p.139を読みながら。

マルチバイト文字はPython3で処理した

累積和を使って重心の計算を上から順にやるオーダーが1つ落とせる。

2/13

(この辺で、ただ解いた問題つらつら載せても記録にしかならないと思ってひと言コメントをつけ始めた)

解説を見て、うわああってなったけど蟻本p.239にも類題があって、「ああ行列累乗テクはやっぱ使うんだ」ってなったけど共役な無理数にきづけなかったし、どうしようもなかった。高校の時こんな感じの話は結構何回もやったような話だと思うんだけど...

Python3ではmap関数で1行に複数の入力があるものを処理しようとすると、map objectが返ってくるのでそのまま利用できないからlistなどをかませて使う。今回はsetが役立ちそうだったのでsetを使用。(submission)

こういう入力がややこしい感じでも綺麗に処理できる良さがやっと感じられるようになってきた(submission)。1行目みたいなアンパック代入なら、何もかませなくて大丈夫。あみだの部分の処理は縦の棒を見る必要性がないので、indexを1からスタートして1個飛ばしで読むようにすれば横棒の有無だけをみることができてそれ以下の処理がシンプル。

運ぶ順序が決まっていて、ある荷物をどの山に載せるべきかは、ギリギリ載せても大丈夫な位置がベストであるからそのような位置をlower_boundで探して値を更新してソートしておく。もしどの山にも載らないくらい重いなら、新しい山を作る。auto型のよさ(submission)。

2/14

1~nまでの和をn(n+1)/2で計算しておいて、2の累乗を配列で用意しておきnより小さい限り2倍して引く。オーバーフローこわいのでPython使った

CF 8VC Venture Cup 2016 - Elimination Roundに参加

ABCの3完、Dは正直出来るべき問題だった感がある...

imulan.hatenablog.jp

2/15

リストの要素を探してindexを返す関数はlist.indexなので、それを使ってCDの位置を見つけてその都度swapする。

10個以上は10個買いがお得。端数を個別に買うか10個買いがおとくかで最小値で判定。

アルファベットごとに数え上げ。

こういうのは整数で出来る範囲に収めるのが誤差回避に繋がる。消費税5%をかけて小数点以下切り捨ては、最小に価格を105倍しておいてから整数同士の割り算として100で割ることによって小数点以下切り捨ても実現できて確実な方法。

数字の変換と逆変換を用意しておいて、数字を変換してからソートして、それを逆変換してあげる。