けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JAG

AOJ 2297 Rectangular Stamps (JAG 夏合宿 2011 day2-H) (450 点)

状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…

AOJ 2584 壊れた暗号生成器 (ICPC 模擬国内 2014 C) (400 点)

BNF が書かれているので、LL(1)文法を再帰降下とかするのが標準みたいだけど、ad-hoc にスタックでなんとかしてしまった 問題へのリンク 問題概要 以下の BNF によって定義された文字列が与えられる。 <Cipher> ::= <String> | <Cipher><String> <String> ::= <Letter> | '['<Cipher>']' <Letter> ::= '+'<Letter> | '-'<Letter> | 'A' | 'B' |</letter></letter></letter></cipher></letter></string></string></cipher></string></cipher>…

AOJ 2403 敵の敵は味方 (JAG 模擬国内 2012 E) (550 点)

TLE が厳しかった... 問題へのリンク editorial 問題概要 頂点数 の単純無向グラフ が与えられる (連結とは限らない)。各頂点 には重み がついている。 頂点 1 を含む の安定集合をすべて考えたときの、安定集合中の頂点の重もの総和の最大値を求めよ。 制約…

AOJ 2295 Power of Power (JAG 夏合宿 2011 day2-F) (550 点)

コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…

AOJ 2304 Reverse Roads (JAG 夏合宿 2011 day3-E) (450 点)

最大流問題の構造についての理解を問ういい感じの問題! 問題へのリンク 問題概要 頂点数 、辺数 の単純有向グラフが与えられる (すべての辺の容量は 1)。2 点 間の最大フロー (辺素パスの本数) について考える。 今、いくつかの辺を選んで向きを反転するこ…

AOJ 2116 Subdividing a Land (JAG 冬合宿 2007 E)

Pell 方程式!!! 問題へのリンク editorial (day2-E) 問題概要 (意訳) 正の整数 が与えられる。 を正の整数として、 の値が最小となるような を 1 つ求めよ。 制約 考えたこと が平方数のときは として、 が答えとなる (最適値は 0)。 が平方数でないとき…

AOJ 2638 Hyperrectangle (JAG 夏合宿 2014 day2-J) (550 点)

りんごさんセット!!! 問題へのリンク 問題概要 次元空間において () を満たす部分の体積を とすると は整数値となる。この整数値を 1000000007 で割ったあまりを求めよ。 制約 考えたこと 最初は色々迷走していた。三次元の場合を考えていて思っていたの…

AOJ 2858 Prime-Factor Prime (JAG 模擬地区 2017 C) (350 点)

貴重な区間篩の問題 問題へのリンク editorial 問題概要 2 つの正の整数 が与えられる。以下の条件を満たす整数 の個数を求めよ。 の相異なる素因数の個数が素数個 制約 考えたこと が小さいので、それを活かした解法が考えられそう。具体的には区間篩が使え…

AOJ 2566 Restore Calculation (JAG 模擬地区 2013 B) (350 点)

これが生まれて初めての作問だった!!! AOJ-ICPC で ☆4 個ついてて嬉しい! 問題へのリンク editorial 問題概要 虫食算が与えられる。解の個数を 1000000007 で割ったあまりを求めたい。 より正確には長さ の 3 個の文字列 が与えられる。これらは '?' か …

AOJ 2863 Separate String (JAG 模擬地区 2017 H) (500 点)

めちゃくちゃ面白かったし勉強になった! 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…

AOJ 2681 Parentheses (JAG 春コン 2014 E) (500 点)

めちゃくちゃ面白かった! 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…

AOJ 2679 Decoding Ancient Messages (JAG 春コン 2014 C) (700 点)

多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…

AOJ 2677 Breadth-First Search by Foxpower (JAG 春コン 2014 A) (400 点)

LCA ライブラリを持っていれば書くだけ! 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…

AOJ 2678 Cube Coloring (JAG 春コン 2014 B) (450 点)

頭整理するのが大変だった 問題へのリンク editorial 問題概要 個の格子点 (、、) がある。 これらの格子点を以下のルールに則って 色 () で塗る。 点 の、 とのマンハッタン距離が であるとき 点 を、色 % で塗る 各 について、その色で塗られた格子点が何…

AOJ 2726 Black Company (JAG 夏合宿 2015 day4-J) (500 点)

素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…

AOJ 2904 GuruGuru (JAG 夏合宿 2018 day3-A) (200 点)

英文だし、題意をちゃんと読み解くのがちょっと大変 問題へのリンク editorial 問題概要 L と R のみから構成された文字列 が与えられる。ロボットは最初北方向を向いている。文字列 を左から順番に読んで次のように処理していく。 L のとき、ロボットは 90 …

AOJ 2333 僕の友達は小さい (JAG 夏合宿 2010 day2-D) (500 点)

これ面白い!! 問題へのリンク editorials 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選ぶ方法のうち、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 選んだ数の総和は 以下である 選んだ数の総…

AOJ 2376 DisconnectedGame (JAG 冬合宿 2010 day3-H) (600 点)

こないだの ARC でめっちゃ似た問題が出たので!これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…

AOJ 2385 Shelter (JAG 冬合宿 2010 day4-G) (700 点)

ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…

AOJ 2160 Voronoi Island (JAG 夏合宿 2009 day2-F) (450 点)

ボロノイ図 問題へのリンク editorials 問題概要 頂点の凸多角形と、その内部に 個の点が与えられる。それらの各 個の点に対して、以下の問に答えよ。 凸多角形のうち、その点に最も近い領域の面積を求めよ 制約 考えたこと まさにボロノイ図を求めよ、とい…

AOJ 2600 Koto Distance (JAG 夏合宿 2013 day2-A) (250 点)

面白かった 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの各点 に対し、 を満たす点 に電波が届く。 から までの長方形区間全体に電波が届くかどうかを判定せよ。 制約 考えたこと 全体を覆っているとき、以下のいずれかは成立しているこ…

AOJ 2630 Dictionary (JAG 夏合宿 2014 day2-B) (550 点)

最初は「え!? i 行目の文字列情報がないと i+1 行目以降のことを考えられなくない?」となってしまって、途方に暮れてしまった 問題へのリンク 問題概要 個の文字列 があって、それぞれいくつかの文字は '?' で隠されている (したのは の例) '?' 全体をア…

AOJ 2574 Magical Switches (JAG 模擬地区 2013 J) (900 点)

枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…

AOJ 2972 All your base are belong to us (JAG 夏合宿 2019 day1-F)

今日の ABC 151 F で、「三分探索」とか「山登り法」とか聞いたので!!! 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。 今、好きな位置に点を打って、その点から 個の点との距離のうち、大きい順に 個の総和をとる。 上手に点を打ったとき…

AOJ 2378 SolveMe (JAG 冬合宿 2010 day3-J) (1200 点)

伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…

AOJ 2439 箱根駅伝 (JAG 夏合宿 2012 day3a-F) (600 点)

sky さんの提唱した、代々伝わる名問題!!! 問題へのリンク 問題概要 人の選手が箱根駅伝を走っている。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示される。 ある中継所を 番目に通過したそれぞれの選手について、前…

AOJ 2712 Escape (JAG 夏合宿 2015 day2-G) (500 点)

こどふぉでまったく同じ問題が出た!!! 始点の入力の仕方が異なるのみ (こっちでは始点はノード 1 に固定、こどふぉでは始点 s を入力で与える) drken1215.hatenablog.com #include <iostream> #include <vector> #include <queue> using namespace std; int N, M, S = 0; vector<long long> w;</long></queue></vector></iostream>…

AOJ 2708 ABC Gene (JAG 夏合宿 2015 day2C) (300 点)

こういうの好き。操作によって実現できるかどうかを問う問題は全体的に好き 問題へのリンク 問題概要 文字列 "ABC" に対して以下の操作を好きな回数だけ行うことで、所望の文字列 S に変形できるかどうかを判定せよ。 A, B, C のいずれかの文字を選び、文字…

AOJ 2386 Sightseeing Tour (JAG 冬合宿 2010 day4-H) (250 点)

完全グラフはどのように向きづけしてもハミルトンパスが存在するというね!!! その証明はすごく楽しいと思う!!! 問題へのリンク 問題概要 頂点数 の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して 頂点 i から頂点 j …

AOJ 2624 Graph Automata Player (JAG 夏合宿 2013 day4-F) (550 点)

グラフに行列は付き物!!! 問題へのリンク 問題概要 頂点の有向グラフが与えられる。自己ループを含み得るが、多重辺は含まないことが保証される。 各頂点に 0 か 1 の値が割り振られている (が、その値がわからない)。以下の操作を 回行った後の各頂点の…