competitive_programming

競争力のあるプログラミングとエクササイズ

これらは、いくつかの競争力のあるプログラミングの問題とさまざまな演習の私のC ++ソリューションです。同様の問題は、異なるアルゴリズムとデータ構造を使用して解決されます。時には標準ライブラリが提供するアルゴリズムを使用して、自分のライブラリを使用することもあります。

ほとんどのソリューションは、元UVAのオンラインジャッジ制限によりC+11にあります。提出が成功した後、それらのいくつかは、C ++ 14/17機能を使用するように変更されました。

元ウバOJの問題

問題ソース

id	タイトル	カテゴリ
001 08	最大合計	線形検索、最大サブアレイ、カデンのアルゴリズム
001 09	Scud Busters	凸式船体
001 12	ツリーサミング	バイナリツリー
001 20	フラップジャックのスタック	スタック、パンケーキソート
001 22	レベルの木	バイナリツリー、レベルオーバートラバーサル、幅最初の検索
001 40	帯域幅	順列、バックトラッキング
001 47	ドル	動的プログラミング、コインの変更
001 64	文字列コンピューター	動的プログラミング、編集距離
002 00	まれな注文	トポロジーソート、深さfirst検索
002 16	並んでいる	ダイナミックプログラミング、ハミルトニアンパス、ビットマスク
002 18	moth oradication	凸式船体
002 22	予算旅行
002 40	可変ラディックスハフマンエンコーディング	Huffman Tree、深度最初の検索
002 59	ソフトウェア割り当て
002 64	カンターに頼ります
002 70	並んでいます
002 94	除数
003 34	同時イベントの識別
003 48	最適な配列マルチ順序	動的プログラミング、マトリックスチェーン乗算
003 50	擬似乱数
003 53	厄介なパリンドローム	多項式ローリングハッシュ、文字列処理
003 57	方法を数えます
003 61	警官と強盗
003 72	whatfix表記	バイナリツリー、プリ/イン/イン/ポストオーバートラバーサル変換
003 74	ビッグmod	バイナリ指数、モジュラー指数
004 29	単語変換
004 37	バビロンの塔
004 39	ナイトは動きます	幅広い検索
004 54	アナグラム
004 55	周期的な文字列	文字列、Knuth -Morris – Prattアルゴリズム
004 59	グラフ接続	Disjoint-Set/Union-Find、グラフ接続コンポーネント
004 69	フロリダの湿地
004 81	何が上がるか	最長のサブシーケンス、バイナリ検索
004 82	順列アレイ
005 01	ブラックボックス	AVLツリー、バイナリツリーイテレーター
005 07	ジルは再び乗ります	線形検索、最大サブアレイ、カデンのアルゴリズム
005 16	プライムランド
005 26	文字列距離	動的プログラミング、編集距離
005 36	木の回復	バイナリツリー、プリ/イン/イン/ポストオーバートラバーサル変換
005 40	チームキュー
005 43	ゴールドバッハの推測	素数
005 48	木
005 51	ネスティングの括弧の束
005 58	ワームホール
005 62	分割コイン
005 68	ただの事実	要因、再発関係
005 74	要約してください
005 82	ランダムに有線のニューラルネット	深さfirst検索、グラフバイコンコンポーネント
005 83	主要な要因
006 12	DNAソート	並べ替え、反転カウントをマージします
006 23	500！	要因、大きな整数
006 30	アナグラム
006 39	ルークされないでください
006 74	コインの変更
006 79	ボールを落とす
006 84	積分決定要因	ガウスエリミネーション、ユークリッドアルゴリズム
006 86	ゴールドバッハ推測II	素数
007 01	考古学者のジレンマ	対数
007 14	本のコピー	線形分割、暗黙のバイナリ検索
007 19	ガラスビーズ	デュバンのアルゴリズム、辞書的に最小限の回転
007 27	方程式	式解析、シャントヤードアルゴリズム
007 29	ハミング距離の問題	バックトラッキング
007 50	8人の女王チェスの問題	バックトラッキング
007 87	最大サブシーケンス製品	最大製品サブアレイ、ビッグ整数
007 93	ネットワーク接続
007 96	重要なリンク	深度検索、グラフブリッジ
008 20	インターネット帯域幅
008 33	滝
008 68	数値迷路	バックトラッキング
008 72	注文
009 08	コンピューターサイトの再接続
009 29	数字の迷路
009 42	周期的な数	合理的な数、10進数、ハッシュテーブル
009 90	金のためのダイビング
009 91	安全な敬礼	組み合わせ、再発関係、カタロニアの数
011 21	サブシーケンス	スライドウィンドウ
011 75	女性の選択	安定した一致問題、Gale-Shapleyアルゴリズム
012 10	連続した素数の合計	素数
012 52	20の質問
012 60	販売
012 93	シンボリック派生	表現解析、シャントヤードアルゴリズム、シンボリック評価。
013 72	ログジャンプ
016 50	番号文字列	組み合わせ、再発関係
100 03	スティックを切る
100 04	バイコーリング
100 18	逆にして追加します	Integers、196アルゴリズム
100 61	ゼロと数字はいくつですか？	要因、素数、因数分解、対数
100 79	ピザ切断	組み合わせ、中央多角形
101 07	中央値は何ですか	優先キュー、オンラインアルゴリズム
101 71	会議教授。ミゲル
101 93	あなたが必要なものは愛です	最大の一般的な除inor
102 20	私は大きな数字が大好きです！	要因、大きな整数
102 23	ノードの数	組み合わせ、再発関係、カタロニアの数
102 29	モジュラーフィボナッチ	フィボナッチ数、モジュラー指数
102 45	最も近いペアの問題	2D最も近いポイントペア
102 68	498-bis	ホーナーのルール
102 82	バベルフィシュ	ハッシュテーブル
102 98	パワー文字列
103 05	タスクの注文
103 11	ゴールドバッハとオイラー	素数
103 19	マンハッタン
103 27	フリップソート	AVLツリー
103 41	それを解決します	数字、ニュートンの方法
103 64	四角	バックトラッキング、ビットマスク
103 82	草を散る	貪欲な、間隔カバー
104 28	ルーツ	ルート発見、二等分法
104 54	TRExpression	表現解析、シャントヤードアルゴリズム、カタロニアの数
104 96	ビーパーを集める
105 33	桁の素数
105 67	ベイツを埋めるのを手伝います
105 70	エイリアンとの出会い	順列、スワップカウント、サイクルカウント
105 76	Y2Kアカウンティングバグ
105 86	多項式遺跡
106 00	ACMコンテストとブラックアウト
106 04	化学反応
106 51	ペブルソリティア
106 55	熟考！代数	再発関係、モジュラー指数
106 64	荷物
106 84	ジャックポット
106 99	要因を数えます	素数、素数分解
107 23	サイボーグ遺伝子
107 38	Riemann vs Mertens	プライムナンバー、メビウス関数、メルテンス関数
108 01	ホッピングを持ち上げます
108 10	ウルトラクイックソート	マージ/挿入ソート、反転カウント
108 55	回転した正方形	マトリックス回転、マトリックス転置
108 70	再発
109 20	スパイラルタップ	分析式
109 31	パリティ
109 34	水風船を落とす
109 35	カードを捨てます	キュー、単独でリンクされたリスト
109 38	ノミサーカス
109 54	すべてを追加します	ヒープ
109 57	Su Doku Checker	バックトラッキング、ビットマスク
109 94	簡単な追加	分析式
110 57	正確な合計
110 60	飲み物
110 77	順列を見つけます	組み合わせ、再発関係、スターリング数
111 37	独創的なキューブレンシー
111 51	最長のパリンドローム	動的プログラミング、文字列処理
111 71	SMS	動的プログラミング、文字列処理、Trie
111 95	別のN -queenの問題	バックトラッキング、ビットマスク
112 27	銀の弾丸
112 35	頻繁な値
112 36	食料品店
112 57	新しいマーケティング計画	ポリゴン、刻まれた円の半径、優先キュー
112 58	文字列パーティション	動的プログラミング
112 60	奇数の根の合計	分析式、empl。バイナリ検索、モジュラー算術
112 71	抵抗器の格子	再発関係、漸近拡大
112 83	Boggleをプレイします	バックトラッキング
112 97	国勢調査	2D SQRT分解
113 62	電話リスト	Trie、プレフィックスマッチング
114 13	コンテナを埋めます
114 20	引き出しの胸	組み合わせ、再発関係
114 56	列車です
114 61	平方数	暗黙のバイナリ検索
114 62	年齢のソート	ソートをカウントします
114 63	コマンドー
114 75	パリンドロームまで拡張します
115 17	正確な変更
115 36	最小のサブアレイ	スライドウィンドウ
115 72	ユニークな雪片	線形検索、ハッシュテーブル
115 84	パリンドロームによる分割
116 21	小さな要因	対数
116 34	乱数を生成します
116 36	こんにちは世界！	分析式、対数
116 58	最高の連合
116 86	スティックを拾います
116 91	アレルギー検査
117 03	sqrt、log、sin	再発関係
117 14	ブラインドソート	注文統計（2 nd最大）
117 33	空港
119 02	ドミネーター
119 91	Rujia Liuからの簡単な問題？	ソート、バイナリ検索
119 97	K最小の合計
120 86	ポテンショメータ	フェンウィックツリー
121 05	大きい方が良い（1）
121 05	大きい方が良い（2）
121 92	グレープバイン	バイナリ検索
122 38	アリのコロニー
123 47	バイナリ検索ツリー	バイナリ検索ツリー、前/注文後トラバーサル
124 55	バー	完全な検索、バックトラッキング
124 58	ああ、私の木！
124 62	矩形	線形検索、スタック、ビットマスク
124 94	個別のサブストリング	レックス。最小回転、デュバンのアルゴリズム、ハッシュテーブル
125 04	辞書の更新	クイックソート
126 40	最大の合計ゲーム	線形検索、最大サブアレイ、カデンのアルゴリズム
126 97	最小限のサブアレイ長	線形検索、最大サブアレイ、カデンのアルゴリズム
127 02	拡張	バイナリ形態、バイナリ画像拡張
129 11	サブセット合計	サブセット合計、完全な検索、ミートインザミドル
130 50	パスの発見	組み合わせ、再発関係
132 82	ケーキのようなマッケイクフェイス（1）	ソート、線形検索
132 82	ケーキのマッケイクフェイス（2）	ビットマスク、バケティング

国際的な高性能コンピューティングコンテスト

問題ソース

id	タイトル	カテゴリ
C2	画像を取得します	Fractal、Mandelbrot Set、MPI、 std::thread

その他の問題や運動

さまざまなオンラインソースからのその他の問題。

タイトル	カテゴリ
バイナリ検索ツリーへの配列	バイナリ検索ツリー
ユニットadjを備えた配列。違い検索	線形検索
バイナリソート付き配列遷移点	バイナリ検索
バイナリツリーの直径	バイナリツリー、深さ最初のトラバーサル
バイナリツリートップビュー	バイナリツリー、幅最初のトラバーサル
Bitonic配列検索	バイナリ検索
3つの配列の一般的な要素	線形検索
Y字型のリンクリストの接続ポイント	単独でリンクされたリスト
アナグラムのサブストリングをカウントします	ハッシュテーブル、スライディングウィンドウ
右側の小さな要素をカウントします	AVLツリー
郵便番号で正方形をカウントします	分析式
トリプレットを数えます	線形検索、ペア合計検索
バイナリストリームの分裂性	モジュラー算術、分裂性
平衡点	線形検索
括弧を生成する（1）	組み合わせ、バックトラッキング
合計のサブセットがあります	動的プログラミング
リンクされたリストはパリンドロームです	単独でリンクされたリスト
サブツリーです（1）	バイナリツリー、深さ最初のトラバーサル
行列のk番目の要素ソートされたマトリックス	ヒープ
Kスワップを使用した最大数	バックトラッキング
ヒストグラム内の最大の長方形	線形検索、スタック
最大の正方形のブールマトリックス	動的プログラミング、最大の正方形サブマトリックス
フィボナッチの最後の2桁	フィボナッチ数、モジュラー算術、バイナリ指数
リストマージ	単独でリンクされたリスト
リストマージソート	単独でリンクされたリスト、マージソート
最も長い明確な特徴的なサブストリング	線形検索
最長のパリンドロミック合計サブストリング	線形検索
多数派の要素	Boyer – Moore多数決アルゴリズム
アレイを厳密に増やします	最長のサブシーケンス、バイナリ検索
マトリックス回転	マトリックス回転、マトリックス転置
ソートされた要素間の最大距離	線形検索
文字列内の最大数値	線形検索、辞書編集の比較
各サブアレイの最大（1）	スライドウィンドウ、バランスの取れたバイナリツリー
各サブアレイの最大（1）	スライディングウィンドウ、deque
3つの要素の最大積	線形検索
Min-Stack	スタック
ソートされた回転アレイの最小要素	バイナリ検索
ジャンプの最小数（1）	動的プログラミング
ジャンプの最小数（2）	線形検索
ほぼソートされています	ヒープソート、挿入ソート
次のより大きな要素	線形検索、スタック
バイナリツリーの距離kのノード	バイナリツリー、深さ最初のトラバーサル
グリッド内のパス数	組み合わせ
均一で奇妙なノードをパーティションします	単独でリンクされたリスト
2つのスタックとしてキュー	キュー、スタック
重複したノードを削除します	単独でリンクされたリスト
中央のノードを削除します	単独でリンクされたリスト
辞書からアルファベットを復元します	トポロジーソート、カーンのアルゴリズム
単独でリンクされたリストを逆にします	単独でリンクされたリスト
文字列内の逆単語	線形検索
単独でリンクされたリストを回転させます	単独でリンクされたリスト
回転した配列検索	バイナリ検索、線形検索
2番目に大きい	注文統計、2番目に大きい要素、バイナリカウンター
行と列を設定する場合	線形検索
順列の最小数	線形検索
サイズ3のソートされたサブシーケンス	線形検索
サイズ4のサブシーケンスをソートしました	線形検索
平方根	暗黙のバイナリ検索
与えられた合計でサブアレイ	線形検索
3ウェイパーティション	配列パーティション
指定された合計を持つ2つの要素	線形検索、ハッシュテーブル
順序付けられていない等しいアレイ	シーケンス、ハッシュテーブル
XORリンクリスト	二重にリンクされたリスト
ゼロサムサブアレイ	線形検索、ハッシュテーブル