アドホックに構文解析した。カッコ列の問題とみなして、stack で処理した。 問題へのリンク 問題概要 次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。 a[2147483647] a[0]=1 B[2] B[a[0]]=2 a[B[a[0]]]=3 a[2147…

アドホックにも実装できそうだけど、構文解析ライブラリで殴った！ 問題へのリンク 問題概要 0 以上 9 以下の整数値に対して「+」「×」で連結して得られる長さ の文字列 が与えられる。たとえば以下のような文字列が与えられる。 1+2*3+4 また、Bob がこの式…

重み付き Union-Find の練習問題！ 問題へのリンク 問題概要 個の値 があるが、それらの値がわからないので、特定したい。 次の 2 種類のクエリが 個、与えられるので順に処理せよ。 3 つの値 が与えられる。 であるという情報が与えられる。 2 つの値 を与…

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

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

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

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

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

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

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

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

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

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

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