2019/1/30
2019/1/30
辺は重みの昇順でソートし、union findで連結成分に頂点の重みと辺の重みの最大と追加時点で頂点の重みよりも大きかった辺の数を持たせる。
追加した辺が連結成分の重み以下だった場合、その連結成分内の辺は全て条件を満たす(昇順であるため)。
そうでない場合、その辺は最終的に使えない可能性があるので個数を保持しておく。
辺の追加の度に現在条件を満たす辺の数を計算することができるのでそれが答えとなる。
2019/1/6
2019/1/6
各頂点vに数字a_v(>=0)が振られた根付き木があり、
各頂点vの根からの経路中の頂点のaの和、s_vが与えられる
ただし、深さ(根からの距離+1)が偶数の頂点はs_vが消されている
各s_vに矛盾しないようなa_vを計算し、ありうる中の最小のsum(a_v)を求める問題
ある頂点vの親をpとしたとき、s_p、s_vがわかっていればa_v = s_v - s_pである
s_vがわかっていない場合は、vの子のsはわかっているためa_vは条件を満たす中の最大であるmin(s_(vの子) - s_p)となるのが最適
a_vがわかればs_vも確定するため、根から上の処理を子に向かって行なっていけばよい
2018/12/27
2018/12/27
N個の整数A[i]が与えられる
以下の操作を任意回行なって、全てのiに対してA[i] = B(Bは任意の定数)を達成できるかを判定する
A[i] += 2if (A[i] == A[i + 1]) A[i] = A[i + 1] = A[i] + 1
2を任意回加算できることから、後者の操作のみで数列の偶奇を合わせることができるかを判定すれば良い
後者の操作をうまく行うことで、1(00)*1であるような数列(mod 2)は00..00にすることができる
また、1(00)*1→00..00の操作でできる数列は2の倍数の長さになることから、以下のような挟んだ形も処理できることがわかる
10100101
10000001
00000000
よって、スタックで前の1の位置を保持して都度処理をすることで00..00にできるかの判定をすることができる11..11にできるかについても同様に判定できるので両方で判定を行い、どちらかで可能であればYES、そうでなければNOとすれば良い
2018/12/24
2018/12/24
木の上を操作する回数は深さと同じなので、前から貪欲に以降解が構築できるかの判定を逐次行うことで最小の解が構成できる。
解の存在は部分和問題のように見えるが、Nが選べるならN-1が選べるので選べるものの最小と最大を見れば良い。
clog
clog
ブログサービスの開発ログ
2018/12/9
twitter cardに対応した
2018/12/6
サーバー側のリファクタリング
その他
- 記事にプロジェクト内番号の付与
- created_atにon updateがついていたのを修正
/api/v1/projects/:projectId/post?id=を追加
2018/12/2
TODO
- クライアント
- ツイートボタン
- ツイッターカード
- レイアウト変更
- サーバー
- プロジェクト表示名の追加
- 記事を投稿順で呼べるAPIの追加
- Internal Server Error解消
2018/9/18
- 文章中に画像を追加しやすく
- 単一記事へのURL
2018/9/9
- markdownのパーサーをmarkedからmarkdown-itに変更した
- markedだと改行でpタグが分割されなかったため
- highlight.jsを導入した
- ↓
{
"json": "hoge"
}2018/9/6
投稿フォームを追加
2018/09/05
サムネイル
