kactl

カトル

このリポジトリは、KTH の ICPC チーム参照ドキュメントである KACTL をホストします。これは、ICPC スタイルのプログラミング コンテストで使用するための、コピー＆ペースト可能な 25 ページの C++ コードで構成されています。

閲覧可能な最終バージョンについては kactl.pdf を、生のソース コードについては content/ を参照してください。

願望

KACTL アルゴリズムは、便利で、短く、十分に高速で、十分にテストされており、関連する場合は読みやすく、変更が簡単である必要があります。コードは手動で入力され、オーバーヘッドが追加されるだけなので、あまり汎用的になるべきではありません。スペースの問題により、非常に一般的/単純なアルゴリズム (ダイクストラなど)、または非常に珍しいアルゴリズム (一般的な重み付けマッチング) も除外します。

何かが足りないと感じた場合、クリーンアップできる可能性がある場合、またはバグに気づいた場合は、問題を提出するか、プル リクエストを送信してください。

KACTL のカスタマイズ

KACTL はそのままでも使用できますが、個人用のコピーを作成する場合は簡単に変更できます。特に、表紙を変更したり、含めるアルゴリズムを独自に選択したりすることができます。スペースの問題により、リポジトリ内のすべてのアルゴリズムが PDF に含まれているわけではありません。色付きの構文強調表示を有効にすることもできます。

content/kactl.tex KACTL のメイン ファイルで、チーム名、ロゴ、構文の強調表示などを変更するために編集できます。このファイルは、各章の内容を定義するcontent/サブディレクトリのそれぞれからchapter.texファイルをインポートします。これらには、LaTeX 形式のソース コード、テキスト、数学が含まれます。章にコードを追加または削除するには、 chapter.texファイルから対応するkactlimport行を追加または削除します。より適切に配置するには、 hardcolumnbreak 、 columnbreak 、またはnewpageコマンドを挿入するとよいでしょう。ただし、これは通常、重要なコンテストの前にのみ行われ、メイン ブランチでは行われません。 PDF に含まれていないアルゴリズムは、 chapter.texでコメントアウトされたままになっています。

KACTL をビルドするには、*nix マシン上でmake kactl (またはmake fast ) と入力します。これにより、 kactl.pdf更新されます。 (Windows も同様に動作する可能性がありますが、テストされていません。) doc/READMEには、これに関する追加の注意事項がいくつかあります。

ヒント:

1. make showexcluded実行して、デフォルトで除外されるものを確認します。デフォルトの構成は、初心者チームと上級チームにとって適切なバランスとなるように選択されています。
2. これらのアルゴリズムを入力するときにハッシュを利用してください。各アルゴリズムの右上には 6 文字の MD5 ハッシュがあります。このハッシュは、 hash.shまたは.vimrcの:Hashコマンドを使用して生成できます。ハッシュ化では空白とコメントは無視されます。

コーディングスタイル

KACTL は比較的簡潔なコーディング スタイルを使用し、コードを短縮するのに役立ついくつかのマクロ/typedef がテンプレートで定義されています。行幅は 63 文字で、インデント用のタブが付いています (PDF ではタブ = 2 スペース)。

各アルゴリズムには、コードの作成者、コードが追加された日付、アルゴリズムの説明、テスト ステータス、およびできればソース、ライセンス、時間計算量を含むヘッダーが含まれています。

kactl.pdf は 25 ページ + 表紙に収める必要があります。便宜上、生成された kactl.pdf がリポジトリにコミットされることもありますが、git の操作が遅くなるため、あまり頻繁にはコミットされません。

テスト

KACTL は、アルゴリズムの正確さに対する高いレベルの信頼を目指しています。テストは、オンラインの裁判官と (新しいアルゴリズムの場合) ランダムに生成された大量の事件の出力をより単純なアルゴリズムと比較するストレス テストの両方で行われます。これらのテストはstress-testsディレクトリに存在し、コミットごとに CI を使用して実行されます。 CI は、すべてのヘッダーがコンパイルされること ( docs/scripts/skip_headersの除外リストを除く)、および latex がコンパイルされることも検証します。

old-unit-tests約 10 年前に最後に触られた、壊れた単体テストがいくつか含まれています。

ライセンス

競技プログラミングの常として、ライセンス状況は少し不透明です。多くのソース ファイルにはライセンスのマークが付いています (私たちは CC0 を使用するようにしています) が、そうでないものも多くあります。ただし、おそらく他の作成者からの善意が想定されており、コードは配布されていないため、多くの場合、許可は必要ありません。物事を遡りやすくするために、ソースと作成者がソース ファイルに記載されています。

インターネット上から取得したリファレンス実装を除き、 stress-testsのすべては暗黙的に CC0 です。