19に参加したのでそのメモ。結果は346位/3176人だった。Cycles4つのノードA,B,C,Dをもつ有向グラフを考える。D→Aのエッジをa、A→Bのエッジをb、B→Cのエッジをc、C→Dのエッジをd、A→Cのエッジをe、B→Dのエッジをfとする。a~fの重みが与えられたとき、負の閉路をなくすためには、最小でいくら重みを足せばよいか。1つのエッジにのみ重みを足すことができる。不可能な場合は-1を返こと。制約:a~fの重みの値は-20から+20全エッジに対し、足す重み全て(0~80)をチェックするだけでよい。ちなみに、すべてのループがエッジaを通るため、答えが-1になることはない。Robots無限個のキャンディーが入ったM個のコンテナが、1列に配置されている。2つのロボットがある。ロボットはコンテナ間を移動して、キャンディーを運ぶことができる。キャンディー運ぶ順番(あるコンテナから別のコンテナへ)が指定されたとき、トータルで最小のロボット移動距離を求めよ(隣り合うコンテナ間の距離を距離1とする)。キャンディーを運ぶ順番は次のように指定される。#コンテナMa1からMb1に運ぶ。Mbn制約:次のDPを設定し、手順を後ろからループしていく。以降の移動距離の最小(Aの位置<Bの位置)単純に実装するとメモリと実行時間が足りなくなるので、(1)DP配列の再利用(2)あり得ない条件は無視して枝刈り、を行った。Products次の数列を考える。スカラ積の集合としたとき、Sの剰余の個数をMでModしたものを求めよ。制約:で開始するフィボナッチ数列の変種と考えればよい。フィボナッチ数列の特徴を利用すると、この数列に対してはが導き出せる。部分を見ていけばよい。}}これは解けなかったのが悔しかった。「フィボナッチ数列」で検索してみるべきだった。Subsequences一次元配列A[](長さN、Indexは1から始まる)が与えられたとき、次の疑似コードで得られるansを答えよ。1)制約:まった手が出なかった。Editorialは理解できるのだが、最後が「これをSegmentTreeを使って解けばよい」で終わっていて困る・・・。このレベルなら自明であるべきなのだろうか。仕方ないので、SegmentTreeの集中特訓をしてから、後でもう一度解いてみることにする。なる回数を求めればよい。ここで、と定義すると、となる。求めるためには、別の配列Bを用意するとよい。範囲内すべてが1になるものの数と等しくなる。SegmentTreeを使えば解くことができる。月別アーカイブはてなブログをはじめよう!yambe2002さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。