2024年夏休み交流戦・練習編1
2024年夏休み交流戦・練習編1
A - 🐓
AtCoder - abc079_d
問題文
各頂点のコストが与えられ、それを1に変換するのに必要な最小コストを求める。
解法
すべての数を1にするには、直接1に変換するか、別の数に変換してからさらに変換する方法がある。
これは$floyd$アルゴリズムによる最短経路探索と似ているため、$floyd$を適用できる。
コード
#include<bits/stdc++.h&g ...
8月5日 02:59 投稿
Codeforces Round 1051 (Div. 2) A~D2問題の解説
A. 全ての長さの減算
思考問題。
長さが \(k(k \in [1,n])\) の区間を選び1を引く操作を繰り返す場合、まず\(a_i = n\) の位置を特定します。次に、\(n\) が存在する区間を維持し、\(n-k+1\) がその両側に存在するか確認し、存在すれば区間を拡張します。存在しない場合は操作は不可能です。
コードを表示```
#include <bits/stdc++.h>
using namespace std;
using i ...
8月1日 18:57 投稿
Codeforces Round #671 (Div. 2) 主要問題のアルゴリズム解法と実装
A - Digit Game
正整数 $n$ が与えられたとき、先手は奇数インデックスの位置、後手は偶数インデックスの位置を交互に消去していく。最後に残った数字の奇偶性によって勝者が決定する。二人が最適に行動する場合の勝者を判定する。
最後に残る位置は $n$ の偶奇によって一意に定まる。$n$ が奇数の場合は先手が制御する位置（0-indexed で偶数インデックス）、$n$ が偶数の ...
7月19日 20:58 投稿
Codeforces Round 1027 (Div. 3) 問題解説（A〜E）
概要
本稿では、Codeforces Round 1027（Div. 3）の問題AからEまでの解法を示す。
問題A：数値構築
問題内容
4桁の整数cが与えられる。整数a（0以上99以下）とb（0以上99以下）を用いて、(a+b)² = c を成立させられるか判定する。
解法
0から√nまでの範囲で遍历し、平方数になるかを判定すればよい。a+b = √c が成立する必要があり、a=0, b=√c で試すだけで十分である ...
7月19日 20:01 投稿
Codeforces Round 1020 (Div. 3) 解説
A. Dr. TC
Dr. TC は患者の知能をテストするために、以下のような問題を設計しました。
長さが \(n\) の二進数文字列 \(s\) を作成します。
この文字列 \(s\) を元に、\(n\) 個の二進数文字列 \(a_1, a_2, \dots, a_n\) を生成します。具体的には、\(a_i\) は \(s\) の第 \(i\) 文字を反転（1 なら 0 に、0 なら 1 に）したものです。
これらの文字列を \(n \times n\) ...
7月7日 22:51 投稿
Codeforces Edu Contest 161 解法と分析
問題A: 文字列照合判定
この問題では、文字列cの各文字が対応する位置の文字列aまたは文字列bのいずれかと一致するかを判定する必要があります。すべての文字が一致する場合は"NO"、そうでない場合は"YES"を出力します。
#include
#include
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test_cases ...
7月7日 20:03 投稿
Codeforces Round 999 合併部門における競技プログラミング問題の解説
A - 数列の並べ替えとスコア最適化
長さ n の整数列 a が与えられる。初期値が 0 の変数 s に対して、a の要素を順に加算する。s が偶数になった場合、ポイントを 1 加算した上で s を 2 で割った余り（つまり s % 2）に更新する。この操作を繰り返す中で、得られるポイントの合計を最大化するために、a の要素をどのように並び替えるべきか。
重要な観察として、奇数の個 ...
6月22日 18:23 投稿
Codeforces Round 998 (Div.3) 解説: A-D問題の解法と実装例
コンテスト参加後の復習と解法の整理を行います。問題AからDまでのアプローチとコードをまとめました。
A. Fibonacciness
5要素の数列における最大の「フィボナッチ度」を求める問題です。数列の長さが5であるため、最大でも度は3となります。各位置で成立するフィボナッチ関係の式を検討します。
具体的には、a0+a1 = a2、a1+a2 = a3、a2+a3 = a4の3つの条件が考えら ...
6月22日 17:44 投稿
Codeforces Round #1058 (Div. 2) 問題解説
A - MEX Partition
この問題の核心は、配列全体のMEX（Minimum Excluded Value）を求めることに帰着します。与えられた配列 $A$ をいくつかの部分集合に分割し、そのすべての部分集合のMEXが等しくなるための条件を考えます。
$A$ のMEXを $m$ とします。$m$ は $A$ に含まれない最小の非負整数であるため、$m$ より大きい要素は各部分集合のMEX計算において無視できま ...
6月21日 21:20 投稿
Codeforces 1000~1100 第三週の問題解説
部分文字列と部分配列
目的は、文字列 a と b を部分配列として含む最短の文字列を見つけることです。その長さは a と b の長さの合計から、両方で共通する文字数を引いたものです。a は必ず含まれるため、b の各文字が a で順番に現れるかをチェックします。
注意: 部分文字列は連続した文字列ですが、部分配列は順序を保ちつつ連続性は必要ありません。
#include <bit ...
6月13日 22:13 投稿