異端開発室

基本操作 LCT（リンクカットツリー）は、Splay木を使用して森を管理します。実際のエッジの追加や削除が可能です。親への参照のみを行い、子への参照はしません。 notroot: ノードがSplay木のルートである場合は0を、それ以外は1を返します。ノードがルートであるときには特別な扱いが必要なためです。 splay: 現在のノードを現在のSplay木のルートに回転させます。 Acce ...

問題1: カーペットの重なり 会場の矩形エリア（平面直交座標系の第一象限と見なされます）にいくつかの矩形カーペットを敷きます。合計n枚のカーペットがあり、1からnまで番号が付けられています。これらのカーペットは、番号の小さい順に座標軸に平行に順次敷かれ、後から敷かれたカーペットが前に敷かれたカーペットの上に重なります。カーペットの敷き詰めが完了した後 ...

A - Capitalized? 英字からなる文字列 $S$ が与えられる。先頭が大文字で、残りがすべて小文字であるかを判定する。 単純に先頭文字が 'A'～'Z' の範囲にあり、他の文字がすべて 'a'～'z' の範囲にあるかをチェックすればよい。 #include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; bool ok = isupper(s[0]); for (in ...

問題A: 停車可能区間の判定 ある区間内に指定された位置が含まれるかを判定する問題です。xとyの大小関係によって、区間の方向が変わる点に注意が必要です。 コード例 #include <iostream> #include <algorithm> int main() { int n, x, y, z; std::cin >> n >> x >> y >> z; bool result = false; if (x ...

プログラミングにおける時間制御技術 背景 時折、私たちの検索処理は非常に長時間かかり、タイムリミットエラー（TLE）が発生します。TLEが発生した場合のスコアは0ですが、タイムリミット直前に現在の最適解を出力できれば、スコアは0以上となります。このような状況では、時間制御技術が必要になります。 時間制御とは 時間制御、その名が示す通り、時間を制御するこ ...

この問題は2500点の難易度を持つ競技プログラミングの問題です。 問題概要 二つの異なるアプローチを紹介します。 解法1 まず、各数の出現回数が3の倍数である場合を考えます。区間が有効であるためには、全ての数の出現回数を3で割った余りが0である必要があります。この条件を満たすために、出現回数を3で割った余りの配列をハッシュ化し、以前に同じハッシュ値が出現し ...

A問題: 時間帯の重なり判定 この問題は、ある時間が指定された時間範囲に含まれるかを判定するものである。注意点として、時間帯が翌日にまたがるケースがある。これを処理するために、終了時刻が開始時刻より小さい場合は終了時刻に24を加算し、範囲を正しく表現する。 次に、基準となる時刻（国王が叫ぶ時刻）がその範囲内にあるか、または24時間を加えたバージョンが範 ...

高精度計算 トライ木を用いたA+B #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; struct TrieNode { int children[26]; int value; } nodes[1000]; char buffer[100]; int nodeCount = 0, totalNodes = 0, resultSum = 0; bool negativeFlag; void insertNumber() { int cur ...

問題 1000: 2つの整数の合計 問題概要 2つの整数 a と b を読み込み、それらの合計を出力してください。 C++ コード例 #include <iostream> // 標準入出力ライブラリをインクルード int main() { int value1, value2; // 2つの整数値を格納する変数を宣言 // 標準入力から2つの整数値を読み込む std::cin >> value1 >> value2; // 読み込んだ2つ ...

A. Image Scaling 簡単な問題。矩形の幅と高さを求め、それらの最大公約数で割って互いに素にするだけ。 コードを表示#include <cstdio> #include <cstring> int n, m, x1, y1, x2, y2; char grid[505][505]; int gcd(int a, int b) { while (b) { int t = b; b = a % b; a = t; } return a; } int main() { scanf ...