アルゴリズムベースの組み合わせ論問題IMOスタイル[複製]
問題は図に示されています。解決策は構成的証明であると想定されているため、実行時間などに関係なく機能するアルゴリズムを見つける必要があります。私はこれを解決することができず、私はしばらくの間試みてきました
編集:私の主な方向は、すべてのrawの符号を負の合計で変更することでした。これで、すべてのrawが完了し、すべてのエントリの合計が非負になります(すべてのrawの合計が非負になるため)
回答
1 quasi
行または列の合計が負の場合は、1つを選択し、符号を逆にします。
プロセスを繰り返します。
各遷移の後、マトリックス内のすべてのエントリの合計が増加します。
ただし、エントリの絶対値は変更されないため、合計の可能性は限られています。
その結果、プロセスは最終的に終了します。
1 AryanHemmati
次の単純なアルゴリズムを使用するだけです。各ターンで、負の合計でランダムな行または列の符号を逆にすると、この手順が有限の動きで終了することが証明されます。このアルゴリズムを使用すると、すべてのボードは常に増加し、この合計は上から制限され、この合計には有限の可能性があるため、アルゴリズムはどこかで停止し、すべての行と列の合計が負ではないという点があります。