ちょっと変わった解き方をしたので記録。 Problem - F - Codeforces （追記）公式Editorial もこの解き方でした。 問題概要 以下の問題を ケース解け。 個の正整数 が与えられる。この中から3個以下の整数を「どの2要素も約数・倍数の関係にない」という条件…

お題箱より。 No.778 クリスマスツリー - yukicoder 解法 飾りを頂点0を根とする根付き木とみなします。言葉を言い換えると、求めるものは以下の2条件を満たすペア の個数です。 頂点 が頂点 の先祖である。 頂点番号について、 である。 ここでの「先祖」は…

「スクリプト言語」と呼ばれるRuby、Pythonなどの言語に代表される、比較的実行速度の遅い言語で競技プログラミング（特にAtCoder）をすることについて。 最近色々ともやもやすることが多いので、思っていることを書きます。まさにこれらの言語を使っている…

E - Common Subsequence 公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。 解法 記法について 数列 を単に 、数列 を単に と書くことにします。 与えられた数列は1-indexedで扱い、「0要素目」として空の要素…

F - Minimum Bounding Box 解法 各座標軸ごとに、動きのイメージをつかむ 時刻を文字 で表し、 に依存する変数を のように表します。 まず、 座標を分けて考えてみます。 座標だけに注目すると、それぞれの点は以下の3つにグループ分けできます。 グループ1…

お題箱より。 F - Donation 私も公式解説を見て通したので、公式解説の流れで書いていきます。 解法 時間を逆回しにしてみる 考察を進めていく順番ですが、まず「時間を逆回しにする」ことを考えてしまったほうが良いように思います。普通にゲームを進めると…

E - Sum Equals Xor 解法 ※ と のXOR演算を、 という記号で表すことにします。 まず注目すべきは という条件です。これは知識として覚えておくと得な性質なのですが、XOR演算は繰り上がりのない足し算と思うことができます。 このことを確かめるために、 の…

Problem - C1 - Codeforces Problem - C2 - Codeforces 問題概要 枚の画像がランダムに表示されるWebサイトがある。各画像には重み が設定されていて、画像 の表示確率は である。 画像を 回表示させる。このとき画像が1回表示されるごとにその画像の重みが…

お題箱より。 E - Tozan and Gezan 解法 プレイヤーを以下のように表記します。 Aさん: を操作する。先攻。ターン数を最大化したい。 Bさん: を操作する。後攻。ターン数を最小化したい。 また、 と表記することにします。 もしゲーム開始時点で全ての につ…

お題箱より。 K - 種類数 β 解法 この問題はグラフとして捉えると見通しが良くなります。それぞれの整数を頂点とし、ペア を頂点 と頂点 を結ぶ辺として考えます。整数を選ぶことを頂点に色を塗ることに喩えると、各辺ごとに「両端の頂点のうちどちらかを選…

E - Complete Compress 公式解説とちょっと違う方法で通したので書いておきます。 解法 木DPを考える コマを集める頂点を全て試すことにします。集める頂点を と表記し、 を根とする木DPを考えます。 それぞれの頂点 について、それ以下にある部分木に含まれ…