理解するのに少し時間がかかったので、次回以降に考えなくて済むようにメモ。 なので中身はあまりない。ある点 p が多角形 polygon (凸とは限らない) の中にあるかどうかを判定。 Crossing Number Algorithm を使う。(下記 reference 参照) ほぼパクリだが下…

いつも忘れるのでメモ。複素平面上の回転は複素数の積で表せる。 回転させたいとき、回転させたい座標に偏角 の単位ベクトルをかければよい。 C++ だと complex クラスを使えば簡単に記述できる。 ( 極形式 の複素数表記は polar で取得できる。)複素平面を…

余事象を考えて包除原理を用いる問題に出会う度、理解に時間がかかるのでメモ。「すべて～ない」などの条件をもった場合の数を直接求めるのは難しく、否定の条件を考えて余事象で求めることがある。 例えば、求める条件が任意の に対して であるというときに…

全方位木 DP の抽象化を書いてみた。 コードと使用例のみ。(使用例はネタバレあり)気が向いたら解説を書くかもしれない、未来の自分に期待。 少しだけ書くと、rerooting_function では、子ノードの subtree_dp の累積を両側から取って、それぞれの子ノードに…

読みやすさを考慮していないので、詳しく知りたい人は最後に載せたリンク先を参照したりしてほしい。 図や表を気休め程度に載せているが、それを手で書いたりしていると理解が深まるかもしれない。 自分はそうしてやっと理解している気になった。まず木を区…

隣接 項間漸化式の一般項 の値を高速に求める手法を最近知ったのでメモをしておく。 一般項を求めるのは、 行列で行列累乗を用いると、 で求めることができる。 ただ、きたまさ法と呼ばれる手法を用いれば、 で求めることができる。表記など怪しいので、詳し…

問題へのリンク (問題内容は省略) atcoder.jp 考察 想定解ではなかったが、汎用性がありそうなのでメモしておく。各クエリに対して効率的に求めたいが、 をそのままにして考えるのは難しい。( 例えば、 について昇順でソートしても、 について単調性がある保…

atcoder.jp 問題概要 長さ の整数列 がある。 を満たすすべての整数 に対して、次の問題を解く。 整数 に対して、, ( or ) を満たす の最大値を求める。ただしここで or はビットごとの論理和を表す。 制約 考察 → 実装 ある を見ているとき、最大値に関わり…

昨日の ABC155 の D 問題の類題であり、D 問題はこれを引っ張ってきて何とか通せた。 実装を無限にバグらせて、通ったのコンテスト終了 10 分前くらいだけど… atcoder.jp 問題概要 長さ の数列 が与えられる。 の計算で現れた 個の値を昇順で並べたときの 番…

Codeforces で青になった。 上振れすぎだが素直に嬉しい。 Atcoder まだ緑なんだけど… ここ数日やる気がなさ過ぎて、何もできていない、やばい。 こんなんでは維持できないなあ…

競技プログラミングというか、ほとんど高校数学の話ではあるが… 解いた問題のことを書きたいが、気力がないので、簡単な話でお茶を濁しておく。任意の底の対数を計算したいが、C++ ではそのような関数は用意されておらず、底の変換公式に従って計算する必要…

Codeforces でこの操作が必要な問題があり、それにかなりの時間を取られていたら終わってしまったので、メモしておく。 問題の説明などを書く気力がないので、操作方法だけ記す。 問題のリンク : Problem - D - Codeforces例えば、 回の操作で から のいずれ…

atcoder.jp 問題の概要 匹のスライムが横一列に並んでいて、左から 番目のスライムの大きさは である。 隣り合う 匹のスライムを合体させて、 匹のスライムにする。 このとき、 匹のスライムの大きさを とすると、 のコストを支払う。 また、合体後の大きさ…

atcoder.jp 問題 から の番号が振られている 枚の皿があり、皿 には 個の寿司が置かれている。 すべての寿司がなくなるまで、次の操作を繰り返す。 の目が等確率で出るさいころを振り、出目を とする。皿 に寿司がある場合、皿 の寿司を 個食べる。皿 に寿司…

書いたことはあったが、やり方を忘れていて悲しかったので、簡単にまとめておく。DAG (Directed Acyclic Graph) とは、閉路を持たない有向グラフのことを指す、有向非巡回グラフである。 トポロジカルソートとは、この DAG の頂点をどのノードもその出力辺の…

追記 (2020/11/26) https://codeforces.com/contest/1279/problem/D 参照した問題は多分これなんだけど、全然いらなかったし、むしろ下記の受け取り方だとおかしい。 そうは言っても、getline での受け取り方は知っておいた方がいいと思うので、残しておく。…

結構前に過去問を解いていた時に、気が付かなかったのでメモ。 が整数のとき、 は、 ( と の最大公約数) の倍数。これは、拡張ユークリッドの互除法から得られる着想である。(←あまりよく分かっていない。)まあ、相変わらずこういうので多くの時間を犠牲にし…

排他的論理和 (XOR) は桁上がりのない加算 (ﾌﾞﾝｯﾌﾞﾝｯ ←素振り音)atcoder.jp 問題 要素数の数列が与えられる。 XOR をで割った余りを求めよ。 制約 入力値はすべて整数である。 考察 → 実装 で解けるなら、なんてことはない問題であるが、制約上厳しいものが…

atcoder.jp 【問題の概要】 が与えられる。 を両端とした要素数 個の数列を考える。 このとき、隣り合う要素の差が 以上 以下であるような数列を作ることは可能であるかを判定せよ。 未定の要素に対して、大小の制限はない。 【考察】 よく分からないので、…

atcoder.jp【問題の概要】 番号1から番号Nの人がいて、トーナメントで番号1の人が優勝した。番号2から番号Nの人に関しては、どの番号の人に負けたかという情報が与えられる。この情報と矛盾を生じないトーナメントで、その深さが最小であるときの深さを出力…