AtCoder

技術室奥プログラミングコンテスト G: おおきなかずを作った

問題 tkppc.contest.atcoder.jp 解法 動的計画法で後ろから数字の桁数を決めていく。この時、s[i, k] と s[j, k] の文字列の大小関係を比較したいが、普通にやるとO(N)かかってしまう。そこでSA-ISを使うのが想定解法っぽい。 mayokoex.hatenablog.comが、SA…

Indeed なう A日程 D: Longest Path (木DP)

問題 indeednow-finala-open.contest.atcoder.jp 解法 木DP。 コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #incl…</stack></queue></list></vector></string></cmath></algorithm></iomanip></iterator></fstream></sstream></iostream></cstdio>

CODE FESTIVAL 2015 あさぷろ Hard A: 一次元オセロ

問題 code-festival-2015-morning-hard.contest.atcoder.jp 解法 1回もひっくり返されない区間iが存在する。この時、区間i-jと区間i+jは、それぞれj回ひっくり返されるので、ある区間を選んだ時にひっくり返される合計の回数は累積和で予め計算しておくこと…

AtCoder Beginner Contest 015 D: 高橋くんの苦悩

問題 abc015.contest.atcoder.jp 解法 DP コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include </map></set></stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>

AtCoder Regular Contest 046 D: うさぎとマス目

問題 arc046.contest.atcoder.jp 解法 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net組み合わせを高速に求める数論ライブラリを手に入れた。 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> using namespace std</map></set></queue></vector></algorithm></iostream>…

AtCoder Regular Contest 046 C: 合コン大作戦

問題 arc046.contest.atcoder.jp 解法 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> men_o</int></map></set></queue></vector></algorithm></iostream>…

CODE THANKS FESTIVAL 2015 G: カメレオン

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 ダイクストラやるだけ。 コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <tuple> #include <sstream> #include <typeinfo> #include <fstream> #include…</fstream></typeinfo></sstream></tuple></vector></set></algorithm></iostream></ctime></cstring></cmath></cstdio>

CODE THANKS FESTIVAL 2015 H: 穴あきケーキ

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 2次元の累積和をとる。こうすると長方形の中の累積和がO(1)で得られる。kenkoooo.hatenablog.com後はしゃくとりする。 コード ライブラリはmamekinさんのコピペです。 #include <cstdio> #include <iostream> #in</iostream></cstdio>…

CODE FESTIVAL 2015 予選B D: マスと駒と色塗り/Squares, Pieces and Coloring

問題 code-festival-2015-qualb.contest.atcoder.jp 解法 塗り終わった区間の[始点, 終点]を保持しおく。塗るときに合併される区間がある場合は合併していけば、保持する情報も少なくて済む。これのイメージで解いた↓kenkoooo.hatenablog.com コード import …

AtCoder Regular Contest 043 C: 転倒距離

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

AtCoder Beginner Contest 008 D: 金塊ゲーム

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

AtCoder Beginner Contest 009 C: 辞書式順序ふたたび

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

天下一プログラマーコンテスト2015予選A C: 天下一美術館

問題 C: 天下一美術館 - 天下一プログラマーコンテスト2015予選A | AtCodertenka1-2015-quala.contest.atcoder.jp 解法 http://tenka1.klab.jp/2015/explain/quala_c.htmltenka1.klab.jp隣り合った2マスが両方Bと違い、かつ、入れ替えればBと一致する場合、…

AtCoder Regular Contest 042 B: アリの高橋くん

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

AtCoder Regular Contest 042 C: おやつ

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

AtCoder Beginner Contest 025 C: 双子と○×ゲーム

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

AtCoder Beginner Contest 018 D: バレンタインデー

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

AtCoder Typical Contest 001 C: 高速フーリエ変換

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

AtCoder Regular Contest 038 C: 茶碗と豆(grundy数・セグメント木・二分探索)

問題 C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoderarc038.contest.atcoder.jp 解法 AtCoder ARC #038 : C - 茶碗と豆 - kmjp's blogkmjp.hatenablog.jp コード import java.util.Arrays; import java.util.Scanner; public class Main { public sta…

AtCoder Beginner Contest 023 D: 収集王(二分探索)

問題 D: 射撃王 - AtCoder Beginner Contest 023 | AtCoderabc023.contest.atcoder.jp 解法 二分探索でスコアを探索する。 コード import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scann…

AtCoder Beginner Contest 023 C: 収集王(片側全探索)

問題 C: 収集王 - AtCoder Beginner Contest 023 | AtCoderabc023.contest.atcoder.jp 解法 AtCoder ABC #023 : Python練習編 - kmjp's blogkmjp.hatenablog.jp コード import java.util.Scanner; import java.util.TreeSet; public class Main { private st…

AtCoder Beginner Contest 004 D: マーブル (最小費用流)

問題 D: マーブル - AtCoder Beginner Contest #004 | AtCoderabc004.contest.atcoder.jp 解法 AtCoder Beginner Contest 004 解説 from chokudai www.slideshare.netスタートと赤・緑・青のノードを結び、赤・緑・青と座標-500~500のノードを結び、これらの…

AtCoder Beginner Contest 022 D: Big Bang (幾何・凸包)

問題 D: Big Bang - AtCoder Beginner Contest 022 | AtCoderabc022.contest.atcoder.jp 解法 AtCoder Beginner Contest 022 解説 from chokudai www.slideshare.net外側の点を結んで、全ての点が内部か線上にあるような多角形を作る。(凸包というらしい)…

AtCoder Regular Contest 037 C: 億マス計算 (二分探索)

問題 C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder 解法 各a[i]の段のmid以下のa*bの数をカウントし、それがKとなるようにmidを二分探索する。 コード import java.util.Arrays; import java.util.Scanner; public class Main { public static vo…

AtCoder Beginner Contest #006 D: トランプ挿入ソート (二分探索・最大増加部分列)

問題 D: トランプ挿入ソート - AtCoder Beginner Contest #006 | AtCoder 解法 AtCoder Beginner Contest 006 解説 コード import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws Excep…

AtCoder Beginner Contest #005 D: おいしいたこ焼きの焼き方 (2次元の累積和)

問題 D: おいしいたこ焼きの焼き方 - AtCoder Beginner Contest #005 | AtCoder 解法 たこ焼き器について、二次元の累積和を求めておく。クエリに対して作れる長方形を全列挙し、その長方形を(x,y)だけ平行移動した時に、長方形内部の美味しさの合計を計算す…

AtCoder Beginner Contest 003 D: AtCoder社の冬 (包除原理・bit管理・動的計画法)

問題 D: AtCoder社の冬 - AtCoder Beginner Contest #003 | AtCoder 解法 ステップとしては、 R*C内のX*Yの取りうるパターンを調べる。 X*Y内のD+Lの取りうるパターンを調べる。 D+L内のDとLのパターンを調べる。 の3つをこなす必要がある。R*C内のX*Yの取り…

AtCoder Beginner Contest 021 D: 多重ループ (組み合わせ・モジュラ逆数)

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 1からnの中から重複を許してk個選ぶという問題に帰着できる。 を求めたいが、割り算をすると計算に時間がかかりすぎる。そこでモジュラ逆数を使う。モジュラ逆数 - Wikipedia コード impo…

Indeed なう A日程 D: Longest Path (木DP)

問題 D: Longest Path - Indeedなう(オープンコンテスト) | AtCoder 解法 ある頂点vに注目した時に、「vに入ってくる最大のパス」と「vから出て行く最大のパス」を計算する。この2つが同じパスにならないように、頂点はそれぞれ1度ずつしか注目しない。め…

AtCoder Regular Contest 036 C: 偶然ジェネレータ

問題 C: 偶然ジェネレータ - AtCoder Regular Contest 036 | AtCoder 解法 dp[pos][diff0][diff1]:= pos文字目まで見た時に、(0の文字数)-(1の文字数)の最大値がdiff0であり、(1の文字数)-(0の文字数)の最大値がdiff1である組み合わせの数とする。S[pos]='0'…

Indeedなう A日程 E: Page Rank

問題 E: Page Rank - Indeedなう(オープンコンテスト) | AtCoder 解法 最初に全社員のPage Rank を1.0としておき、定義にしたがって1000回ほど計算すると収束する。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Scanne…

ARC 036 D: 偶数メートル

問題 D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder 解法 0〜N-1と、N〜2N-1の2N個の街があると仮定する。 ノード数2NのUnion-FInd木を用意する。 xとyの間に敷設する道路の長さが偶数なら、xとy、x+Nとy+Nをuniteする。 奇数ならxとy+N、x+Nとy…

Indeedなう A日程 C: Optimal Recommendations

問題 C: Optimal Recommendations - Indeedなう(オープンコンテスト) | AtCoder 解法 dp[i][j][k]:= 能力i, j, k の人が行ける最高の報酬の会社として、 dp[i][j][k + 1] = Math.max(dp[i][j][k + 1], dp[i][j][k]); dp[i][j + 1][k] = Math.max(dp[i][j +…

ARC 032 C: 仕事計画 (動的計画法)

問題 C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder 解法 ある時刻time以降の仕事の最大数を考える。 コード import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; public class Main { private static final int MA…

Typical DP Contest G: 辞書順 (動的計画法)

問題 G: 辞書順 - Typical DP Contest | AtCoder 解法 dp[i][c]:= i文字目以降の部分列で文字cから始まるものの個数、とする。i=N-1から順々にdpを埋めていき、埋め終わったらそこから文字列を復元すれば良い。 コード import java.io.BufferedReader; impor…

Typical DP Contest F: 準急 (動的計画法)

問題 F: 準急 - Typical DP Contest | AtCoder 解法 (駅i+1で連続j+1回目の停車をする組み合わせ) = (駅iで連続j回目の停車をする組み合わせ)なので、愚直にやってもO(NK)で解ける。工夫して、 (駅i+1で停車する組み合わせ) = (駅iで停車する組み合わせ) + (…

Typical DP Contest E: 数 (動的計画法)

問題 E: 数 - Typical DP Contest | AtCoder 解法 下からi桁目まで見た時にj余る整数の数を記録しておく。この時、i桁目がNのi桁目以下になる数も記録しておく。 コード import java.util.Scanner; public class Main { private static final long MOD = 100…

ABC 020 D: LCM Rush

問題 D: LCM Rush - AtCoder Beginner Contest #020 | AtCoder 解法 // 最大公約数 static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } // 最小公倍数 static long lcm(long a, long b) { return a * b / gcd(a, b); } 最大公約数と最…

ABC 020 C: 壁抜け

問題 C: 壁抜け - AtCoder Beginner Contest #020 | AtCoder 解法 ゴールについた時の(歩数, 黒マスを通った回数)の組み合わせを記録しておき、それぞれについてxの最大値を求めれば良い。黒マスを通った回数は高々100なので、大した量にはならない。 コード…

Typical DP Contest D: サイコロ (動的計画法)

問題 D: サイコロ - Typical DP Contest | AtCoder 解法 サイコロを振った回数を1から少しずつ大きくしていく。それぞれの回数について、2の指数、3の指数、5の指数を数え、その状態になる確率を求める。 コード import java.io.IOException; import java.ut…

Typical DP Contest C: トーナメント (動的計画法)

問題 C: トーナメント - Typical DP Contest | AtCoder 解法 やるだけ。 コード import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] arg) { int K = nextInt(); int N = 1 << K; int[] rating = n…

Typical DP Contest B: ゲーム (動的計画法)

問題 B: ゲーム - Typical DP Contest | AtCoder 解法 お互いに最善を尽くす時、dp[i][j]の前の手はdp[i-1][j]またはdp[i][j-1]になっているはずなので、それで計算する。 コード import java.io.IOException; public class Main { public static void main(…

Typical DP Contest A: コンテスト (動的計画法)

問題 A: コンテスト - Typical DP Contest | AtCoder 解法 dp[i][j]:=i問目まででj点に到達できるかどうか、を保存しておき、dp[N][i]をカウントする。 コード import java.io.IOException; public class Main { public static void main(String[] args) { i…

Indeedなう(予選B) C: 木

問題 C: 木 - Indeedなう(予選B) | AtCoder 解法 やるだけ。やるだけだけどnew int[100000][100000]はMLEするので、別の方法を考える。 コード import java.io.IOException; import java.util.ArrayList; import java.util.PriorityQueue; public class Ma…

CODE FESTIVAL 2014 Middle B: 枕決め

問題 B: 枕決め - CODE FESTIVAL 2014 Middle | AtCoder 解法 高さhを1から少しずつ大きくしていく。 x[i]=hになる人iがいたら、y[i]をPriorityQueueに入れる。 PriorityQueueの中でy hの高さの枕をPriorityQueueの人に順番に配る。 ジョブスケジューリング…

CODE FESTIVAL 2014 Middle A: 身体バランス (ダイクストラ法)

問題 A: 身体バランス - CODE FESTIVAL 2014 Middle | AtCoder 解法 ダイクストラ。 コード import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; public class Main { public static void m…

Indeedなう(予選A)D: 15パズル(幅優先探索・枝刈り)

問題 D: パズル - Indeedなう(予選A) | AtCoder 解法 あるマス(i, j)の数字が本来あるべきマスとのマンハッタン距離を計算する。本来あるべきマスまで移動するのに最低でもマンハッタン距離分だけの手数がかかるので、他の数字についてもマンハッタン距離…

ARC 035D: 高橋くんとマラソンコース (セグメント木)

問題 D: 高橋くんとマラソンコース - AtCoder Regular Contest 035 | AtCoder 解法 チェックポイント間の経路数はものすごく大きくなるのでlogで保存しておく。クエリに対してチェックポイント間の経路数の和を返すので、和のセグメント木を作っておく。 コ…

AtCoder Regular Contest 035 C: アットコーダー王国の交通事情

問題 C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder 解法 まず最初のグラフでワーシャルフロイトして2点間の最短距離を出しておく。新しい道路が建設されるたびに最短距離マップを更新する。この際に、以下のようにするとで更新…