宿舎管理システムの設計と実装（C言語によるデータ構造の応用）
概要
本稿では、データ構造とアルゴリズムに関する課題として開発した「宿舎管理照会ソフトウェア」について紹介する。学生の宿舎情報を効率的に管理・検索・操作することを目的とし、C言語で実装された単方向連結リストを基盤としたシステムである。主な機能には、学生情報の追加・削除・検索・ソート・表示が含まれる。ユーザーインターフェースはテキストベースのメニュ ...
5月30日 11:45 投稿
上海大学プログラミングコンテスト2023春季ラウンド4の問題解説
A. 二分探索の学習
基本的な二分探索アルゴリズムを実装する問題です。指定された範囲内でターゲット値を見つけるために必要なステップ数を計算します。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int binary_search_steps(int left, int right, int target) {
int steps = 0;
while (left <= r ...
5月28日 10:30 投稿
重量値セグメント木と動的ノード作成
目次- ブルートフォース法 (1)
ブルートフォース法 (2)
重量値セグメント木
演習問題
はじめに主席木を学習中に、重量値セグメント木の学習ノートを更新しておくのを思い出しました
まず、以下の問題を考えてみましょう：
配列に対して以下の操作を行います：
操作 (1)：配列中の第k小さい要素を問い合せます（答えは存在すると仮定）。
操作 (2)：ある要素を変更しま ...
5月28日 02:10 投稿
ランニオ杯プログラミングコンテスト40日間学習記録
学習の感想
振り返ると、この40日間の学習記録はかなり浅いものでした。実際に学習した時間は半分程度で、一部の時間ではオンラインコースのみを見てコードを書く練習をしなかった状況でした。40日間のうち、真剣に学習できたのは約15日間程度でした。来年の試験ではこのような学習方法は避けなければなりません。
今回の試験では時間配分を間違え、良い結果を得ることが ...
5月27日 06:54 投稿
競技プログラミングにおける探索・数論・木構造アルゴリズムの実装技法
行選択による列制約の充足判定
グリッド状のデータに対し、行の削除操作を制限回数内で行った後、残存する列の要件数が指定値以下に収まるかを検証する問題である。行数が比較的小さいため、深さ優先探索を用いて行の採用・不採用のパターンを網羅する。各探索ノードでは、未削除行に含まれる列インデックスを集合に記録し、重複を除いた後のサイズが閾値を超えないか判定 ...
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 投稿
アルゴリズムとデータ構造 - 二分探索法の応用
二分探索法
基本概念
二分探索法は情報科学で広く応用されるアルゴリズムの一つです。その核心的なアイデアは各操作で半分の候補を除外することであり、これにより問題の解を \(\text{log}_2n\)（情報科学では通常 \(\text{log}n\) と表記）の操作回数で見つけることができます。
補足：アルゴリズムの計算量
コンピュータは十分速いかもしれないが、無限速ではない。——『 ...
5月25日 17:27 投稿
C言語における挿入ソートの仕組みと最適化実装
挿入ソートの基本概念
C言語における挿入ソート（Insertion Sort）は、小規模なデータや部分的に整列済みのデータに対して高い効率を発揮する整列アルゴリズムである。未整列の要素を順番に取り出し、既に整列済みの領域内で適切な挿入位置を後方から探索して挿入することで、全体の順序を構築していく仕組みを持つ。
標準的な挿入ソートの実装
以下に、挿入ソートの基本 ...
5月25日 04:03 投稿
河川の岩場問題：二分探索による最適解
問題リンク
https://www.luogu.org/problemnew/show/P2678
問題背景
年一度の「岩場飛び」大会が開催されます！
問題説明
この大会は一直線の川で行われ、川の中には大きな岩が点在しています。主催者はすでに2つの岩をスタート地点とゴール地点として選定しました。スタートとゴールの間にはN個の岩（スタートとゴールを含まない）があります。競技中、参加者はスター ...
5月19日 12:57 投稿
C言語の基礎演習問題
1.整数の階乗を計算する。
#include<stdio.h>
int main()
{
int i =1;
int n=0;
int ret=1;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
ret=ret*i;
}
printf("%d",ret);
return 0;
}
2.1!+2!+3!+4!+5!+6!+...+10!の和を求める。
#include<stdio.h>
int main()
{
int i =1;
int n=0;
int j=1;
for(j=1;j<=10;j ...
5月19日 00:14 投稿