すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…

「点がどの区間に属するか」は極めて典型的な問題で、それを二次元にしたバージョン！ 問題へのリンク 問題概要 二次元平面上で、左下の頂点が 、右上の頂点が であるような長方形状のケーキがあります。 このケーキ上には 個のいちごが乗っていて、 番目の…

一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。 問題へのリンク 問題概要 のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。 このグリッドに対して、次の操作を可能な…

これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…

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

何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…

嘘貪欲は一瞬脳裏によぎり、それを振り払って問題を解いてた。発想はこれの「後ろから解く」のに似ている。 drken1215.hatenablog.com 問題へのリンク 問題概要 × のグリッドのあるマスにロボットが置かれている。先手と後手はそれぞれ長さ の自分の文字列 …

これも場合分けを丁寧に... 問題へのリンク 問題概要 高橋君は無限に広い 2 次元平面上に住んでいて、N 日間の旅行をします。 高橋君の旅程は長さ N の文字列 S であり、はじめは家にいます。 日目には、 S[i] = 'N' なら北へ S[i] = 'W' なら西へ S[i] = 'S…

回文な問題リストに！！！ 問題へのリンク 問題概要 × のグリッドが与えられ、各セルには 0 か 1 の値が書かれている。 今、縦方向と横方向に切れ目を入れて、4 つの長方形に分けて、それぞれの長方形を 180 度回転させる操作を行う。 このときに、各行各列…

積分した 問題へのリンク 問題概要 サイズ の長方形の紙と、それよりサイズの小さいサイズ の長方形の紙が 2 枚あります。 2 枚の小さいサイズの紙を、それぞれ、大きいサイズの紙の中に包含される範囲内でランダムに配置します (その位置は連続量)。 このと…

こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…

くやしい 問題へのリンク 問題概要 個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて (), (), (), () をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。 各 について共通の を用いなければな…