たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【AtCoder】【C#】AtCoder Grand Contest 041 の反省

AtCoder Grand Contest 041のコンテストに参加したので、その感想を残しておきます。今回はA問題だけ解いて終了しました。A問題でどう考えたか、どこにはまったかを残します。

はじめに

コンテストへのリンク

atcoder.jp

解いた問題

A問題のみです。

解答説明

A問題

問題概要について書きます。

  • N個のテーブル、2N人の選手がいる
  • Xテーブルでの試合に勝った選手は次の試合をX-1で実施。負けた選手は次の試合をX+1で実施
  • テーブル1で勝ったらそのまま、テーブルNで負けたらそのまま
  • A , B が勝ち負けの結果を操作できるとき、AとBが対戦するために必要な最小ラウンドは何か

最初に考えたこと

まず、B-A(A<Bのため)が偶数だった場合は2で割った値が答えになることがわかります。なので、B-Aが奇数だった場合を考えます

普通に動かしているだけでは同じテーブルで試合をすることはないので、テーブル1で試合をするケースとテーブルNで試合をするケースの2パターンをしらべて小さい方を解答にすれば良いと考えました(※下図の例①)。ただ、これだとうまくいきません。

次に考えたこと

何パターンか書いてみたら、テーブル1かテーブルNに1ラウンド滞在させれば下図の例②の様に折り返すことでラウンド数を小さくすることができるとわかりました。

f:id:c_taquna:20191229004511j:plain

なので、

  1. 左側に移動して対戦する場合

  2. 右側に移動して対戦する場合

にわけて考えます。あとは、これを実装してきます。

実装

そんなに難しくないので、実装の説明は省きます。 github.com