AOJ 2172 - Queen's Case

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2172 解法 ゲームの状態グラフにループがあるので、ただ DFS やるだけだとうまくいかない。 これは後退解析という手法で解けて、ど典型なので知らなかったら覚えてしまってよい(どの問題…

AOJ 2587 - Elevator Hall Number

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2587 解法 桁DPしようと思ったが、遷移がうまく書けないので困った。 そこでオートマトンをイメージする。 結論を言うと、a[i] の値で NFA を作ってから DFA に変換し、その上で DP する。…

AOJ 1317 - Weaker than Planned

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1317 解法 普通のバックトラックで解ける。 バックトラックするときは、どういう順番で探索すると枝刈りが起こりやすいかを考える必要がある。 今回なら、文字の種類数が多い方を先に考え…

AOJ 1307 - Towns along a Highway

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1307 解法 こういうのは確定できるところからさせるもの。 とりあえず一番遠いところは unique に定まるので確定させる。 次は、残ってる d の中で最も大きい値を選ぶ。 こいつは、明らか…

AOJ 1322 - ASCII Expression

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1322 解法 今の左端と、上下の区間を持ちながら構文解析を書く。 base の位置は左から見ていって、初めて空白以外が現れた行としてよい。 分数表記のときに余計な space がたくさん入るこ…

AOJ 2017 - Karakuri Doll

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2017 解法 行きの位置、向き、戻りの位置、向きを同時にもって遷移するだけなんだけど、結構めんどくさい。 一番楽なのは DFS で1マスずつ動かしていくのだと思う。 曲がれるタイミングは…

AOJ 2623 - Optimal alpha beta pruning

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2623 解法 普通にαβ法をメモ化再帰でやるだけ。minimize も maximize も同じ。 dp[v][alpha][beta] := negamax(v, alpha, beta) で最善の選び方をした時の解子供の順番は next_permutation…

AOJ 2646 - Tournament

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646 解法 全探索を考えるところから。 n が小さくで列を愚直に持てるとしたら、次の全探索を考えるはず。 res(l, r, rank) := 区間 [l, r) における勝者の最終順位が rank になるときの最…

AOJ 2786 - Share the Ruins Preservation

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2786 解法 Andrew's Monotone Chain を左右からやっていくだけ。 有名な(?)蟻本の実装だと多角形の表現にするために半時計回りにやっているけど、今回はそんなことせずに、上側も下側も…

AOJ 2690 - Content Delivery

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2690 解法 各頂点について一番遠いところを貪欲に選ぶだけ。 一番遠いところへのパス以外はそこで切って、vector かなんかに突っ込んでおけばよい。 m がでかいけどどう考えても n^2 のオ…

AOJ 2743 - Land Inheritance

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2743 解法 全探索をちょっとだけ早くするだけ。 n n == 4 のときは、土地を使い切らない方法で最適なものがありうる。 具体的には螺旋っぽく配置するというもの。真ん中がぽっかり開いてる…

AOJ 2692 - ICPC Teams

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2692 解法 包除原理。 チームにしないといけない組は確定で組ませる。 また、チームにしてはいけない組のすべての部分集合に対して、その集合に含まれる組は確定でチームを組ませるとする…

AOJ 1628 - Floating-Point Numbers

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1628&lang=jp 解説 実装するだけ。 仮数部表現は 1 も含めた 53 bit で表現すると楽だと思う。 a を何回足せば仮数部に収まらなくなるかは簡単な式で O(1) で求まる。 それを今の値に足し…

AOJ 2604 - Pattern Language

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2604\ 解法 変数は 10 個しかないので、それぞれの変数を何桁にするか最初に全探索する。 すると、変数の桁ごとに、どの桁と対応するかを決定できる。 対応する集合を union find 木かなに…

AOJ 1388 - Counting Cycles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1388 解法 m つまり愚直にサイクルを探索しても、そこまで探索空間は大きくない。サイクル空間を考えるにしろ、n, m が大きすぎるので、小さくしたい。 よく考えると、次数が 2 以下の頂点…

AOJ 2686 - Unfair Game

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2686 解法 自明ケースからちょっとずつ難しくしていくのが良いと思った(実験しても良いかも)。 a == b 同じ条件なので Nim (grundy 数) に帰着可能。 ある山の石の個数を s とすると s %…

AOJ 2250 - Operator

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2250 解法 二分探索やるだけじゃーんとなってサンプルチェックして違うことが判明するやつ。見事に引っかかってしまった。良い性質がないか観察してみると、少なくとも可能かどうかの人数…

NEERC 2010 K - Graph Oddity

問題概要 n 頂点 m 辺の単純で連結な無向グラフが与えられる。n は奇数である。 deg(v) を頂点 v の次数とし、k を deg(v) の最大値以上で最小の奇数と定義する。 このとき、グラフを k 色以下で頂点彩色せよ。・制約 3 1 n は奇数 解法 n と k が両方奇数な…

AOJ 2861 RPG Maker

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2861 解法 典型構築だと思われる。 4n - 1, 4m - 1 であることが重要で、この制約のためにすべてのマスを回収するようなパスが存在する。 イメージとしては蛇のようにうねうねしながら移動…

AOJ 1382 Black or White

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1382 解法 いかにも DP の高速化をする見た目をしている。 DP を考える前に、操作を観察する。 色々実験などして考えてみると、 ある位置を3回以上塗るのは最適ではなさそう 2つの区間を違…

AOJ 1622 Go around the Labyrinth

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1622 解法 右手法かフロー(最大流)で解けるが、今回はフローで解く。 フロー解は割と一発ネタなところがある。まず、各マスを2つの頂点に倍化(入力ノード、出力ノード)し、これら2つの…

AOJ 2785 Escape from the Hell

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2785 解法 とりあえず C[i] については無視して考えてみる。 最終日に使うドリンクを決めたとする。このドリンクを k とする。 すると、L - a[k] をできるだけ早く達成したいということに…

DDCC 2018 D - DISCO!

問題文 https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d 解法 区間同士でうまくマージできるような形であればセグ木に乗せることができるので、とりあえずその方針で考えてみる。 2つの区間 A, B があって、それらをマージしたときに "D…

競プロでも使える C++ の便利機能

はじめに C++14, 17, 20 と規格が改定されていくにつれ、色々便利な機能が追加されています。 そのうちのいくつかは競プロであっても有用なのですが、特に最近始めた人のコードを読んでいるとほとんど使われておらずもったいないと感じることが多いです。 そ…

Codeforces Round #213 (Div. 1) D. Ghd

問題文 https://codeforces.com/contest/364/problem/D 解答 https://github.com/Suikaba/procon-solved/blob/master/Codeforces/Round200-249/Round213/Div1-D.cpp 感想 計算量と TL の割に配列サイズでかすぎない?

自分が書く今後の競プロ問題解説記事について

これまでは、難しいなと思った問題や AOJ で解説がない問題の記事をはてなに直接書いてきた。 しかし最近は解いたときのコードを git で管理するようになったので、今後は github の解答コードへのリンクを貼るようにしようと思う。 解説や考察メモはコード…

Lindström–Gessel–Viennot lemma

概要 格子点上で、n 組の始点と終点 $(a_1, a_2, \ldots, a_n), (b_1, b_2, \ldots, b_n)$ が定まっているとして、それらが交差しないようなパスの選び方をカウントできる定理である。($a_i$ をどの $b_j$ と対応付けるか、まで含めて。) 後にこの定理を用…

ACM-ICPC 2018 Asia Yokohama Regional 参加記

はじめに 2018年12月8, 9日に横浜で行われた ACM-ICPC 2018 Asia Yokohama Regional の参加記です。 プラクティス~懇親会あたりまでの話を大雑把にまとめようと思います。 チームについて 自分はチーム Zerokan_Sunshine として kazuma, nakano と一緒に出…

AOJ 2884 Tanka Number

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2884 解法 二分探索 + 桁DP ……ではなく貪欲に解く。 基本的に上の桁から順番に数字を確定させていって、 n 番目を超えないギリギリを選択する、というよくあるやり方。 当然だが各桁は小さ…

AOJ 2787 Pipe Fitter and the Fierce Dogs

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2787 解法 一番上の行のすべての家は special pipe 確定だから、(W + 1) / 2 > K なら不可能であり、それ以外は可能である。 それ以外については、一旦 special pipe を使わないとして考え…