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

問題 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である。…

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

問題 Problem - D - Codeforcescodeforces.com 解法 Z Algorithm を使って文字列の各位置における最長の一致prefixを計算しておく。文中で文字列が交差した際に、計算した条件に合わなければ0を返せば良い。 コード import java.util.Scanner; public class …

問題 Problem - E - Codeforces 解法 下記リンクで丁寧に解説されている。 Codeforces Round #301 (Div. 2) E. Infinite Inversions - mayoko’s diary Codeforces #301 Div2 E. Infinite Inversions - kmjp's blogBinary Indexed Tree については以下の問題…

問題 Problem - D - Codeforcescodeforces.com 解法 (r,s,p)から(r-1,s,p),(r,s-1,p),(r,s,p-1)に遷移するので、渡すDPを書く。 コード import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(…

問題 Problem - E - Codeforcescodeforces.com 解法 まずダイクストラしてスタートからの距離を求めておく。あとは、スタート地点に戻っていくイメージで必要な道を貪欲に集めていけば良い。 コード import java.util.ArrayList; import java.util.Arrays; i…

問題 Problem - D - Codeforcescodeforces.com コード import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] people = ne…

問題 Problem - C - Codeforcescodeforces.com 解法 i+1番目の木にとっては、i番目の木が左側に倒れているか否かが分かれば良いので、渡すDPを書く。 コード import java.util.Scanner; public class Main { public static void main(String[] args) { Scann…

問題 Problem - C - Codeforcescodeforces.com 解法 考えなければならないことは以下の2点のみ。 ゴールに辿り着けるのか 幅優先探索で調べれば良い。 最短距離で辿り着ければ良いので、一度通ったマスの情報は保存しなくて良い。 ゴールに辿り着けたとして…

問題 Problem - C - Codeforces 解法 yukicoder No. 176 の解法がまるごと流用できる。yukicoder No. 176: 2種類の切手 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com コード import java.io.IOException; public class Main { public static void main…