olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

AtCoder

全国統一プログラミング王決定戦本戦-F Flights

問題概要 N個の頂点があり、各頂点はx,y座標とコストを持っている。これらをx,y,costで表す。頂点i,jを考えたときに、を満たすときにij間に距離の辺が貼られる。 スタートからゴールまでの距離の最小値を求めたい。距離はで表す。 メモ まずスタートとゴール…

全国統一プログラミング王決定戦本戦-E Erasure

問題概要 N個のブロックが並んでおり、幅K+1以上の全ての区間がある。区間の数をM個とすると区間の選び方は通りある。全てのブロックを選択できる区間の使い方は何通りか。 メモ 素直なDPをする方法と包除原理を用いる方法がある。 素直なDP seicaさんから掲…

AGC008-E Next or Nextnext

問題概要 サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、 p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。 メモ 途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかった…

AtCoder Biginner Contest 001 D:感雨時刻の整理

難しいというよりも手間のかかる問題と思う。 開始時刻と終了時刻を5分単位に直し、00:00~23:55からの各5分について雨が降っているか否かをboolで判断する。 その後、bool値と雨が降っているかいないかのbool値から、開始時刻と終了時刻を列挙する。 http:…