異端開発室

牛客週間コンテスト 第5回 A-游游の文字変換 #include <iostream> #include <string> using namespace std; int main() { string input; cin >> input; for (size_t i = 0; i < input.length(); ++i) { char current = input[i]; if (current >= 'A' && current < 'Z') { input[i] = cu ...

問題概要 3行3列のマトリックス状に配置された9つの照明スイッチがある。各スイッチを操作すると、該当する位置および上下左右に隣接するセルの電球状態が反転する（ON⇔OFF）。初期状態の入力が与えられた際、すべてのセルをON状態に切り替えるための最小操作回数を求めよ。 入力・出力仕様 標準入力からは3行にわたり、各行3個の整数が半角スペース区切りで渡される。各 ...

基本的な比較計算 二つの整数の積を比較する問題では、直接的な計算を用いる。 #include <iostream> int main() { long long w, x, y, z; std::cin >> w >> x >> y >> z; std::cout numA >> numB; std::cout 1) isCritical[node] = true; } int main() { int cols; cin >> cols; string rowA, rowB; cin >> rowA >> rowB; i ...

問題Dの解法 整数配列Aが与えられたとき、他の全ての要素で割り切れない要素の数を求める問題です。配列サイズは最大2×10^5です。 解法としては、各数値の出現頻度を記録し、各要素の約数を調べて他の要素で割り切れるか判定します。重複要素がある場合に注意が必要です。 #include<bits/stdc++.h> using namespace std; const int MAX = 1e6+5; int main() { ...

問題の分析 この問題は、セグメント木のマージ操作を用いて木構造上の動的計画法を最適化する手法が鍵となります。 まず、値の範囲が最大で10^9まで及ぶため、離散化（座標圧縮）が必要です。各値の出現確率を管理する必要があるため、基本的な木DPを考えます。 動的計画法の設計 dp[v][j] を頂点vにおいて、j番目に小さい値が出現する確率と定義します。遷移は以下の3 ...

A - ペアリング 問題文 4つの数が与えられる。各ステップで同じ値の2つの数字を選んで削除する。この操作を最大何回行えるかを求める。 解法 シミュレーションを行う。 コード コードを表示#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> pii; const int mxn = 1e6 + 5; void solve() { int a, b, c, d; ...

理想的な生成器の判定 正整数kが「理想生成器」であるとは、任意の整数n（n ≥ k）が、長さkの回文配列の要素和として表現可能な場合を指す。回文配列とは、配列aがa1からakまでとakからa1までが同一となる配列である。例として、k=1は理想生成器である（nは[n]で表現可能）が、k=2は非理想（3を表現不可能）。 解法: kが奇数の場合のみ理想生成器となる。偶数の場合、配列 ...

ネットワーク最大流問題は、有向グラフ上で容量制限付きの辺を持つネットワークにおいて、ソース（始点）からシンク（終点）へ送ることのできる最大流量を求める古典的な最適化問題である。この問題は二部マッチングや資源配分など多くの応用に利用される。 基本概念 フローネットワーク：ソース s とシンク t を持つ有向グラフ。s からは流出のみ、t へは流入のみが許 ...

概要 Binary Indexed Tree（BIT）は、単点更新と区間クエリを効率的に処理できるデータ構造です。計算量 O(log N) で操作を実行可能であり、競技プログラミングやアルゴリズム最適化で広く利用されます。 構造と原理 BIT は 2 進数表現に基づく構造を利用します。任意の整数は複数の 2 のべき乗和で表せることから、配列要素をべき乗区間で管理します。lowbit 演算（x & - ...

問題概要 n 個の要素があり、それぞれに整数値の属性 a と b が割り当てられています。いくつかの要素を選択して、選ばれた要素の a 属性の合計 と b 属性の合計 の総和を最大化したいと考えます。ただし、以下の条件を満たす必要があります： a 属性の合計 ≥ 0 b 属性の合計 ≥ 0 この条件下で、(aの合計) + (bの合計) を最大にするプログラムを作成します。 アプロ ...