松枝作成シミュレーションのためのキュー・スタックアルゴリズム
松針を松枝に挿入する加工工程をプログラムで再現する問題を考えます。この工程は特定の制約条件下でデータを処理する必要があり、適切なデータ構造の選択が解決の鍵となります。
与えられるものは、供給装置に並んだ N 枚の松針、容量 M の一時保管箱、容量 K の松枝です。松枝への挿入は、常に前回挿入した松針以下のサイズであるという制約があります。この制約を満た ...
6月29日 19:22 投稿
Codeforces 909 問題A〜Fの解説
Codeforces 909 問題解説
問題URL
A B C D E F
難易度：赤 黄 緑 青 緑 紫
解説
A
問題概要：2つの文字列が与えられる。非空の接頭辞を連結した文字列の中で辞書順最小のものを求める。
アルゴリズムラベル：貪欲
解法分析：
辞書順比較は左から順に文字を比較し、どちらかが終了するか異なる文字が見つかるまで続ける。このため、貪欲法が有効。前後の文字列の接頭辞を比 ...
6月26日 19:39 投稿
AtCoder ABC389のアルゴリズム実装と解説
問題C: キューによる区間管理のシミュレーション
この問題では、列の先頭への追加や末尾からの削除、特定位置の要素へのアクセスを効率的に行う必要があります。全ての要素を個別に保持するとメモリや計算量が膨大になるため、連続する要素を「区間」として管理する手法をとります。
各区間について「先頭からの相対距離（開始位置）」と「区間の長さ」を構造体で定義し ...
6月6日 19:20 投稿
数列の部分ソート後の指定位置値の特定
問題概要
1からnまでの順列に対してm回の部分ソート操作を実行し、q番目の位置にある数値を求める問題。ソート操作は昇順または降順のどちらかで、指定された区間内の要素を並び替える。
入力形式
n m
a_1 a_2 ... a_n
op_1 l_1 r_1
...
op_m l_m r_m
q
解法概要
二分探索とセグメント木を組み合わせたO(n log²n)のアルゴリズムを使用する。重要なのは「ある値Xより大 ...
5月22日 19:15 投稿
Codeforces Round 859 Div.4 のアルゴリズム解法と実装解説
問題 A: Plus or Minus
問題概要
3つの整数 a, b, c が与えられます。演算子として + または - のいずれかを用いて a と b を結合した結果が c と一致する場合、該当する演算子を出力してください。必ずいずれか一方のみが成立することが保証されています。
解法のアプローチ
単純な条件分岐で対応可能です。和 a + b が c と等しければ + を、等号が成立しなければ必然的 ...
5月13日 22:32 投稿