問題 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…

問題 D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoderabc018.contest.atcoder.jp 解法 またはなら間に合うが、は間に合わない。そこで男子か女子のどちらか一方だけをビットで回して、もう一方は相手のビットに対する得点を出してソートし、…

問題 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…

問題 Problem - E - Codeforcescodeforces.com 解法 Editorial Codeforces Round #302 - Codeforcescodeforces.comstrings[i][j]に注目した時に、2つの操作を考える。 strings[i][j]だけを変える。この時はcost[i][j]がかかり、少なくともstrings[i]が覚えや…

問題 Problem - D - Codeforcescodeforces.com 解法 Codeforces #302 Div1 B. Destroying Roads - kmjp's blogkmjp.hatenablog.jpまず二点間の最小距離を出しておく。nの最大値が3000なのでワーシャルフロイトをするとだから終わらない。辺の数の最大値が300…

問題 Problem - C - Codeforcescodeforces.com 解法 Codeforces #307 (Div. 2) Editorial - Codeforcescodeforces.com二分探索で間に合う最小の時間を探す。適当に決めた時間に対して、以下の操作を繰り返す。 残ってる人の中から１人を、残っている一番遠い…

問題 Problem - C - Codeforcescodeforces.com 解法 動的計画法で dp[i][j][k]:=i人目まででj行書いてバグがk個ある組み合わせ を求める。ある行fまで終わっている時にfからf+1、f+2、...への遷移を考えると以下のような4重ループになる。 // dp[i][j][k]:=i…

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces #299 Div1 C. Tavas and Pashmaks - mayoko’s diarymayokoex.hatenablog.com コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.…

解法 ならばが成り立つ。が成り立つ時、Mを除いて、が成り立つのはどういう時かを考える。Mのある約数Pについて、Pの倍数がの中に含まれているにもかかわらず、の中にPの倍数が含まれていなかった場合、はPの倍数になるが、はPの倍数にならない場合があり、…

問題 Problem - D - Codeforcescodeforces.com 解法 スコアを上げるためにはできるだけ多く割り算したいので、プレイヤーはnに対して素因数分解する。なので、aの素因数の数をとすると、求める数はである。 クエリのたびに計算すると時間がかかりすぎるので…

問題 Problem - E - Codeforcescodeforces.com 解法 最大フローやるだけ。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { private final int MAX = 10000; public void solve() { Scanner sc…

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces Round #305 (Div. 1) C. Mike and Foam - mayoko’s diarymayokoex.hatenablog.com例えば、棚に(1, 2, 3, 4, 6)が入っていて、6を入れる場合を考える。 1, 2, 3, 4, 6と6は公約数として1をもつ…

問題 Problem - D - Codeforcescodeforces.com 解法 各人iが最弱になるチームを考え、そのチームには最大で何人まで入れることが出来るかを考える。そのためには、iより小さい人がiより右とiより左のどこにいるかを調べれば良い。類題:D: 登山家 - CODE FEST…

問題 Problem - E - Codeforcescodeforces.com 解法 ...->1->0の形にならないといけないので、最後の数字が0でなければNO x->1=1なので最後から2番めの数字が1ならばYES ...->0->0 となっている時、すなわち、最後の2つが0の時を考える 最後の2つ以外に0が1…

問題 Problem - D - Codeforces各頂点からk本ずつ辺が出ているような無向グラフで、橋が存在するものは存在するか。 解法 k=1の時はサンプルをコピペする。橋を取り除いた時、残ったグラフの片方は次数がk-1の頂点が1つ存在し、残りの頂点の次数はkである。…

問題 C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder コード import java.util.Scanner; public class Main { public void solve() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] a = new int[N]; int[] b = new int[…

問題 Problem - C - Codeforcescodeforces.com 解法 h[i]->a[i]になるまでの時間first[i]とa[i]->a[i]の時間cycle[i]を取っておく。求める時間secはsec=first[i]+cycle[i]*zのような形になるので、ゴリ押しでループさせていけば良い。（それでも間に合う）se…