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

解説見ても計算量について理解できなかったので、自分なりに考えたものの備忘録。atcoder.jp 問題 長さ の整数列 が与えられる。 これを並び替えた数列を として、次の条件を満たすものの総数を で割った余りを求める。ただし、重複する要素は区別する。 ・ …

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

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

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

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

酒入ってたけど、入ってなくても思いつかなかったな。codeforces.com 問題概要 つの 文字列で 文字でも一致する状態を "a bit similar" であるとする。 文字列 が与えられたとき、 から得られる長さ の部分文字列すべてに対して "a bit similar" である辞書…

難しい、全然分からんかった。 リンク codeforces.com 問題概要 (雑) 長さ の区間があり、 個の区間が の形式で与えられる。これらの区間を つのグループに分けることを考える。(各区間はただ一つのグループに属し、複数個には属さない。) 各グループでは長…

こういう問題を素早く解けるようになりたい。 リンク codeforces.com 問題概要 の 個の街がある。街 には の確率で電波塔が設置される。電波塔のパワー は自由に設定でき、距離が 未満の街に電波が供給される。街 と街 には電波が供給されず、 に重複なしで…

リンク atcoder.jp 問題概要 頂点有向グラフが与えられる。 グラフの頂点をランダムに選び、選んだ頂点から到達可能な頂点を消す作業を、グラフが空になるまで繰り返す。 このときの操作回数の期待値を求める。 制約 (考察) 同じような考え方を用いる問題を…

問題へのリンク atcoder.jp 問題概要 の収納スペースと、既に片付けられている 個のマスコットの配置が与えられたとき、残りのマスコットの片付ける方法を で割った余りを求める。 ただし、途中で長方形ができるだけ多くなるように並べる。 制約 考察 長方形…

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

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

atcoder.jp 問題概要 '0', '1', '?' からなる長さ の文字列が与えられる。 '?' には、'0' または '1' が入れられる。 それを埋めた '0' と '1' からなる文字列の任意の連続部分列の中で '0' と '1' の個数の差が 以下となる文字列の個数を で割った余りを求…

DP は比較的すぐに浮かんだのに、復元できなくて詰んだ、反省。 リンク D. Nastya and Scoreboard codeforces.com 問題概要 上図のように数字を点灯させることができる Scoreboard がある。 個の Scoreboard の状態が与えられるが、新たに 個点灯させたとき…

問題へのリンク C - Eugene and an array codeforces.com 問題概要 長さ の数列 が与えられる。区間の和が となる連続部分列を含まない連続部分列の個数を求めよ。 制約 考察 ある条件を満たす数え上げの問題である。 本番では、さっと順序立てて書けずに、…

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

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

本渡楓と楠木ともりの FUN'S PROJECT LAB のイベントに行ってきた。 あまりチケットが取れる期待していなかったのだが、昼の部と夜の部ともに取れた。 本渡上陸作戦は単独イベントまで 4 年いかないくらいかかったのに、ゲストがいるとは言え 1 年足らずで単…

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 での受け取り方は知っておいた方がいいと思うので、残しておく。…

昨日は、問題の考察をしながら Abema でやってた一挙放送つけてたら、一日が終わってた気がする。 ○○○○が悪いんだよ… (←わかる人にはわかる) やっぱり危機管理おもしろいなあ。(←わかる人にはわかる) 今日は、セグ木分からんって言ってたら一日が溶けてた。 …

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

やる気がなさすぎるし虚無すぎるので、雀荘にでも行ってやろうかと就寝前に思っていたが、起床が遅すぎたので断念。 目が覚めたときに身体痛すぎるんだけど、ほんとどうなってんのかな… 今も痛みが抜けてないけど。雀荘行きは無事阻止されたので、勉強できる…