けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

数学的帰納法

diverta 2019_2 F - Diverta City (900 点)

冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない 問題へのリンク 問題概要 頂点からなる重みつき無向単純完全グラフであって、 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる 通りの…

AtCoder AGC 006 B - Median Pyramid Easy (400 点)

これの Easy バージョン。すごく楽しくて好き!!!!! Easy:操作の結果が所望になる入力を求める逆問題 Hard:操作に入力を与えた結果を求める問題 という風になっていて、普通「操作の結果を求めるだけ」の問題の方が絶対簡単なことが多いのに、Easy と …

AtCoder AGC 031 D - A Sequence of Permutations (1000 点)

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

AtCoder AGC 031 C - Differ by 1 Bit (800 点)

証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…

AOJ 2386 Sightseeing Tour (AOJ-ICPC 250 点)

完全グラフはどのように向きづけしてもハミルトンパスが存在するというね!!! その証明はすごく楽しいと思う!!! 問題へのリンク 問題概要 頂点数 の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して 頂点 i から頂点 j …

AOJ 2939 オセロ (RUPC 2019 day1-C)

めちゃ面白い! 問題へのリンク 問題概要 オセロにおいて、黒石が 1 個だけない状態からスタートする。 ........ ........ ........ ...ox... ....o... ........ ........ ........ ここから通常のオセロルールでプレイする。今、 個のクエリが投げられ、各…

AOJ 2730 Line Gimmick (300)

星 1 個ついてるし、面白かった。「予想」を正しく立てられるかどうかがポイントなんな。最初はカッコ列系の考察するのかと思って迷走したん。 問題へのリンク 問題概要 >><><<< みたいな文字列が与えられる。最初にどこを踏んでも良い。踏んだパネルは消え…