めっちゃ面白い問題！ 問題へのリンク editorials 問題概要 個の直方体がある。 番目の直方体は の形をしている。 今、これらの直方体からいくつかを選んで積み木を作る。このとき、奥行き方法は必ず長さが になるようにする。 縦または横方向については、 …

Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…

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

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

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

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

伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…

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

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

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

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

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

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

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

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

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

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

ランダムウォークな問題！ 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

ロリハそのものな問題！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…

この問題の原案やってました！高校の頃、時刻表同好会の友達から 「f(n) = n15 を 15 で割った余りとすると任意の整数 n に対して f(f(n)) = n になるんだけど、これって暗号の危機じゃない？」 というメールを受け取って、あれこれ考えたことがキッカケにな…

面積二等分系問題、こないだ ICPC アジア 2019 にも出ていた。そっちは超むずいけど、こっちは簡単。 問題へのリンク 問題概要 頂点の凸多角形が与えられる。以下の条件を満たす点 P を求めよ: P を通る任意の直線によって、凸多角形は面積の等しい 2 つの凸…

最大 22 頂点のグラフの彩色数を求める問題 問題へのリンク 問題概要 本の折れ線が与えられる。折れ線に対応した 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。 このグラフの彩色数を求めよ。 制約 解法 前半の幾何は虚無。実質的…

一目見て bitDP なのはわかるのだけど、手こずった...... 問題へのリンク 問題概要 匹の猫をステージ に順番に送り込む 猫 がステージ をクリアできる確率は 猫 がステージ をクリアしたら、次のステージ もその猫で挑まなければならない 猫 があるステージ…

グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…

人工的過ぎる設定であまり自然じゃない問題だけど、整数の整除についての注意点を学べる教育的良問ですね。 問題へのリンク 問題概要 整数 が与えられる。 を 回二乗した数より大きい最小の素数を とする。 を で割ったあまりを求めよ。 制約 < 1000 考えた…

構文解析練習第三弾。AOJ-ICPC 350 点。 問題へのリンク 問題概要 (5-3*4)*(0-2+1) のような以下の BNF で定義される計算式が与えられる: <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | * ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優</op></expr></op></expr></number></expr></expr>…

「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。

これ面白い！！！！！！！！ 好き！！！！！！！ 問題へのリンク 問題概要 平面上に 個の点の座標 と、それらを結ぶ 本の線分がある。 線分のある部分は通過ができないので、線分に囲われた領域とその外側の領域とは行き来することができない。 そこでいくつ…

問題へのリンク 問題概要 整数 があたえられる。 進法で有理数 p/q を小数で表したときに有限小数となるような最小の 2 以上の整数 を求めよ。 制約 < < 考えたこと とりあえず p/q を約分しておく。 そして、q を素因数分解したときの、指数部を全部 1 にし…

AOJ-ICPC で無作為に問題を選んで実装する練習をした。あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があった。。。 問題へのリンク 問題概要 1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列と呼ぶ。 12Fizz4BuzzFizz78F…