考察：独立に考えてよい
座標ごとに情報を整理するのは頻出！ 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている（各人が左右どちらを向いているかは文字列 で与えられる）。 各人が、その位置から、向いている方向に向かっ…
これ結構難しくて、嵌まる人は嵌まってしまうと思う！！ 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき：ポーション が現れる それを拾うかどう…
「x 軸と y 軸を独立に考えられる」と「主客転倒・寄与分解」の合わせ技！！ 問題へのリンク 問題概要 座標平面上に、 本の直線 と、 本の直線 がある。 これらの直線のうち 4 本を選んでできる長方形領域は 個あるが、それらの面積の総和を 1000000007 で割…
集計処理の応用問題 問題へのリンク 問題概要 一般に、文字列 からいくつかの文字を抜き出して、それを並び替えることによって文字列 を作れるとき、 から を作れるという。 英小文字からなる 個の文字列 が与えられる。 のいずれからも作れる文字列 のうち…
円環上の Zero-Sum Ranges!! 問題へのリンク 問題概要 円周上に 個の地点 がこの順に時計回りに並んでいる。地点 から地点 （ のとき とする）まで時計回りに移動するのに要する時間は である。 次の条件を満たす の個数を求めよ から時計回りに へと到達す…
意外と頭がこんがらがる 問題へのリンク 問題概要 人の人 がいて、人 の名字は 、名前は である。 各人にニックネームをつけたい。人 のニックネーム は または である かつ である任意の に対して、 かつ である という条件を満たす必要がある。このような…
集計処理系の良問！ 問題へのリンク 問題概要 英小文字からなる文字列 について、どの英小文字も登場回数が偶数回であるかどうかを判定せよ。 制約 解法 (1)：各文字について登場回数を見ていく まずは愚直な解法を考えよう。文字 = 'a', 'b', ..., 'z' につ…
面白い問題！ 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…
すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…
素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変 問題へのリンク 問題概要 種類のスライムがいる。 種類目のスライムは、サイズが であり、 体いる。 一般にサイズが であるスライムを 2 体合体させて、新たにサイズが のスライムを …
この辺りから難しくなって来てる。「 で合格・不合格」という条件をどのように適切に言い換えるかが問われている。 問題へのリンク 問題概要 電源が 個、モーターが 個、ケーブルが 個ある。電源は と番号づけられていて、モーターは と番号づけられていて、…
「点がどの区間に属するか」は極めて典型的な問題で、それを二次元にしたバージョン！ 問題へのリンク 問題概要 二次元平面上で、左下の頂点が 、右上の頂点が であるような長方形状のケーキがあります。 このケーキ上には 個のいちごが乗っていて、 番目の…
ちょっと面白い問題！ 競プロ始めたばかりの方々に、計算量のことを意識させるのに良い問題かもしれない。 問題へのリンク 問題概要 どの 2 つの値も互いに相異なるような、長さ の数列 が与えられる。 この数列 の異なる 2 要素の和として表せる値の中に偶…
色々な考え方ができる楽しい問題ですね！ 3 通りの解法を自分なりに咀嚼して整理しました。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 が の倍数となるような最小の整数 を求めよ。 制約 考えること：まずは素因数分解 この問題のように、「倍数…
一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。 問題へのリンク 問題概要 のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。 このグリッドに対して、次の操作を可能な…
バチャ中に TLE が取れなかった... で実装してしまっていたけど、 にする必要があったみたい。 問題へのリンク 問題概要 長さ の 0 以上の整数からなる数列 が与えられる。 0 以上の整数 を適切に定めて XOR で定まる数列 の転倒数が最小となるようにせよ。…
素因数分解ゲー！ 今なら ABC D あたりに出てきそう (実際に出てきた！) ジャッジページ 問題文 問題概要 正の整数 が与えられる。 が の倍数となるような最小の正の整数 を求めよ。 制約 解法 以下の記事の問題と全く同じです。詳しい解法はこの記事に書き…
幅が小さいので、幅についての 通りの探索が間に合う！ 問題へのリンク 問題概要 のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。 ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 …
すごい面白い！！ 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …
11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…
面白かった 問題へのリンク 問題概要 の行列 と、整数 が与えられる。この行列は、 をちょうど一つずつ要素に含む。 sigma くんは、以下の 2 種類の操作を、好きな順序で 好きな回数 行えます。 全ての について を満たす を選び、行列の 列目をswapする 全…
これ、てんぷら君のおかげで随分とシンプルな問題になった！ 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。各 に対して、 xor xor xor としたときの xor xor xor の値を求めよ。 制約 解法 XOR に関する問題は各桁ごとに考えるのは常套手段では…
これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
ゴリ (prd さん) と一緒に出て楽しかったコンテスト。 そして「グラフのサイクル・パスの列挙」に関する問題は北大セットの定番というイメージになってきた。 問題へのリンク 問題概要 下図のような 角錐が与えられる (底面が 角形で "頂点" の頂点番号を 0 …
確かに、えでゅふぉのラス問にありそう！ 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …
久しぶりに素因数分解する問題が来た！！！！！！！！！！！ 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…
考え方自体は典型的ではある 問題へのリンク 問題概要 個の整数 が与えられる。 これらから 2 個選んで XOR をとって得られる整数 ( 個ある) の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと XOR をみたら、とにかく「各桁ごとに考える」とい…
ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…
