ICFPCを見逃してはならない理由を説明し、一連のヒントを示します。 次の週末は無料で、チームを集めて参加しましょう！
思慮深いハッカーのための競争
ICFPC-チームの競争。 独身者向けのコンテストは数多くあります。たとえば、 Facebook Hacker CupやGoogle Code Jamなどです。 ゲーム用のAIが好きな場合、 codingame.comは2〜3か月ごとに優れた課題を実施します。 シングルスの大会では、トップは通常、いくつかの天才によって詰まっていますが、チームでは忍耐力と優れた組織性のためにうまく機能することが可能です。
チームの規模は任意です。 通常、ICFPCタスクはいくつかの方法で解決できます。 すべての方法を試して最高のものを選ぶのは大きな仕事です。 2011年、私は2人のチームでプレイしました。 アイデアが不足していませんでしたが、手の不足を痛感しました。
思慮深い人のための競争。 競争は3日間続くので、オリンピアードのプログラマーほど速くする必要はありません。 タスクについて考え、アルゴリズムを理解し、実装する時間があります。
タスクは簡単ではありません。 コンテストの主催者は毎年変わります。 通常、これは大学であるため、科学的な問題への参照とコンピューターサイエンスの古典をタスクに追加します（たとえば、2014年にSECDマシンへの参照がありました）。 さらに、ICFPCは、関数型プログラミングICFPに関する科学会議と一致するタイミングであり、これはタスクに影響します。 機能的な擬似言語で説明を読まなければならない場合（恐れるな、一般の人が理解できるように！）、仮想マシンとコンパイラをプログラムします。
1つのタスクがあります！ 72時間以内に、無制限の規模のチームで解決できる問題は1つだけです。 しかし、多面的で難しい。 最適に解決することはできませんが、他のチームよりもうまく解決できます。 最も珍しくて鮮やかなタスクは、2006年と2007年のタスクです。このタスクでは、仮想マシン内の仮想マシンがボールを支配し、仮想マシンのリバースエンジニアリングも行いました。
記念日があります）
私xoposhiyは、ICFPCに9回参加しました。 そして、何か新しいことがあるたびに：
- 2007年には、エイリアンのDNAとロープの文字列データ構造を編集するタスクがありました。
- 2009年-仮想マシンシミュレータ用のプログラムを使用して衛星を軌道に打ち上げ、
- 2010年-車と燃料に関するまったく異なるタスク、
- 2011年-カードゲームLambda the Gathering about SKI-combinators、
- 2012年-ボールダーダッシュ用のボット。ゲーム中に要件が変更され、
- 2013-入力および出力の例による算術関数の選択、
- 2014年-2台の仮想マシン上のPac-Manのボット、
- 2015年-呪文付きの六角形のテトリス、
- 2016年-難しい折り紙を解き、コンパイルします。
近年、私たちのチームは一貫してトップ10にランクされています。
- 2016年-6位
- 2015年-7位と13位（2つのチームがありました）、
- 2014年-7位、
- 2013年-3位、
- 2012年-13位、
- 2011年-最終ラウンドには達しませんでした。
- 2010年-22位。
興味深いことに、2013年の3位は8人のチームで優勝しました。 そして昨年、6位は12人ものチームで占められました。 ここで、普通の人は、このような3日間の群衆がたった1つのタスクで生産的に作業できることを驚くべきでしょうか？ 教えて！
神話上の男月と戦う方法
フレデリックブルックス法： 「プロジェクトが期限に間に合わない場合、労働力の追加はそれをさらに遅らせるでしょう」
昨年のICFPC 2016のタスクの例を紹介します。
ダンは、1×1の紙の正方形のシートから組み立てられた平らな折り紙のシルエットです。 折り紙スキャンを復元する必要があります。つまり、シート上の折り目をマークし、スキャン上の各頂点についてシルエット上のどこに行くかを記述します。 初めに、主催者からの100のシルエットがあります。 一日で、参加者はライバルのために自分のタスクを提出することができます。
決定方法
タスクの二重性を使用します。 折り紙を決める必要があります。 また、ライバルが解決できない折り紙を考案する必要もあります。 これは並行作業の最初の機会です。 ICFPCでは、デュアルタスクが一般的です。 2010年と2014年には、同様のタスクがありました。
さまざまな方法で問題を解決します。 折り紙を解決する2つの方法をすぐに思いつきました。シルエットに表示されるポリゴンから1×1の正方形を収集する方法と、その逆でシルエットを1×1の正方形に拡張する方法です。 これらの方法のどれが優れているかは明確ではなかったため、私たちは分割し、並行してそれらを実行し始めました。
そして、彼らは多くのシルエットが凸型の数字であることに気づきました。 しかし、それらは簡単に解決されます-正方形のエッジを曲げることによって。 したがって、我々は凸折り紙用の別のソルバーを作成しました。
それから、WILD BASHKORT MAGES（hello、 ripatti ）チームからのいくつかの難しいタスクに気付きました。これは多くのポイントをもたらし、それらのソルバーを作成しました。 （最終的に、MAGESは折り紙用の特殊なソルバーも作成することを学びました）
次に、数十の折り紙を手動で処理するのに役立つビジュアルソルバーを作成しました。 その結果、1つの問題に対して5つの異なるソルバーがありました。
2013年には、さまざまな種類のタスクに対応する2つの異なるソルバーがあるため、3位になりました。 ICFPCでは、ソリューションの専門化と複製が役立ちます。
ヘルパーコードから始めます。 ソルバーをプログラミングする前に、サブジェクト領域を記述するデータ構造をエンコードする必要があります。 プログラムI / O テストする。 プロファイルと最適化。 1つのグループがこれらのタスクに従事している間、残りはアルゴリズムについて考えています。
視覚化する。 折り紙は数字で記述されていましたが、私たちはそれらを見てみたいので、すぐにビジュアライザーを取り上げました。 各ICFPCで、何らかのビジュアライザーまたはビジュアルデバッガーを作成する必要があります。 ここに私たちのものがあります：
そして、これが、ウナギを獲得したチームのソルバーでの視覚化の様子です。
インフラストラクチャに投資します。 最初の混乱とラッシュが終わったら、日常的なタスクを自動化します。 新しいタスクの自動ダウンロードを行いました。 Gitはチーム全体で利用できるようにGitで折り紙を決定しました。 他のICFPCでは、彼らの改善が有用か有害かを実験して理解するために、ソリューションの最終品質をテストするシステムを作成しました。
それをテストします。 多くのコードを取得するのは簡単です。 正しく動作させるのは困難です。 常にエラーが発生するため、特にチーム全体が使用する低レベルコードでテストを作成するようにしてください。 テストを作成しない場合、3日のうち2日がデバッグに費やされます。 このレッスンは何度も繰り返してきました。 ただし、テストについて話すのは簡単で、競争の激しい状況ではテストを採点するのは難しい。
2で割ります。 ペアで作業すると、12人が6人になります。 カップルがより良いソリューションを提供します。 カップルはいつでも分割でき、各参加者は共通のコードに精通しています。 たとえば、ペアでビジュアライザーの作成を開始し、正しいアーキテクチャを配置してから、機能を計画して分散させ、それらを並行して実行できます。 コーディングするのはさらに楽しいものですが、それは正確ではありません。
マージの競合を避けます。 大規模なチームのリポジトリ内のストーリーは、枝分かれしていることが判明しました。 不正確な動きがあると、マージの競合が発生し、神経が損なわれ、時間がかかります。 したがって、変更履歴を処理することはICFPCで非常に役立ちます。 コードの設計に同意し、IDE設定ファイルをリポジトリに追加し、自動フォーマットを使用します。
ドリームチームを編成します。 タスクは事前に知られていないため、その場で分解する必要があります。 したがって、ICFPCの人々は、状況をすばやくナビゲートし、アイデアを生成して他のチームメンバーに販売し、最も有用なタスクに投資し、他の人のコードの束を読んで、自分の編集でそれを破ることができない便利です。
科学部門を組織します。 チームの一部は、科学記事を読み、既製のツールを探し、主催者や他の参加者からの手がかりを解読できます。 他の科学と同じように、それはすぐに消耗するものではありません。 しかし、昨年、こうしていくつかの有用な考えを見つけました。
寝ることを忘れないでください。 72時間のマラソンがあなたを待っており、新鮮な頭はその重さの価値があります。
Kontur.ruチーム
今年、私たちのチームは[これまでのところ] 14人です。 私たちはすべてのヒントに従い、最高のゲームを見せようとします。
コンテスト中に、Telegramのチャンネルで興味深い記事を書きます。 購読して応援してください。
t.me/KonturTech
本当のジェダイはただ見ることができませんよね？ さらに、ICFPCをプレイすることは、最終結果に関係なく、興味深くエキサイティングです。 だから、チームをまとめて参加してください。 そして、力があなたと一緒にありますように:)
- コンペティションサイト （従来、開始前に最低限の情報があります！）
- 主催者のさえずり