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

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

座標圧縮

AtCoder ABC 128 E - Roadwork (500 点)

これと似てる!!! これの解法 3 みたいなやり方をイベントソートって呼ぶのね。 drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う 整数 が与えられて、区間 […

Chokudai SpeedRun 002 K - 種類数 β (600 点)

これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…

AtCoder ABC 113 C - ID (300 点) (座標圧縮の教育的練習問題)

いわゆる「座標圧縮」を練習できる問題!!! 問題へのリンク 問題概要 組の 2 整数 が与えられる。 の値は のいずれかである。 各 に対して、 という値が、 の値が等しいようなものの中で何番目に小さい値なのかを求めよ。 (出力形式については特殊なので、…

2018 codeFlyer 予選 D ハンコ (二次元いもす法)(500 点)

座標圧縮して二次元いもす法だけど、頭がごっちゃになった。 2018 codeFlyer 予選 D ハンコ 問題概要 白黒からなる N × M の二次元盤面が与えられる。これをより大きな盤面 H × W の左上隅に置く。N × M 盤面を H × W 盤面からはみ出さない範囲で動かしてい…

yukicoder 649 ここでちょっとQK!

yukicoder 649 ここでちょっとQK! K は固定で与えられる。数の集合 S に対する以下の Q 個のクエリを処理してください。i 番目のクエリは以下のいずれかです。 タイプ 1: S に数 v[i] を追加する。 タイプ 2: S に含まれる数のうち K 番目に小さい数を答…

AtCoder ARC 008 D - タコヤキオイシクナール

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…