読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

2016/4 Solved(1)

4/1

mapを使う。

4/2

前からと後ろからとdijkstraして、中継点を全探索する。

4/3

imulan.hatenablog.jp

4/4

4/5

解説の方法よりも下の桁から見ていって、すでにleading zero領域に入っているlucky numberの数と繰り上がりの有無を保存しつつDPを埋めていく方法が自分にはしっくりきた。

imulan.hatenablog.jp

4/6

targetから逆算していって、initialに辿り着けるかをBFSする。先頭にBが来ているときは先頭を除いて全体をreverseしたものがひとつ手前であり、一番後ろにAが来ているときはそのAを除いたものがひとつ手前のものとしてありうる。

4/7

円環状に数字を並べる時に、隣り合う数字同士の差の最大値を最小化しようと言う問題。ソートして、端から埋めていくのが一番差が開かなくていいんじゃないかってやったらうまくいった(1,3,5,11,9,2的な)。

4/8

N以下で、素数、またはある素数の累乗(16とか、27とか)の値がLCMに最も影響するので、その数の2倍を取れば良い。

4/9

GCJ2016 Qualification Roundに参加

A,BとC-smallで45点。C-largeは、上半分と下半分が同じなら絶対約数があるっていうの、めっちゃ賢いと思った...

4/10

(何も出来なかった)

4/11

4/12

TCO 2016 Round 1Bに参加

Easy,Medの2完。Hardは方針も立たなかったし復習しておきたい。引っ越しなどで約1ヶ月ぶりのコンテスト参加ってこととPC変えたばっかってのが影響して、Arenaが直前まで開けなくて焦ったり、いざEasyを開けたらGreedが設定できてなかったり、設定が終わったと思ったら手が滑ってMedを開けてしまったり、散々だったがレートは増加した...未だにDiv1に留まれているって感じがする。

4/13

解説を見て、dpを頂点、そこの頂点がどっちでも良い/白じゃないとダメにすれば確かにうまくいくと感じた。数え上げの時に、考えてみて加算と乗算がまざるな...とは思ったけどこういう分け方だったか...(木DPを初めて書いたかも)

4/14

imulan.hatenablog.jp

4/15

区間を決めて、その区間が妥当であるかの判定はO(N^3)で行える。また、割り切る数vの候補については、リストの中のうち最低どれか1つを割り切る素数に限定すれば、1000以下の素数の一部のみで調べればよいことになるので十分間に合う。

Pythonには文字列を大文字にするupper、小文字にするlowerがある。