問題 C: 転倒距離 - AtCoder Regular Contest 043 | AtCoderarc043.contest.atcoder.jp 解法 最初に転倒数を求めて、それの1/2だけ転倒するようにバブルソートする。バブルソートに一部は Binary Indexed Tree を使うと高速化できる。 コード import java.ut…

解法 TopCoder SRM 666 Div1 Medium SumOverPermutations - kmjp's blogkmjp.hatenablog.jp コード public class SumOverPermutations { private final int MOD = (int) 1e9 + 7; public int findSum(int n) { if (n == 1) { return 1; } // パスカルの三角…

解法 動的計画法（メモ化再帰）する。2回以上来る顧客をbitで管理しておく。 各タイミングの各bitにおいて、「来ない時」「来たから売る時」「来たけど売らない時」をそれぞれの計算して期待値を出せばいい。重要な式はこんな感じ。 double sell = dfs(time …

解法 左上のN*Mの長方形内の遇奇を考えれば良い。 i行目の和が奇数になるパターンを組み合わせて、i行目までの各列の和が最終的に奇数になるようにビットDPすれば良い。 コード import java.util.Arrays; public class MagicalGirlLevelTwoDivOne { private …

コード public class WalkOverATree { public int maxNodesVisited(int[] parent, int L) { int N = parent.length + 1; int[] dist = new int[N]; int max = 0; for (int i = 1; i < N; i++) { dist[i] = dist[parent[i - 1]] + 1; max = Math.max(max, dis…

解法 動的計画法（メモ化再帰）するだけ。（独力で解けたのでメッチャ嬉しい） コード public class PerfectMemory { private double[][] dp; public double getExpectation(int N, int M) { int C = N * M; dp = new double[C + 1][C + 1]; double ans = dp…

この記事は、下記プログラミング入門資料の一部です。プログラミング入門の資料 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com for ループとは forループとは、「N回繰り返し作業を行う」ということができるものです。コードとしては以下のように書きま…

この記事は、下記プログラミング入門資料の一部です。プログラミング入門の資料 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com 配列とは 整数の入れ物を1個作るときは int a; としました。2個作るときは int a; int b; のようにしました。このように入…

この記事は、下記プログラミング入門資料の一部です。プログラミング入門の資料 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com if文 if文とは、「もしAならBをして、そうじゃないならCをする」といった感じの条件分岐をするための機能です。 もしAなら{…

この記事は、下記プログラミング入門資料の一部です。プログラミング入門の資料 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com 文字列の宣言 整数の入れ物aを作るときは int a; でしたが、文字列の入れ物aを作るときは string a; とすることで作れます…

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

この記事は、下記プログラミング入門資料の一部です。プログラミング入門の資料 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com 入力 整数の入れ物 a に整数の入力を受け取るには cin >> a; とします。これは入力がなされる前にaが作られている必要があ…

この記事は、下記プログラミング入門資料の一部です。プログラミング入門の資料 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com 開発環境 paiza.ioにアクセスしましょう。デフォルトでC++のコーディングができるはずです。Web-based online coding envir…

概要 この記事群は下記イベントで行われる「プログラミング入門」のための資料として作成されました。【初心者向け】 CODE FESTIVAL 予選突破練習会 【非公式】 : ATNDatnd.orgプログラミング初心者が競技プログラミングに取り組むのに必要な、最低限の知識…

解法 SRM 512 Div1 Medium SubFibonacci - simezi_tanの日記d.hatena.ne.jp コード import java.util.Arrays; public class SubFibonacci { private final int MAX_F = 46; public int maxElements(int[] S) { long[] fib = new long[MAX_F]; fib[0] = 1; fi…

解法 ゲーム木的な考え方で深さ優先探索する。実は今までどのカードを取ったかを記録しておく必要はない。現状のビットを維持できる（現状のビットに影響のないカードを取ることができる）なら511を作って負けることはないので、ビットを増やしてしまうカー…

解法 lucky number の総数は大したことないので全列挙しておく。あとは全ての lucky number についてそれぞれの戦略を考えれば良い。 コード import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; public class TheLuck…

解法 文字列の長さ伸びたり縮んだりする気がするが、例えば右端にaddする場合は左端と同じ文字をaddするので、操作を重ねるごとに考えるべき文字列は縮んでいく。メモ化再帰で求めれば良い。 コード import java.util.Arrays; public class Palindromization…

問題 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を少しずつ小さくしていくようにすれ…

解法 SRM 508 div1 med:YetAnotherORProblem - mayoko’s diarymayokoex.hatenablog.com無理ゲー臭がすごい。 コード public class YetAnotherORProblem { private final long MOD = 1000000009; private final int MAX_D = 61; public int countSequences(lo…

問題 D: 金塊ゲーム - AtCoder Beginner Contest 008 | AtCoderabc008.contest.atcoder.jp 解法 AtCoder Beginner Contest 008 解説 from AtCoder Inc. www.slideshare.netいわゆるメモ化再帰。w1 コード import java.util.HashMap; import java.util.Scanne…

問題 C: 辞書式順序ふたたび - AtCoder Beginner Contest 009 | AtCoderabc009.contest.atcoder.jp 解法 前の方から貪欲に決めていく。 コード import java.util.Arrays; import java.util.Scanner; public class Main { public void solve() { Scanner scan…

解法 SRM564 Div1 Medium "AlternateColors2" - WARushekaing.hatenablog.comこのページの別解がすごすぎた。 コード public class AlternateColors2 { public long countWays(int n, int k) { long ans = 0; for (int red = 1; red <= k; red++) { int notr…

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

解法 SRM 507 Medium CubePacking - simezi_tanの日記d.hatena.ne.jp SRM 507 div1 med:CubePacking - mayoko’s diarymayokoex.hatenablog.com最低でもNs+Nb*L*L*Lは必要だが、L*L*Lを1列にNb個積み上げて、そこに1*1*1のNs個を出来るだけ平たく詰めば条件を…

解法 問題文通りに分配していけばいいが、全員同じになったら後は等分配するだけになるので、ループする必要はない。 コード import java.math.BigInteger; import java.util.Arrays; import java.util.PriorityQueue; public class TheJackpotDivOne { publ…

解法 SRM 506 div1 med:SlimeXGrandSlimeAuto - mayoko’s diarymayokoex.hatenablog.com街aから街bに移動する時、街cにある車を使うと、a->cを歩き、c->bを車で移動する。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Pr…

解法 TopCoder SRM 505 Div1 Medium SetMultiples - simezi_tanの日記d.hatena.ne.jp[C, D]の中でC*2 コード public class SetMultiples { public long smallestSubset(long A, long B, long C, long D) { C = Math.max(C, D / 2 + 1); A = Math.max(A, B / …