各要素ごとに独立
操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。 問題へのリンク 問題概要 問題画像そのままを 解法 1: 自分のやつ 僕が最初に考えたことは、例えば 「最初…
何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…
嘘貪欲は一瞬脳裏によぎり、それを振り払って問題を解いてた。発想はこれの「後ろから解く」のに似ている。 drken1215.hatenablog.com 問題へのリンク 問題概要 × のグリッドのあるマスにロボットが置かれている。先手と後手はそれぞれ長さ の自分の文字列 …
面白かった 問題へのリンク 問題概要 100 桁以下の整数 が与えられる (文字列型で受け取るのがよさそう)。 も も十進法表記で '4' が登場しない を満たすような整数 の組を 1 つ求めよ。 制約 < < 考えたこと 繰り上がりを考えると面倒なので、繰り上がりが…
これも場合分けを丁寧に... 問題へのリンク 問題概要 高橋君は無限に広い 2 次元平面上に住んでいて、N 日間の旅行をします。 高橋君の旅程は長さ N の文字列 S であり、はじめは家にいます。 日目には、 S[i] = 'N' なら北へ S[i] = 'W' なら西へ S[i] = 'S…
完全グラフはどのように向きづけしてもハミルトンパスが存在するというね！！！ その証明はすごく楽しいと思う！！！ 問題へのリンク 問題概要 頂点数 の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して 頂点 i から頂点 j …
回文な問題リストに！！！ 問題へのリンク 問題概要 × のグリッドが与えられ、各セルには 0 か 1 の値が書かれている。 今、縦方向と横方向に切れ目を入れて、4 つの長方形に分けて、それぞれの長方形を 180 度回転させる操作を行う。 このときに、各行各列…
F2 線形代数大好き！ 問題へのリンク 問題概要 個の整数 の部分集合を選んで XOR 和を にする方法のうち、 個の区間 [ ] () について 区間の中から選ぶ個数は偶数個か奇数個かが指定される という制約を満たすものが何通りあるか求めよ。 制約 考えたこと 実…
積分した 問題へのリンク 問題概要 サイズ の長方形の紙と、それよりサイズの小さいサイズ の長方形の紙が 2 枚あります。 2 枚の小さいサイズの紙を、それぞれ、大きいサイズの紙の中に包含される範囲内でランダムに配置します (その位置は連続量)。 このと…
こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…
ゆかたゆたんと一緒に解いたん。 今後まだ解いてない様々な 500 点問題について何がポイントになっているのかをブログ書きながら明らかにして行きたい。500 点問題の苦手意識を克服するぞい。 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。…
素因数分解 & 重複組合せ を勉強できる、すごく教育的問題だった！！！ 問題へのリンク 問題概要 (ABC 110 D) 整数 が与えられる。 を満たす整数の組 () が何通りあるか、1000000007 で割った余りで求めよ。 制約 解法 素因数分解っぽいテーマの問題。こうい…
