2015-08-01から1ヶ月間の記事一覧

topcoder SRM 666 WalkOverATree

頂点数N (1 <= N <= 50) の木がある。スタート地点が決められており、辺の上を移動できる回数L (1 <= L <= 100) が与えられたとき、最適な動き方をすれば、(重複を許さないで) 最大で何個の頂点に行くことができるか? O(LN3) よりは小さい解法 頂点v以下に…

AOJ 0254 Scone

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0254 概要:N個の正整数列 (1 <= N <= 3*104) が与えられる。連続する部分列の和 mod M (1 <= M <= 105) を最大化したときの値を求めよ。 O(N3) 解法 [begin,end) をO(N2)で決めて,和のmod …

AOJ 0270 Modular Query モジュロ・クエリ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270 カードが6, 7, 11, 13, 14, 15, 16, 19で,q=5のクエリに答えたいとする。 5で割った余りが最大になり得るのは,5*1のlower_boundの1つ前,5*2のlower_boundの1つ前,……,なので,ソートして…

AOJ 1505 Dungeon

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1505&lang=jp 前処理 とりあえずスタート地点からの最短距離d_s,ゴール地点からの最短距離d_gを計算する。 たとえば,各頂点のd_s,d_gが以下のような感じだったとする。 d_s d_g 0 5 1 1 1…