問題概要 $ N $頂点からなる木があり，$ i $番目の頂点には最初$ A_i $個の石が置かれている． 相異なる2つの葉を選び，その2頂点間のパス上にある頂点から石を1個ずつ取り除く．ただし，パス上の頂点で石が1個も置かれていない頂点がある場合，この操作はで…

問題概要 高橋くんと青木くんが Nim (石取りゲーム) をする．ただし先攻は高橋くんで，それぞれの山から1回に取れる石の数に以下のような制約がある． $ N $個の山があり，$ i $番目の山は最初$ A_i $個の石がある． ある地点で$ i $番目の山にある石の数を$…

codeforces.com 問題概要 学び 解法として「和をkで割ったあまりがvをkで割った余りと等しくなるようなタンクの部分集合」がほしいと考えていたが，トレース？付きのDPがなかなか書けなかった． 以下のソースコードでは2次元配列used[i][j]を使って，「1から…

問題概要 整数 長さは 上記2条件を満たす文字列中で，同じ文字のみからなる部分文字列のうち最長のものの長さが最も短い． 上記3条件を満たす文字列中で辞書順最小である． 解法概要 "同じ文字が続いても良い数" ABB…B(Bがk個) ABB…B ABB…B…のprefix AA…A(A…

問題概要 与えられる文字列sと'yahoo'の0回以上の繰り返しの文字列との編集距離を求める． 解法 普通の編集距離DPを元にいくつかアレンジを加える． 編集先文字列はインデックスjについてj%5が0,1,2,3,4番目の文字がそれぞれy,a,h,o,oの文字列と考える 'yaho…

問題概要 N個の文字列が与えられる． 解法 まず， 次に， " (こうして書き出してみると割と"やるだけ"……) ソースコード #include<iostream> #include<string> #include<vector> #include<set> #define rep(n) for(int i=0;i</set></vector></string></iostream>