競技プログラミングコンテスト問題解説：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 投稿
数学アルゴリズム問題の解法と思考プロセス
回文数の判定
回文数を判定する問題では、まず基本的なケースを考慮し、一般的なケースを解決した後、特殊なケースを処理することで問題を解決できます。
class PalindromeChecker {
public boolean isPalindrome(int number) {
if (number < 0) {
return false;
}
if (number < 10) {
return true;
} ...
6月6日 19:31 投稿
グラフ理論：K値の最大化問題 - 二分探索とシミュレーションによる解法
グラフ理論：K値の最大化問題 - 二分探索とシミュレーションによる解法
問題文
n個の頂点とm辺の単純無向グラフが与えられます。このグラフを完全グラフに補完する必要があります。補完のルールは、あらかじめパラメータKを選び、各ステップで「頂点uとvの間に辺が存在せず、かつ両頂点の次数の和がK以上」である辺のみを追加することです。このルールに従って辺を追加し ...
6月6日 17:45 投稿
宿舎管理システムの設計と実装（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 投稿