コーナーケース
異常コーナーケース祭りのやばい問題だった 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。このグラフの頂点 にそれぞれ駒 が置いてある。次の操作を繰り返す。 駒 のうちの一方を選ぶ 選んだ駒を隣接する頂点のいずれかに動…
ずっと、「2 個分開いているかっこについて、1 個閉じてから、また 1 個開く」というパターンを見落として、WA 12 個がとれなかった！！ 問題へのリンク 問題概要 1 - 20 - 13 + 14 - 5 のような、 個の正の整数を「+」「-」で連結した計算式が与えられる。…
で解けた！ 同じ値が連続する場合の対処に苦慮した。 問題へのリンク 問題概要 強さが のスライムが一列にこの順に並んでいる。 に対して、次の問に答えよ。 【問】 初期状態で左から 番目にいるスライムが高橋君である。高橋君が下記の行動を好きな回数だけ…
二重頂点連結成分分解して得られる Block-Cut 木のクエリに答えていく問題。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。次の 回のクエリに答えよ。 【クエリ】 各クエリでは 2 頂点 が与えられる。 個の頂点のうち、次の…
とても面白かった。場合分けを詰め切るが大変だった。 問題へのリンク 問題概要 橋がただ 1 つだけ存在するような連結で単純な無向グラフをハシポンとよぶ。 頂点数 、辺数 の連結で単純な無向グラフが与えられる。このグラフに辺を追加することで、ハシポン…
方針を立てるのは難しくないけど、とにかく重たい問題だった。 問題へのリンク 問題概要 人 に対して合計 票が集まった。これらの人のうち条件「自分よりも多くの票を集めた人が 人未満」を満たす人が当選となる。 票のうち途中まで開票されて、各人 には 票…
で場合分けする系！ 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす最小の整数 （）を求めよ。(存在しない場合は -1。） 【条件】 を 進法表記したときの桁の和が である 制約 考えたこと が小さい範囲は愚直に調べればよさそうだ。 があ…
同じ文字が連続するかどうかを判定するのは、しばしば見かけますね。ラストに注意！ 問題へのリンク 問題概要 "salty" または "sweet" からなる 個の文字列 がこの順に与えられる。 "sweet" が 2 回連続すると、それ以降の文字列を受け入れられなくなる。す…
制約が と大きいので、ちゃんと整数論的処理をしないといけない！ 問題へのリンク 問題概要 以上 以下の整数のうち、 の倍数は何個あるか？ 制約 考えたこと 制約が と極めて大きいので探索手法で解くことは難しい。数学的に求めることを考える。 まず、「 …
個から 個を選ぶ設定の問題！ 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…
というコーナーケースにやられた！ 問題へのリンク 問題概要 整数 が与えられる。 を で割った余りの一の位の値を求めよ。 (マルチテストケース) 制約 考えたこと まず最初に考えたのは「全体を で割った世界」で考えれば良いということ。 このことを正当化…
えぐいコーナーケースに注意！ でもサンプルにあるね。 問題へのリンク 問題概要 財布に 円玉が 1 枚以上入っています。 財布に入っている合計金額がちょうど 円であるようなことが、あり得るかどうかを判定してください。 制約 考えたこと 基本的には「 が …
面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…
ちょっと難しい問題。 問題へのリンク 問題概要 3 文字の 'R' と 'S' のみからなる文字列 が与えられる。 において、'R' が最大で何個連続しているかを答えよ。 解法 ありうる文字列は 通りあることに注意しよう。よって、すべての文字列を調べることができ…
とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…
伝説の誤差問題！！ 誤差について学べる、とても教育的な問題。 問題へのリンク 問題概要 人がコイントスをしました。各人には と番号がついています。 人目は、 回表が出て、 回裏が出ました。 人目のコイントスの成功率は と定義されます。 人 の番号を、…
怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…
意外とややこしい問題。 ラウンド目の成績によっては、これまでの暫定の最大スコアと最小スコアが変わるかもしれないという点に注意！ 問題へのリンク 問題概要 ラウンドの試験が行われる。各ラウンドの得点は 0 以上 100 以下の整数値である。全ラウンドの…
すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…
旧 ABC の C 問題の中でも、個人的に最難だと思う問題！ 現代の ABC で出題されても水色 diff になると思う。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の各文字を並べ替えてできる文字列 のうち、 となる が 個以下であ…
「要するに o の最長連続箇所を求めればいい (ただし例外あり)」って感じに、シンプルに整理する力が問われる問題！ 問題へのリンク 問題概要 正の整数 に対して、 レベル のダンゴ文字列とは、以下の条件を満たす文字列である。 o と - からなる長さ の文字…
floor sum のいい感じの練習問題！ 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単…
久しぶりに bit ベクター高速化を使った。デバッグがしんどかった。 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。今、次の操作をちょうど 回実行する と を選ぶ と とを swap する 操作実行後の の値の最大値を求めよ。 制約 考えた…
面白かった！ ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…
ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…
競プロ典型90問の問題 001 の類題。「最大値の最小化」をする二分探索の典型問題ですね。 問題へのリンク 問題概要 二次元平面上に 個の円が与えられます。またそれらとは別に 個の点が与えられます。円同士は互いに交わることはなく、点が円に包含されるこ…
発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …
なぜか埋め込みにこだわってしまい、本番 AC できなかった... 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす最大の正の整数 を求めよ (存在しない場合は -1、無限個存在する場合は -2)。 確率 % で表が出るサイコロを 回振るとする 表が出…
番兵を入れるとかすれば、怖いケースをあらかじめ除去できそう 問題へのリンク 問題概要 左右方向一列に 個のマスが並んでいます。 この 個のマスのうち、マス の 個のマスは青色で、それ以外のマスは白色です。 あなたは一回だけ、正整数 を一つ選んで幅 の…
