問題概要 部屋にプラグがいくつかある。変換器がいくつか存在する。使いたい道具と、必要なプラグが与えられるので、使う道具の数を最大化する問題。 解法 プラグの変換は容量無限の辺を張り、最大流を流す。

問題概要 人がN( 解法 各人aに対して、aはXに属する、aはYに属する、のような頂点を持っておきunion findでつなげていく。

問題概要 TシャツがN( 解法 二部グラフの最大マッチング。本当はもう少し効率よくとけるけど、サイズが小さいので実装が楽なのを選んだ。

問題概要 ノード数V( 解法 Dijkstra。

問題概要 ノード数V( 解法 各辺に容量1を付随して始点から終点へ流量2の最小費用流を流す。

問題概要 1*1*1, 1*1*2, 1*1*3のブロックがある。これを幅w( 考えたこと Div1 500とはちょっと違うのか、後でまたぐことがあるから分割してメモ化再帰で解くのは厳しい。 しかしw 下のビットと上のビットを組み合わせるタイプの奴か。 前処理で下のビットを…

問題概要 2次元ボードにA..Zの文字が1文字ずつ埋まっている、4近傍を選んで歩くとき、A..Zを順に踏んでいくパスがあるかどうか判定する問題。 考えたこと 分岐がないのでDFSするだけで行けそう。 何事もなく通った。

250は今回もリサブミット。早解きしないとどうしようもなかったのでこれはまあ仕方がない。500は解けなかったが類題をちょっと前に解いていた。学習能力…。チャレンジフェーズは見切り発車で2失敗したけど、順位にはあまり影響しなかった(もちろんそういう状…

問題概要 連続するC[i]( 考えたこと まずサンプルを考えよう。 (...延々と考える) サンプルはとりあえず理解した。でもこれ一般化はキツい。 とりあえず単調性はあるので長さに関して二分探索はできるけどそれはどうでも良いような気がする。 区間和なんだか…

問題概要 整数n(素数の和で表すことができるか。 考えたこと 素数かどうか見るだけな気がする。素数ってきっと合成数の和で表せる…よね。 自信はないけどみんな提出しまくっているので速く出さないとどうせ死ぬのでそのまま提出。 提出後n=1..10とかを調べて…

問題概要 長さN( 解法 累積和を使って連続する部分和を表現すると、accum[end] - accum[from-1] =) kのような形に変形できる。さらにaccum[from-1] + k >= accum[end]のような形の線形計画法になって、このような形(右辺、左辺に係数1の変数が出てくる)だと…

問題概要 2次元平面上にV( 解法 距離が10以下の2点間に辺を張って全点間最短路。

問題概要 ノード数V( 解法 ノードに容量がある場合は、ノードを分裂させてその間に容量付きの辺を張れば良い。

結果。 どの問題も割と易しめ。

問題概要 ノード数V( 解法 Dijkstra。

問題概要 2次元平面上にV( 解法 円の半径について二分探索する。union findでつなげて要素数がS以下になったらvalid。

問題概要 ノード数V( 解法 トポロジカル順序の小さい順にDPする。有向閉路があったらそれ以降は無数に存在する。

問題概要 無向グラフが与えられる。辺を追加してグラフを連結にしたい。総コストを最小化する問題。 解法 Kruskal。

問題概要 ノード数V( 解法 ベルマンフォード。

問題概要 ノード数V( 解法 Warshall-Floyd。

結果。 久しぶりに2完できた。500がちょっと遅かったけど、とりあえずは解けたことに満足。でも計算量勘違いしてた。250は絶対撃墜祭りになると思っていたら予想通りそうなった。いろいろ準備していたのに部屋の人々が撃墜力高くて1個しか落とせなかった。次…

問題概要 1*1*1, 1*1*2, ..., 1*1*K( 考えたこと 問題文長い。でも図を眺めてキーワードっぽいのを拾い読みしたら何となく理解できた。 要するに高さぴったりHのものを作るのかー(誤読)。 制約がDPしてくださいといわんばかりなので、DP的に考える。 高さが…

問題概要 a,b,c,d,ub(1区間[1,ub]の中に、初項a公差bの等差数列、初項c公比dの等比数列に含まれる数がいくつあるか求める問題。 考えたこと 包除原理っぽく両方に含まれる奴を最後に引けばよさそう。 等比数列はすぐ爆発するから全列挙余裕。ただしd=1は例外…

結果。全部解いたのに反映されてない…。どれも問題文が心持ち長くて入出力が面倒なのが多かったけど難易度としてはどれも易しかった。

問題概要 ノード数V( 解法 グラフが小さいのでWarshall-Floyd。

問題概要 UnionFindして最大の群の要素数を求める問題。 解法 やるだけ。rankとか持っておくと多少楽になるかも。

結果。PKUの簡単な問題とTimusの簡単な問題からなるセット。P1~P9は既に通してた。

問題概要 N(裁定取引でもうけることができるか求める問題。できる場合は最短のループを求める。要するに、最小の負の閉路を検出する問題。 解法 ベルマンフォードするだけだが、更新のタイミングには注意すること。

問題概要 ノード数N( 解法 最大のボトルネックな部分は最短経路を求めるのと同じようにできる。今回はNが小さいのでWarshall-Floydで十分。

結果。初参加だったので勝手が分からず、5問全部通してから登録したけど反映されなかった(5問目だけは反映されてる)。