問題 Marked Ancestor | Aizu Online Judgeルートが頂点 0 の木が与えられる。頂点 0 の点は最初から黒く, それ以外の点は白い。これについて, 以下の二種類のクエリが投げられるので, 対応する。 頂点 v を選び, その点を黒く塗る。 頂点 v, もしくはその先…

問題 TopCoder Statistics - Match OverviewDAG が与えられる。次の条件を満たす頂点集合 S の最大の大きさを求めよ。 条件: 任意の異なる 2 つの頂点 i, j S について, i から j へのパスも j から i へのパスもない。 解法 この問題に関して, dilworth の…

問題 Eleven Lover | Aizu Online Judge数字のみからなる文字列 s が与えられる。この中に, 連続した文字列でその表す数が 11 の倍数であるようなものは何通りあるか。ただし, 先頭が 0 であるような数は数とみなさないことにする。 解法 区間 [i, j] が 11 …

問題 Class Representative Witch | Aizu Online Judge 解法 (S[i], T[i]) のペアごとに考えます。S[i] と T[i] の間にいくつの P[j] があるかが分かれば(これは lower_bound を使えば高速にわかる), 2 つおきの累積和を使って目的の値が求められそうです。 …

問題 City Merger | Aizu Online Judgen 個の文字列が与えられる(それぞれの文字は 20 字以下)。これら n 個を連続部分文字列として含む文字列を作りたい。この文字列の最小の長さはいくらか。 解法 bitDP します。dp[now][state] = (state にある文字列は作…

問題 arc056.contest.atcoder.jp 解法 kmjp さんの解法を参考にしました。 kmjp.hatenablog.jpdp[t] = (「t の時間に飲む」と決めたとき, t の時間までに得られる美味しさの総和の最大値)とします。部分点解法では, t の前に飲む時間 t1 を全探索します。t1 …

問題 No.387 ハンコ - yukicoder 解法 bitset を使うアレです。各色ごとに考えます。 色 i が現れる位置 pos を覚えておき, memo |= b*2^pos とすれば, memo という配列に「色 i が塗られる場所」が記録されます。これをすべての色について行えば良いです。 …

問題 No.386 貪欲な領主 - yukicoder 解法 よくある問題は, 「木に辺コストが与えられる。頂点 (u, v) が何個も与えられるので, u, v 間の距離を答えろ」みたいのがあります。これは LCA を使うと簡単に求めることができるので, 今回の問題もこれに帰着させ…

問題 No.385 カップ麺生活 - yukicoder 解法 お金が素数になるところは絶対に通る方が得です。そこで, dp[m] = (お金が m になるまでに買えるカップ麺) というのを覚えておくと, m が素数のところでは ans += dp[m] とする dp[m] が最大のところで ans += dp…