プログラマーのための挑戦的な競争
こんにちはhabrachitatel。
最近、数学プログラマー向けのコンテストを開催したいと思っていますが、これらのコンテストは、少なくとも効果的な解決アルゴリズムを持たない問題を提案するという点で、プログラミングオリンピックとは多少異なります。 さらに、これまで誰も解決したことがないか、ほとんど解決していないが、大きな成功を収めていないタスクが提案されています。 これらの問題の最後の特徴は、ロシアに埋もれた数学の分野である「あなたがいつ知っている」科学の他の有用な分野と、列挙的組み合わせ論に何らかの形で関連していることです。 しかし、これはそれほど重要ではありません。
そのような競争の例は、n×nのチェス盤に6人の女王を置く問題に関する競争です。 それは最初に私の競争の枠組みで正確に解決され（すべての構成の数の明示的な公式が得られた）、列挙子の組み合わせに関与する研究者の間で共鳴を引き起こしました。 フォーミュラ自体により、この問題の研究者は新しく強力な仮説を立てることができました。 この記事では、Habréでのこのようなタスクに関する自分の立場を表明しました。
将来のポリマーの物理学に関連する別の競争により、この分野の研究者は、欠陥のある格子も簡単に計算できること、および実際には現実的ではない欠陥のない格子を示すことができます。 これは、「ハミルトニアン以前」のサイクルを計算することで示されました。 対応する競争は、動的計画法に関する記事によって強化されました。 この記事で説明されているアルゴリズム（適切な実装を使用）は、世界で群を抜いて最速です（控えめですが、そうです）。 より深刻なコンピューティングパワーがあれば、列挙子の組み合わせで重要な結果を得ることができますが、夢を見ることは有害ではありません。 つまり、この競争は科学にも役立ちました。
現在、私は賞金プールがなくても、「そのような」コンテストを1つ開催しています。レパートリーで最も難しい問題を解決することを提案します。 なんで？ （もちろん、自由時間の存在下で）競争する恋人たちが、他のそのような恋人たちと競争できるように。 提案された問題は難しい（いずれにせよ、それらを解決するための効果的なアルゴリズムの存在は証明されていない）ので、古典的な意味（オリンピアードのプログラミング-スピードと品質のため）ではなく、「誰が最良のアプローチを持っているか」という意味で戦わなければなりません。 そして、誰かがより多くの力を手に入れることができます。 いずれにせよ、私は個人的には勝者ではなく、競争の過程で共同力によって得られた結果自体に興味があります。 練習の結果、私の競争の最後の2つは、科学に実際に役立つことが証明されました。
コンテスト自体は私のブログで開催され、他のコンテストに加えて、プログラミングとはまったく異なる意味を持つ投稿を公開しています。 あなたは単にそれらに注意を払うことができず、すぐにメニューの「 コンテスト 」セクションを選択します。 実際のところ、個人的な理由やコンテストの実施経験が不十分であるという理由で、コンテスト用に別のリソースを作成することはできないため、当面はブログで実施するトレーニングを行います。
タスクの詳細な説明は、コンテストのページに記載されています。ここでは、条件の概要を簡単に説明します。
自然数nが与えられます。 数値3 kが10進表記で少なくともn個の連続したゼロを含むような最小整数kを見つけます。 たとえば、n = 1の場合、3 10 = 59 0 49であり、これは1つのゼロを含むトリプルのべき乗の最初であるため、答えはk = 10になります。 n = 2の場合、答えはk = 35です。335 = 5 00 31545098999707であり、これは2つのゼロを含むトリプルのべき乗の最初のものです。
ドミノをカバーするというよく知られた問題（英語へのリンク）、または二量体の問題があります。 この問題の意味は、1×2ドミノでm×nチェス盤をタイリングする方法の数を計算することです。これにより、ドミノナックルが重ならないようにし、ボードの端から出てボードを完全に覆わないようにします。 たとえば、n = m = 2の場合、2つの方法しかありません（両方とも垂直方向または水平方向の両方のドミノ）。
次に、ボードをシリンダーに「ロール」して、左右の境界線を接続します。 この場合、任意のコーティングは次のように表すことができます。ドミノが左端から飛び出すと、その後半が右側に表示され、その逆も同様です。 2n×2nの正方形のチェスシリンダーのタイルの数を計算する必要があります。 n = 1の場合、答えは5になり、n = 2の場合、答えは121になります...はっきりしない場合、写真は競技のページにあります。
サイズがn×nの正方格子がある場合。 その中で、4、6、8などの長さで、最大長までの単純なサイクルを見つけることができます。 [単純なサイクルは、自己交差のないサイクルです]。 たとえば、2×2格子には長さ4のサイクルが1つあります。3×3格子には長さ4の4サイクル、長さ6の4サイクル、長さ8の5サイクルがあります。つまり、シーケンスが答えになります[4,4,5]。 4×4ラティスでは、答えはシーケンス[9,12,26,52,76,32,6]（4〜16の長さ）です。 n = 5,6、...の答えに名前を付ける必要があります
だから、すべての参加者へようこそ。 私のコンテストや悪意のある人の意味を理解していない人は、決して自分を見せないでください。 頑張って
PS。 はい、ブログに「私はPRです」と投稿するのが適切ですが、これには十分なカルマがありません。 この投稿はスポーツプログラミングにも関連しています。
最近、数学プログラマー向けのコンテストを開催したいと思っていますが、これらのコンテストは、少なくとも効果的な解決アルゴリズムを持たない問題を提案するという点で、プログラミングオリンピックとは多少異なります。 さらに、これまで誰も解決したことがないか、ほとんど解決していないが、大きな成功を収めていないタスクが提案されています。 これらの問題の最後の特徴は、ロシアに埋もれた数学の分野である「あなたがいつ知っている」科学の他の有用な分野と、列挙的組み合わせ論に何らかの形で関連していることです。 しかし、これはそれほど重要ではありません。
そのような競争の例は、n×nのチェス盤に6人の女王を置く問題に関する競争です。 それは最初に私の競争の枠組みで正確に解決され（すべての構成の数の明示的な公式が得られた）、列挙子の組み合わせに関与する研究者の間で共鳴を引き起こしました。 フォーミュラ自体により、この問題の研究者は新しく強力な仮説を立てることができました。 この記事では、Habréでのこのようなタスクに関する自分の立場を表明しました。
将来のポリマーの物理学に関連する別の競争により、この分野の研究者は、欠陥のある格子も簡単に計算できること、および実際には現実的ではない欠陥のない格子を示すことができます。 これは、「ハミルトニアン以前」のサイクルを計算することで示されました。 対応する競争は、動的計画法に関する記事によって強化されました。 この記事で説明されているアルゴリズム（適切な実装を使用）は、世界で群を抜いて最速です（控えめですが、そうです）。 より深刻なコンピューティングパワーがあれば、列挙子の組み合わせで重要な結果を得ることができますが、夢を見ることは有害ではありません。 つまり、この競争は科学にも役立ちました。
現在、私は賞金プールがなくても、「そのような」コンテストを1つ開催しています。レパートリーで最も難しい問題を解決することを提案します。 なんで？ （もちろん、自由時間の存在下で）競争する恋人たちが、他のそのような恋人たちと競争できるように。 提案された問題は難しい（いずれにせよ、それらを解決するための効果的なアルゴリズムの存在は証明されていない）ので、古典的な意味（オリンピアードのプログラミング-スピードと品質のため）ではなく、「誰が最良のアプローチを持っているか」という意味で戦わなければなりません。 そして、誰かがより多くの力を手に入れることができます。 いずれにせよ、私は個人的には勝者ではなく、競争の過程で共同力によって得られた結果自体に興味があります。 練習の結果、私の競争の最後の2つは、科学に実際に役立つことが証明されました。
タスク
コンテスト自体は私のブログで開催され、他のコンテストに加えて、プログラミングとはまったく異なる意味を持つ投稿を公開しています。 あなたは単にそれらに注意を払うことができず、すぐにメニューの「 コンテスト 」セクションを選択します。 実際のところ、個人的な理由やコンテストの実施経験が不十分であるという理由で、コンテスト用に別のリソースを作成することはできないため、当面はブログで実施するトレーニングを行います。
タスクの詳細な説明は、コンテストのページに記載されています。ここでは、条件の概要を簡単に説明します。
問題1. 3からnの程度
自然数nが与えられます。 数値3 kが10進表記で少なくともn個の連続したゼロを含むような最小整数kを見つけます。 たとえば、n = 1の場合、3 10 = 59 0 49であり、これは1つのゼロを含むトリプルのべき乗の最初であるため、答えはk = 10になります。 n = 2の場合、答えはk = 35です。335 = 5 00 31545098999707であり、これは2つのゼロを含むトリプルのべき乗の最初のものです。
問題2.シリンダー上のダイマー
ドミノをカバーするというよく知られた問題（英語へのリンク）、または二量体の問題があります。 この問題の意味は、1×2ドミノでm×nチェス盤をタイリングする方法の数を計算することです。これにより、ドミノナックルが重ならないようにし、ボードの端から出てボードを完全に覆わないようにします。 たとえば、n = m = 2の場合、2つの方法しかありません（両方とも垂直方向または水平方向の両方のドミノ）。
次に、ボードをシリンダーに「ロール」して、左右の境界線を接続します。 この場合、任意のコーティングは次のように表すことができます。ドミノが左端から飛び出すと、その後半が右側に表示され、その逆も同様です。 2n×2nの正方形のチェスシリンダーのタイルの数を計算する必要があります。 n = 1の場合、答えは5になり、n = 2の場合、答えは121になります...はっきりしない場合、写真は競技のページにあります。
問題3.正方格子上のサイクルの統計
サイズがn×nの正方格子がある場合。 その中で、4、6、8などの長さで、最大長までの単純なサイクルを見つけることができます。 [単純なサイクルは、自己交差のないサイクルです]。 たとえば、2×2格子には長さ4のサイクルが1つあります。3×3格子には長さ4の4サイクル、長さ6の4サイクル、長さ8の5サイクルがあります。つまり、シーケンスが答えになります[4,4,5]。 4×4ラティスでは、答えはシーケンス[9,12,26,52,76,32,6]（4〜16の長さ）です。 n = 5,6、...の答えに名前を付ける必要があります
だから、すべての参加者へようこそ。 私のコンテストや悪意のある人の意味を理解していない人は、決して自分を見せないでください。 頑張って
PS。 はい、ブログに「私はPRです」と投稿するのが適切ですが、これには十分なカルマがありません。 この投稿はスポーツプログラミングにも関連しています。
All Articles