当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける！！！ というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…

ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…

さ、300 点！？ 問題へのリンク 問題概要 個の中からランダムに選ぶ試行を 回行う。それぞれのものが出た回数が 回になる確率を としたとき、 を満たすような最小の を求めよ。 制約 考えたこと 確率を求めること自体は難しくなくて、 で求められる。が、こ…

再帰関数の使い方に慣れるための教育的問題。 この手の再帰的なフラクタルっぽい構造を読み解く問題は「十分回数を重ねると最初の方の模様が収束する」みたいなことをするイメージがあるけど、今回はそういうのじゃなくて純粋に再帰関数の使い方を問われる問…

好き！ 確かに天才系問題だけど、実験を積み上げると見えて来る感じが最高！！！ 問題へのリンク 問題概要 × の盤面に何個かのコマが置かれている。先手と後手が交互に、以下のいずれかの動作を繰り返す: コマを 1 つ選び、それを 1 マス左か下に動かす (た…

これ好き！！！ しばらく、CPSCO の良さげな問題を解説するターンをやってみたい。 問題へのリンク 問題概要 石の山が 2 個あって、それぞれ初期状態では 個積まれている。ここから先手と後手が交互に 残っている石の山から 1 つ選び、その石の個数を とする…

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

高校の頃とかに「グリッドの左上から右下まで行く最短路が何通りあるか」みたいな問題に親しんでいれば、自然に思えるかもしれない 問題へのリンク 問題概要 のグリッドがあって、最初は駒は左上隅に置かれていた。 駒が上下左右に動きながら右下隅まで移動…

割と難しい気がする。数学センスが少し必要な感じ 問題へのリンク 問題概要 のブロックが の直方体状に並んでいます。 高橋君は各ブロックを赤色または青色で塗ろうとしています。 このとき、次の条件が成り立つようにします。 赤いブロックも青いブロックも…

期待値に関するセンスがちょっと求められる問題 問題へのリンク 問題概要 高橋君はテストケースが ケースある Yes/No 判定問題に対して、ソースコードを提出したところ 問で TLE して、残りの 問は正解しました。 そこで「 問については 100ms で正解し、残…

居酒屋からのエクストリーム参加。D 問題が面白そうだったので突っ込んだ。解けてよかった！！！ 問題へのリンク 問題概要 から までの整数からなる 2 つの順列 に対して、新たな順列 を以下のように定める: := 項目の値は である 今、順列の列を で定める。…

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

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

もこもこさんが Twitter で挙げてた問題に色んな解法を寄せられていて面白かったのでメモします。 問題 を満たす整数 をすべて求めよ 解法 1: 判別式が平方数 (Pulmn さんの解法) 恐らく受験数学的には最もメジャーな解法です。 を二次方程式として見たとき…

二部グラフ解法頭いいと思ったものの、整数論的考察で通したのでその報告を。TL 見た限りだと、kirika さんと同じ解法っぽいですがかなり少数派っぽいです (ただし、自分はイデアルという概念を意識できてはいなかったです...)。 d1=2^k * u (u は奇数) とす…