問題 https://beta.atcoder.jp/contests/dwacon2017-prelims/tasks/dwango2017qual_b 0から9と?で構成される文字列 s が与えられる。?を好きな数字に変えることで25の繰り返しのみで構成される s の部分文字列 s' の最大の長さを求めよ。 考え方 貪欲法では…

問題 https://beta.atcoder.jp/contests/abc104/tasks/abc104_d 長さ の文字列 が与えられる。 のうち つ文字を選んだときに左から となっている組み合わせの数を求めよ。 制約 考え方 場合の数である。文字を つ選ぶときに真ん中の を固定して数え上げるこ…

問題 https://atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b 考え方 の閉区間をすべて にする。という操作の性質をフルに用いる。 DPを考える。 の最大値 と定義する。このとき操作を考えて、 の更新を考える…

問題 https://beta.atcoder.jp/contests/abc041/tasks/abc041_d N 頂点上のグラフに、M本の有向辺が与えられる。M本の有向辺の条件を満たし、N 個の頂点を左から右へ横一列に並べる並べ方は何通りか。 制約 2 <= N <= 16 1 <= M <= N(N-1)/2 考え方 トポロジ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=jp 巡回セールスマン問題。有向グラフ G(V, E) 上のある頂点から出発して、出発点に戻る閉路の最短距離を求めよ。 制約 2 <= |v| <= 15 0 <= d_i <= 1000 考え方 bitDPである。…

A.YahooYahooYahoo(400) 問題 方針 雑記 A.YahooYahooYahoo(400) 問題 文字列 S が与えられる。yahooの文字列を0個以上繰り返してできる文字列との編集距離を求めよ。 1 <= |S| <= 105 方針 ポイントは大きく2つ。他は普通の編集距離DPと変わらない（遷移に…

問題 https://beta.atcoder.jp/contests/abc027/tasks/abc027_d 数直線の原点にロボットが置かれている。 はじめ、ロボットの幸福度は 0 である。 このロボットに命令列が与えられる。 命令列は次の 3 文字のみからなり、先頭から末尾まで順に実行される。 M…