問題 codeforces.com 解法 区間DP。@mayoko_ 申し訳ねぇ申し訳ねぇ… [l,r]で回文を挿入しまくって文字列を作りたいです． a[l]==a[i]のところがあったときそこを使うことにしたとき，[l+1,i-1]と[i+1,r]について考えればOKです 回文が始まるのは長さ1か長さ2…

問題 codeforces.com 解法 増加列に含まれる値の種類は多くてN種類なので、T>Nならば、最も多い種類の点の数を (T-N) 回足せば良い。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner…

問題 codeforces.com 解法 テーブル上の既に明らかになっているGCDを取り除いた時に最大の数は、必ず元の配列に含まれているはずである。 コード import java.util.ArrayList; import java.util.Map; import java.util.Scanner; import java.util.TreeMap; p…

問題 codeforces.com 解法 縦，横1000の長方形に切る．長方形内で点をyの値でソートする．ひとつの長方形内では，そこに含まれる点の数をPとすると，x軸方向に1000*P，y軸方向にの長さが最大で必要になる．長方形間ではx軸方向に最大で2000必要になり，これ…

問題 codeforces.com 解法 codeforces.com1つだけでループしている頂点があれば，その頂点から他の頂点に辺を出せば良い．2つだけでループしている頂点があれば，その2点を中心にし，そこから他の頂点に辺を出していく．この2点間の間は1本の辺だけで条件を…

問題 Problem - C - Codeforcescodeforces.com 解法 頂点iに接続している頂点vについて考える。 vが葉に接続している一本道の途中にある頂点であれば、葉の一部と考えれば良い。 i以外にvが持っている葉が2枚以下であれば、vはiの対岸の行に収めることができ…

問題 Problem - B - Codeforcescodeforces.com 解法 「N人をK個のグループに分ける。グループの人数はN/KまたはN/K+1でなければならない。グループの人間を身長順にソートした時の隣接する2人の身長の差の合計を、グループのコストとする。グループのコスト…

問題 Problem - A - Codeforcescodeforces.com 解法 合計lだけ長くした時、辺の組み合わせは全部で(l+2)*(l+1)/2通りになる。このうちhalf=(a+b+c+l-1)/2とした時に、辺の長さがhalfを超える場合三角形にならないので引けばいい。 コード import java.util.S…

問題 Problem - D - Codeforcescodeforces.com 解法 Codeforces Round #316 (Div. 2) D. Tree Requests - mayoko’s diarymayokoex.hatenablog.com コード import java.io.IOException; import java.io.InputStream; import java.util.ArrayDeque; import jav…

問題 Problem - E - Codeforcescodeforces.com 解法 dp[h][w][rh][rw]:=(h,w)を通り、(rh,rw)を通る経路が回文である経路数を持たせたいがメモリが足りない。しかし、(1,1)と(h,w)、(H,W)と(rh,rw)の距離を両方mとして、mを少しずつ小さくしていくようにすれ…

解法 2000000以下の素数と回文を全列挙して、全てのnについて条件を満たすかどうかしゃくとり法で調べれば良い。 コード import java.util.ArrayList; import java.util.BitSet; import java.util.Collections; import java.util.Scanner; public class Main…

問題 Problem - C - Codeforcescodeforces.com 解法 について考える。 の時、自分より前に出てきたbの数を記録しておく。 の時、自分より前に出てきたに記録されているbの数の和を記録しておく。 の時、それまでに出てきたbの数に1加える。 コード import ja…

問題 Problem - D - Codeforcescodeforces.com 解法 残ったボードに存在しうる船の数を常に保持するようにする。 コード import java.util.Scanner; import java.util.TreeMap; public class Main { public void solve() { Scanner scanner = new Scanner(Sy…

問題 Problem - D - Codeforcescodeforces.com 解法 含む範囲のクエリは、重なっている部分だけを取り出していけば、必ず1つだけの範囲になるはず。離れた2つの範囲が出てきた場合、題意に合わないのでcheatである。含まない範囲のクエリは、和集合を取って…

問題 Problem - E - Codeforcescodeforces.com 解法 [i文字目から][jの文字が][k個連続している]という同じ文字列が連続している区間の情報を保持しておく。(start, end, d)というクエリに対して、startからendの中に入っている文字列の数を種類ごとに集計し…

問題 Problem - C - Codeforcescodeforces.com 解法 包除原理を使う。各障害物のセルとゴールのセルに、 (スタートからの経路数)-(障害物を1つ通る経路数)+(障害物を2つ通る経路数)-(障害物を3つ通る経路数)-...を記録するようにすれば良い。 コード import …

問題 Problem - C - Codeforcescodeforces.com 解法 最終的な値が入力の最大値を超えることはない。 aとbが一致するまで大きい方を1/2ずつしていった時の最終的な値をM(a,b)とすると、最終的な値はM(a0,a1,a2,...)を2の累乗倍したものである。 コード import…

問題 Problem - C - Codeforcescodeforces.com 解法 クエリ処理のたびに、最大の高さと、最大の幅を知りたい。 切られるたびに1つ辺が減り、2つ新しい辺が出来る。 以下、縦に切った場合を考える。 w0の長さの辺が切られ、新たにw1とw2の長さの辺が出来ると…

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces #311 Div2 E. Ann and Half-Palindrome - kmjp's blogkmjp.hatenablog.jp半回文の文字列の洗い出しと、K番目の文字列の探索は、各で求めることができるので時間内に終わる。 しかし、kmjpさん…

問題 Problem - C - Codeforcescodeforces.com 解法 テーブル内で最大になる高さを総当たりする。最大の長さLの脚がM本存在する時、Lより長い脚は全て切り、Lより短い脚については、合計M-1本以下になるようにエネルギーの小さい方から切る。 コード import …

問題 Problem - E - Codeforcescodeforces.com 解法 平方分割を用いる。与えられたN個の数字をの配列に入れる。個で1ブロックと考え、ブロック全体がカバーされている加算操作に対しては、別の場所に記録しておく。 import java.io.IOException; import java…

問題 Problem - C - Codeforcescodeforces.com 解法 各(x,y,UL)クエリに対して、一番近い右のクエリを見れば欲しい情報が書いてあるようにしておく。 コード import java.util.Scanner; import java.util.TreeMap; public class Main { public void solve() …

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces Round #309 (Div. 1) C. Love Triangles - mayoko’s diarymayokoex.hatenablog.com問題分が分かりにくいが、「ある2人が同じ人を好き、あるいは嫌いな場合、その2人は愛しあわなければならない…

問題 Problem - B - Codeforcescodeforces.com 解法 島とに対して架けられる橋の長さaは を満たさなければならない。, とおいて、shortDでソートしておく。ある距離lengthについて小さい方から見ていく。shortD=lengthとなる島間距離があったら取り出して、l…

問題 Problem - C - Codeforcescodeforces.com 解法 最大の数字kについて考える。kがn個あり、それ以外の数字がm個あるとすると、kのうち1つは一番後ろでなければならない。残りのn-1個の取りうる場所の組み合わせは、k以外の数字の区別をつけなければ通りに…

問題 Problem - D - Codeforcescodeforces.com 解法 Codeforces Round #309 (Div. 1) B. Kyoya and Permutation - mayoko’s diarymayokoex.hatenablog.com コード import java.util.ArrayList; import java.util.Scanner; public class Main { private long[…

問題 Problem - D - Codeforcescodeforces.com 解法 kをビットに直して考える。各aのi番目のビットの組み合わせは通りあるが、kのi番目のビットが0になるためには、そのうち1が連続して存在するものを取り除かなければならない。 例えば、n=3のとき、以下の5…

問題 Problem - D - Codeforcescodeforces.com 解法 全ての組み合わせを列挙すると通りあるため、間に合わない（と思われていたがC++なら間に合う）。3点が同一直線上にあるパターンと、3点のうち2点以上が重なっているパターンを除けば良い。 まず、点iに注…

問題 Problem - C - Codeforcescodeforces.com 解法 天秤が釣り合う時、となる。この時、と書ける。 mをwで割り切れる限り割り続けると、またはというように、あまり1か-1になる。つまりmがwで割り切れる時は割り続け、割り切れなくなったら1を足すか引くか…

問題 Problem - E - Codeforcescodeforces.com 解法 しゃくとり法。 コード import java.util.Scanner; public class Main { public void solve() { Scanner sc = new Scanner(System.in); String input = sc.next(); sc.close(); int N = input.length(); i…