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

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

ICPCアジア

AOJ 1208 Rational Irrationals (ICPC アジア 1999 A)

Stern-Brocot 木がちょうどよく使える 問題へのリンク 問題概要 正の整数 が与えられる。分子・分母がともに 以下の正の整数であって、既約分数であるような分数の集合を と表すことにする。 を満たす最大の の要素 を満たす最小の の要素 をそれぞれ求めよ…

AOJ 1254 Color the Map (ICPC アジア 2004 G) (450 点)

本質的には彩色数を求めるだけだけど、幾何パートがちょっと面倒... 問題へのリンク 問題概要 二次元平面上に 個の多角形領域 (すべて単純) がある。各領域はそれぞれある国に属している。異なる多角形領域が同一の国に属していることもある。今、国ごとに「…

AOJ 1350 There is No Alternative (ICPC アジア 2014 F) (450 点)

これ好き!!! 問題へのリンク 問題概要 頂点数 、辺数 の、連結な重み付き無向単純グラフ が与えられる。 このグラフの「最小全域木」はさまざまなものが考えられるが、そのすべてに含まれるような辺の集合を考える。 その集合の要素数と、その集合に含ま…

AOJ 1308 Awkward Lights (ICPC アジア 2010 D) (550 点)

ライツアウト系の典型題 問題へのリンク 問題概要 × のグリッドと正の整数 が与えられる。各マスは 0 か 1 の値が振られている。今、以下の操作を好きな回数だけ行うことで、すべてのマスの値を 1 にしたい。それが可能かどうか判定せよ。 マスを 1 つ選んで…

AOJ 1328 Find the Outlier (ICPC アジア 2012 D) (450 点)

連立方程式の練習。多項式補間でも解ける。誤差がきつい。 問題へのリンク 問題概要 次多項式 がある (係数はわからない)。 個の点 の値がわかっている...はずだったが、そのうちの 1 個については間違った値が出力された状態で入力が与えられる。どれが間違…

AOJ 1391 Emergency Evacuation (ICPC アジア 2018 C) (300 点)

結構好き!ソートすることが本質の問題としていい感じな気がする。 問題へのリンク 問題概要 下図のような「中央の通路とそこから横に伸びた乗り物に乗客がどこにいるかを表した地図」が与えられる。乗客は 人いる。各乗客は 1 秒かけて 1 マス移動できる。…

AOJ 1390 Arithmetic Progressions (ICPC アジア 2018 B) (300 点)

面白かった 問題へのリンク 問題概要 個の整数 が与えられる。この中から最大個数の整数を選んで、それを小さい順に並べたときに等差数列となるようにせよ。 制約 考えたこと すごく DP っぽい雰囲気の問題。イメージとしては dp[ i ] := i 番目の要素が最後…

AOJ 1392 Shortest Common Non-Subsequence (ICPC アジア 2018 D) (500 点)

ARC 081 E - Don't Be a Subsequence の文字列が 2 個になったバージョン! 問題へのリンク 問題概要 2 つの '0' と '1' で構成された文字列 S, T が与えられる。 S の部分文字列でも T の部分文字列でもないような文字列のうち長さが最小のものを求めよ。複…

AOJ 1393 Eulerian Flight Tour (ICPC アジア 2018 E) (700 点)

面白い!!!!!!! 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる (連結とは限らない)。 このグラフに何本かの辺を付け加えることで「連結なオイラーグラフ」にすることができるかどうかを判定し、できるならば一例を示せ。ただし多重辺…

AOJ 1399 Sixth Sense (ICPC アジア 2018 K) (500 点)

「辞書順最大」という条件さえなければ典型的な Greedy マッチングではあるね。「辞書順最大」になっても頑張れば基本に忠実にできる。ややこしいけど頑張ればできる感じかな。。。 問題へのリンク 問題概要 人対 人の対戦割当を決めたい。敵が 1 回戦、2 回…

AOJ 1276 Prime Gap (ICPC アジア 2007 B) (150 点)

素数砂漠なん!!! 問題へのリンク 問題概要 整数 が与えられる。 を含む素数砂漠 (連続する合成数) の長さを求めよ。 すなわち、 以上の最小の素数と、 以下の最大の素数との差を求めよ。 制約 解法 エラトステネスの篩で予め 2000000 くらいまでの整数に…