2010年NOIP普及組 課題解説
問題1: 数字の出現回数のカウント
与えられた区間 $[L, R]$ 内のすべての整数について、数字「2」が合計で何回現れるかを求める問題です。
输入例:
2 22
出力例:
6
解法:
各区間内の整数を1つずつ走査し、各数字を10進数桁ごとに分解して「2」の出現回数をカウントします。
#include <iostream>
using namespace std;
int main() {
int left, right;
...
7月1日 16:28 投稿
競技プログラミング問題集: 生成器、MEX、XORの応用
理想的な生成器の判定
正整数kが「理想生成器」であるとは、任意の整数n（n ≥ k）が、長さkの回文配列の要素和として表現可能な場合を指す。回文配列とは、配列aがa1からakまでとakからa1までが同一となる配列である。例として、k=1は理想生成器である（nは[n]で表現可能）が、k=2は非理想（3を表現不可能）。
解法: kが奇数の場合のみ理想生成器となる。偶数の場合、配列 ...
6月26日 21:45 投稿
2024年ICPCヨーロッパ大会最終問題解説
A. Hitoshizuku
貪欲法で解きます。
右端点でソートした後、マッチングされていない点に対して、各右端点以下の点を管理し、その端点が管理されている集合の中で右端点が最も小さい2点とマッチングします。
最適性の証明は調整法によるそうです。
コード例
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using name ...
6月21日 19:26 投稿
競技プログラミングコンテスト問題解説：Codeforces Round 521 (Div. 3)
A. カエルのジャンプ
問題の条件に従って直接シミュレーションを行います。データ範囲に注意し、long long型を使用します。
void solve(){
long long a, b, k;
cin >> a >> b >> k;
cout n;
vector<int> arr(n);
for(int i = 0; i < n; i++) cin >> arr[i];
int result = 0;
for(int i = 0; i < n - 2; i++){
if(arr[i] = ...
6月19日 23:58 投稿
文字列の最適削除と辞書順最小化アルゴリズム
各位置 i の文字を c[i] とし、canErase[x][y] を「文字 x が直後の文字 y を削除可能か」を表すブール配列とする。maxReach[i] は、位置 i から連続して削除可能な最大範囲の終端インデックスを示す（つまり、i+1 から maxReach[i] までの文字はすべて削除可能で、maxReach[i]+1 は削除不可能）。
貪欲戦略として、ある文字が自身の後続文字を削除でき、かつ自身も他の文 ...
6月11日 23:52 投稿
競技プログラミングにおける探索・数論・木構造アルゴリズムの実装技法
行選択による列制約の充足判定
グリッド状のデータに対し、行の削除操作を制限回数内で行った後、残存する列の要件数が指定値以下に収まるかを検証する問題である。行数が比較的小さいため、深さ優先探索を用いて行の採用・不採用のパターンを網羅する。各探索ノードでは、未削除行に含まれる列インデックスを集合に記録し、重複を除いた後のサイズが閾値を超えないか判定 ...
5月26日 19:47 投稿
確率と最適化問題の解法
サイコロとコイン
n面ダイスとコインを使用するゲームの勝率を求める。初期値としてダイスを振り、値が1～K-1の場合コインを繰り返し振る。表が出れば値が倍増、裏が出れば0になり、0で敗北またはK以上で勝利となる。
解法
初期値1～nについて、勝利条件は値が2^x倍されてK以上になることである。各初期値の勝率は1/2^xで、n個の初期値の勝率を合計後nで除算する。
#includ ...
5月26日 00:39 投稿
Codeforces 920 (div3) 解法まとめ
問題 A - Codeforces
入力された四つの座標から、正方形の面積を求める問題です。各辺が軸に平行な正方形かどうかを判定し、辺の長さを計算して面積を求めます。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int cases;
cin >> cases;
while(cases--)
{
int x1, y1, x2, y2, x3, y3, x4, y4;
...
5月25日 02:21 投稿
競技プログラミング問題集：幾何、貪欲法、データ構造
円の面積計算
円の面積を計算する際にはπの精度に注意が必要である。以下のコードは入力値nを用いて円の面積を計算する。ここで円の半径はnに関係する（n*n*0.5をπで割る）。
#include<iostream>
#include<cmath>
using namespace std;
int main() {
double input;
cin >> input;
double area = input * input * 0.5 / M_PI;
printf("% ...
5月23日 22:12 投稿