2023年10月25日 模擬試験の反省
時間管理
7:40 から 8:40 まで、対拍と乱数生成の準備を行い、問題を読み込み、T1 を開始しました。40分で初回の提出を完了し、対拍で小さな誤りを見つけたため修正して再提出しました。
8:40 から 10:20 まで、T2 の解決に取り組みました。以前の模擬試験の T2 と類似点がありましたが、直接的な解法が見つからなかったため、まずは暴力解法を考えました。しかし、n ≤ 6 ...
7月14日 20:38 投稿
文字変換とアルゴリズム問題集
文字変換問題
Ytfcは魔法の森で、文字列の大文字小文字を反転させる必要がある。この問題を解決するプログラムを作成せよ。
入力:
複数の文字列が与えられる。各文字列の長さは1から200の間である。
出力:
各文字列に対して、大文字小文字を反転させた結果を出力する。
#include<stdio.h>
char str[205];
int main(){
while(scanf("%s",str)!=EOF){
...
7月12日 18:31 投稿
红包分配システムの実装とソート処理
問題概要
N人の参加者間での紅包（お年玉）の分配記録を処理し、各人の収支を計算するプログラムを作成します。入力データから各人の収入金額、支出金額、獲得紅包数を算出し、指定された条件でソートして出力します。
入力形式
最初の行には参加者数N（≤104）が与えられます。続くN行には、各参加者が発行した紅包の情報が以下の形式で記述されます：
K N1 P1 N2 P2 ... ...
7月11日 16:44 投稿
LCT（リンクカットツリー）の基礎と応用
基本操作
LCT（リンクカットツリー）は、Splay木を使用して森を管理します。実際のエッジの追加や削除が可能です。親への参照のみを行い、子への参照はしません。
notroot: ノードがSplay木のルートである場合は0を、それ以外は1を返します。ノードがルートであるときには特別な扱いが必要なためです。
splay: 現在のノードを現在のSplay木のルートに回転させます。
Acce ...
7月8日 22:19 投稿
NOIP 2011 第1日問題解説
問題1: カーペットの重なり
会場の矩形エリア（平面直交座標系の第一象限と見なされます）にいくつかの矩形カーペットを敷きます。合計n枚のカーペットがあり、1からnまで番号が付けられています。これらのカーペットは、番号の小さい順に座標軸に平行に順次敷かれ、後から敷かれたカーペットが前に敷かれたカーペットの上に重なります。カーペットの敷き詰めが完了した後 ...
7月8日 20:20 投稿
AtCoder Beginner Contest 338 解説
A - Capitalized?
英字からなる文字列 $S$ が与えられる。先頭が大文字で、残りがすべて小文字であるかを判定する。
単純に先頭文字が 'A'～'Z' の範囲にあり、他の文字がすべて 'a'～'z' の範囲にあるかをチェックすればよい。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
bool ok = isupper(s[0]);
for (in ...
7月8日 19:49 投稿
ABC352コンテスト問題解説
問題A: 停車可能区間の判定
ある区間内に指定された位置が含まれるかを判定する問題です。xとyの大小関係によって、区間の方向が変わる点に注意が必要です。
コード例
#include <iostream>
#include <algorithm>
int main() {
int n, x, y, z;
std::cin >> n >> x >> y >> z;
bool result = false;
if (x ...
7月7日 21:07 投稿
プログラミングにおける時間制御技術：タイムリミット回避戦略
プログラミングにおける時間制御技術
背景
時折、私たちの検索処理は非常に長時間かかり、タイムリミットエラー（TLE）が発生します。TLEが発生した場合のスコアは0ですが、タイムリミット直前に現在の最適解を出力できれば、スコアは0以上となります。このような状況では、時間制御技術が必要になります。
時間制御とは
時間制御、その名が示す通り、時間を制御するこ ...
7月6日 00:29 投稿
CF1418G - Three Occurrences問題の解法
この問題は2500点の難易度を持つ競技プログラミングの問題です。
問題概要
二つの異なるアプローチを紹介します。
解法1
まず、各数の出現回数が3の倍数である場合を考えます。区間が有効であるためには、全ての数の出現回数を3で割った余りが0である必要があります。この条件を満たすために、出現回数を3で割った余りの配列をハッシュ化し、以前に同じハッシュ値が出現し ...
7月5日 22:08 投稿
ABC367 回顾：典型アルゴリズム問題の解法と実装
A問題: 時間帯の重なり判定
この問題は、ある時間が指定された時間範囲に含まれるかを判定するものである。注意点として、時間帯が翌日にまたがるケースがある。これを処理するために、終了時刻が開始時刻より小さい場合は終了時刻に24を加算し、範囲を正しく表現する。
次に、基準となる時刻（国王が叫ぶ時刻）がその範囲内にあるか、または24時間を加えたバージョンが範 ...
7月3日 23:27 投稿