ICPC 2025 成都站 8 題解説
A – 絵画の枚数
四捨五入を満たす整数列 b を構成する問題。
条件は各 i に対して
round(100·b_i/Σb)=a_i。
これを区間に直すと
(2a_i-1)·Σb/200 ≤ b_i < (2a_i+1)·Σb/200。
Σb ≤ 201 であることから、s を 1…201 まで全探索し、各 s に対して貪欲に b_i を決めればよい。
bool build(int n, vector<int> a, vector<int> &out) {
for (in ...
8月11日 08:10 投稿
数字出現回数の統計
ある科学研究の調査で得られた自然数がn個あり、それぞれの数は1500000000（1.5×10⁹）以下である。異なる数の個数は10000個以下である。与えられた自然数それぞれの出現回数をカウントし、自然数の昇順に結果を出力する。
入力形式最初の行には整数nが与えられる。続くn行には自然数が一つずつ書かれている。
出力形式異なる数の個数m行が出力される。各行には自然数とその ...
8月8日 06:20 投稿
LeetCode Arrays編：平方済み配列・最小部分配列・スpiral行列の攻略
LeetCode 977. 平方済みソート済み配列
この問題では、昇順にソートされた整数配列が与えられたとき、各要素を二乗した後の配列も昇順になるような新しい配列を作成します。配列の両端から中央に向かって比較しながら埋めていく手法が有効です。
実装上の注意点：
結果用の新しい配列を明示的に確保し、そこに値を埋めていく方式を採用すること
配列の末尾から順に値を ...
8月5日 08:38 投稿
競技プログラミング問題の解法と実装
A - 二つのオーブンを使用した最小調理時間
N個の料理を連続して調理するのに必要な時間がT_i分与えられます。二つのオーブンを使用する場合の全料理の最短調理時間を求めます。
解法
動的計画法を用いて、一方のオーブンで実現可能な調理時間の組み合わせを求め、最小の最大調理時間を探索します。
#include <vector>
#include <algorithm>
#include <iost ...
8月4日 20:00 投稿
二分探索アルゴリズムの実装と応用
二分探索は効率的な検索アルゴリズムで、ソート済み配列に対する操作に適しています。基本的な実装パターンは以下の通りです：
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
...
8月3日 19:31 投稿
探索アルゴリズムと分散データ構造の実装指南
二分探索法の基本ロジック
要素が昇順に整列された配列に対し、目的のキーが含まれるインデックスを対数時間で特定する関数です。境界値の更新順序と終了条件の設計が正しさの鍵となります。
参考実行枠組み
#include <stdio.h>
#include <stdlib.h>
#define MAX_CAPACITY 10
#define SEARCH_FAILED 0
typedef int ValueT;
typedef int IndexT;
typedef st ...
8月2日 14:32 投稿
二つのソート済み配列の中央値を二分探索で求める方法
問題の理解
二つのソート済み配列が与えられた場合、全体の中央値を効率的に見つける必要があります。単純な方法では両方の配列をマージしてから中央値を計算できますが、これではO(m+n)の時間計算量が必要です。より効率的な解法として、二分探索を用いることでO(log(min(m,n)))の時間計算量で解くことができます。
アルゴリズムの考え方
二つの配列から、左半分の要素数 ...
7月31日 01:06 投稿
競技プログラミング問題の解法とコード例
A 問題
ある日を選んで問題を解くとき、その日の問題数が次の日の問題数よりも多い場合に選択します。ただし、n+1 日目は 0 問とする。
コードを見る
<code>
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a, b;
void solve() {
cin >> n;
a.resize(n + 1);
b.resize(n + 1);
for (i ...
7月15日 16:53 投稿
GJOI 2024.4.20 プログラミングコンテスト問題解説
朝の部
問題1: 鳥の撃ち合い
問題文:
n×nのグリッド上に、各格子点に1羽ずつ鳥がいます。(0,0)を除いて、すべての格子点に鳥がいます。(0,0)には無音の機関銃があり、任意の角度で発射できます。機関銃を発射すると、(0,0)から放射状に伸びる直線上にあるすべての鳥が撃たれます。最大でk回発射できます。撃てる鳥の最大数はいくつでしょうか？
ただし、m羽の鳥は事前に風 ...
7月7日 17:11 投稿
最長増加部分列の効率的解法：貪欲法と二分探索
動的計画法から最適解への転換
最長増加部分列(LIS)問題では、無秩序な配列から厳密に増加する最長の部分列を見つける。例えば配列[10,9,2,5,3,7,101,18]では、LISは[2,3,7,101]で長さ4となる。
動的計画法の基本アプローチ
基本解法は動的計画法(DP)によるO(n²)の実装：
def lis_length_dp(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
f ...
7月6日 22:08 投稿