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

解法 SRM 663 div1 easy:ChangingChange - mayoko’s diarymayokoex.hatenablog.comD円を作る方法のうち、消えるものをDPして求めると、答えを導き出すことができるが時間がかかりすぎてしまう。 for (int q = 0; q < Q; q++) { int v = valueRemoved[q];// …

解法 targetの文字列のうち、initialあるいはinitialの反転部分を見つけ、その前後のBの数が条件にあっているかどうか確かめる。1回以上Bによる反転操作がある場合、絶対に先頭にAは来ない（これで落ちた）。 コード public class ABBADiv1 { public String …

問題 B: アリの高橋くん - AtCoder Regular Contest 042 | AtCoderarc042.contest.atcoder.jp 解法 幾何ライブラリ貼るだけ。 コード import java.util.Scanner; public class Main { public void solve() { Scanner scanner = new Scanner(System.in); int …

問題 C: おやつ - AtCoder Regular Contest 042 | AtCoderarc042.contest.atcoder.jp 解法 最も安い1個については0円と見なすことが出来ると考える。商品を値段の降順でソートして高い方から見ていき、動的計画法で「高い方からn個目までみた時の、予算内で…

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

TCO15 Algorithm Round 2C の東京イベントで併せて開催されたハッカソンに参加してきました。作戦がかなりハマって賞金2000ドルゲット出来たので、自分用メモを残しておきます。 テーマ発表前 適当にチームを作る。@kenkoooo (ぼく), @fat_daruuuuma (Androi…

解法 dp(nターン目の時に)(山札の一番上にある数)の最大値を取るようにdpした。実は山札の一番上の数字さえ覚えておけば、一番上のカード以下のカードは出せないため、どのカードを出したかということを覚えておく必要はない。毎ターン「カードを出す」か「…

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

解法 TopCoder SRM 662 Div1 Medium ExactTree - kmjp's blogkmjp.hatenablog.jp コード import java.util.Arrays; public class ExactTree { private final int INF = 1 << 25; public int getTree(int N, int MOD, int R) { // dp[n][r]:= 頂点数nの木で、…

問題 A Holiday of Miss Brute Force | Aizu Online Judge 解法 x, y, t mod 6によって方向は定まるので、これらの(x,y,t%6)を頂点とする有向グラフを作り、ダイクストラする。 コード import java.util.ArrayList; import java.util.Arrays; import java.ut…

解法 高さでソートして、1番目を末尾、2番目を先頭、3番目を末尾、4番目を先頭、 ... とリストに挿入し、それを返せば良い。 コード import java.util.ArrayList; import java.util.Arrays; public class FoxesOfTheRoundTable { public int[] minimalDiffer…

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

問題 Problem - D - Codeforcescodeforces.com 解法 Codeforces #311 Div2 D. Vitaly and Cycle - kmjp's blogkmjp.hatenablog.jp コード import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; public class Main { private Ha…

問題 C: 双子と○×ゲーム - AtCoder Beginner Contest 025 | AtCoderabc025.contest.atcoder.jp 解法 AtCoder Beginner Contest 025 解説 from AtCoder Inc. www.slideshare.net コード import java.util.Scanner; public class Main { private int[][] b; pr…

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