はじめに この記事は，競技プログラミング初心者が CODE FESTIVAL 2015 の予選を突破して本選に出場するためには，どのような準備をしたら良いのかということを，僕が考えた個人的な記事です．これを読んで行動して酷い目にあっても怒らないでください． COD…

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

解法 メモ化再帰。「あっ！この問題SRMで見たことある！」感がすごい。TopCoder SRM 509 Div1 Medium: PalindromizationDiv1 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com TopCoder SRM 511 Div1 Medium: FiveHundredEleven - 宇宙ツイッタラーXの憂鬱…

コード public class CorrectMultiplication { public long getMinimum(int a, int b, int c) { if (a > b) { int bb = b; b = a; a = bb; } long ans = Long.MAX_VALUE; for (int A = 1; A < 1000000; A++) { long B = c / A; for (int d = -5; d <= 5; d++…

コード import java.util.Arrays; import java.util.HashSet; public class RangeSquaredSubsets { public long countSubsets(int nlow, int nhigh, int[] x, int[] y) { int N = x.length; int[] sX = Arrays.copyOf(x, N); int[] sY = Arrays.copyOf(y, N)…

解法 SRM520 Div1 Medium(500) SRMIntermissionPhase - 赤コーダーになりたいd.hatena.ne.jpDPする。総和をとるところで式を工夫して、問題数の少ない方から埋めていくとO(MAX_P)で計算することができる。 コード public class SRMIntermissionPhase { priva…

解法 桁DPの強いバージョン。深さ優先探索で1文字ずつ足していった時に、C個の文字列を含む状態になるかどうかをメモ化して調べれば良い。文字列の後ろl文字がとwords[i]の前l文字と一致している時に、文字列に1文字cを追加したら何文字が一致するようになる…

解法 愚直オブザイヤー。お前その解法が通っちゃダメだろ……！！ コード import java.util.Arrays; public class ConvexSequence { public long getMinimum(int[] a) { int N = a.length; int[] b = Arrays.copyOf(a, N); while (true) { boolean end = true;…

解法 SRM 517 div1 med:AdjacentSwaps - mayoko’s diarymayokoex.hatenablog.com個人的にはこれと一緒だと思った。TopCoder SRM 666 Div1 Medium: SumOverPermutations - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com コード import java.util.Arrays; p…

問題 読解問題は無理なのでkmjp先生の訳を見た。TopCoder SRM 516 Div1 Medium RowsOrdering - kmjp's blogkmjp.hatenablog.jp コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class RowsOrdering { pr…

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