suzu-log/g86

LiosK問題2

23:51 |

サンプルが人数60人に対して問題数が10、さらに問題の上限と下限が全部同じなので、Greedyに全部やれば埋まるんじゃね?と思った。

#include <iostream>
using namespace std;

#define Fill(a, b) memset(a, b, sizeof(a))

int main() {

  bool opinion[60][10] = {
    {true,  true,  true,  true,  false, true,  true,  false, true,  true },
    {true,  false, true,  true,  false, true,  false, true,  true,  true },
    {false, true,  true,  true,  true,  true,  false, true,  true,  true },
    {true,  false, true,  true,  false, true,  false, false, true,  false},
    {true,  true,  false, false, false, true,  false, false, true,  true },
    {true,  false, true,  false, false, true,  false, false, true,  false},
    {true,  false, false, true,  false, false, false, false, false, true },
    {false, false, true,  true,  false, false, true,  true,  true,  false},
    {false, true,  false, false, true,  true,  true,  false, true,  true },
    {true,  false, true,  true,  true,  true,  true,  true,  false, true },
    {false, true,  false, false, true,  false, true,  false, true,  true },
    {true,  true,  true,  false, true,  false, true,  false, true,  true },
    {false, true,  true,  true,  true,  false, true,  true,  true,  true },
    {false, false, true,  false, false, false, true,  true,  true,  true },
    {true,  true,  true,  true,  false, true,  false, false, true,  false},
    {false, false, true,  false, false, true,  true,  false, false, true },
    {true,  true,  false, true,  false, true,  true,  true,  true,  true },
    {true,  false, false, false, true,  false, false, false, false, true },
    {false, true,  true,  true,  false, false, false, false, false, false},
    {false, true,  true,  false, false, false, false, true,  true,  false},
    {false, true,  false, false, false, false, false, false, true,  false},
    {true,  false, true,  true,  true,  false, true,  true,  false, true },
    {false, false, false, false, true,  true,  false, true,  true,  true },
    {false, true,  true,  true,  false, false, true,  true,  true,  true },
    {true,  false, false, false, true,  false, true,  true,  true,  false},
    {true,  true,  true,  true,  true,  true,  true,  false, false, false},
    {true,  false, true,  false, true,  false, true,  false, true,  true },
    {false, false, true,  false, false, false, false, false, false, true },
    {true,  false, true,  true,  false, true,  true,  false, false, true },
    {true,  true,  true,  true,  true,  true,  false, true,  false, true },
    {false, true,  true,  false, true,  false, false, false, false, true },
    {true,  true,  true,  true,  false, false, true,  true,  true,  true },
    {false, true,  true,  false, false, true,  false, false, true,  false},
    {true,  false, false, true,  true,  false, true,  false, true,  false},
    {true,  false, false, true,  true,  true,  true,  false, true,  true },
    {true,  true,  false, true,  true,  false, false, false, true,  true },
    {true,  false, true,  false, true,  true,  true,  false, true,  true },
    {true,  true,  false, false, true,  true,  true,  true,  true,  false},
    {true,  true,  false, false, true,  false, true,  true,  true,  false},
    {false, true,  true,  false, false, false, false, true,  false, true },
    {true,  true,  true,  true,  false, true,  true,  false, true,  true },
    {true,  false, true,  true,  true,  false, true,  true,  true,  true },
    {false, true,  false, false, false, true,  true,  false, true,  true },
    {true,  false, true,  true,  false, false, false, true,  false, true },
    {false, false, false, false, false, false, true,  false, true,  false},
    {false, false, true,  false, false, true,  true,  true,  true,  true },
    {false, true,  true,  true,  true,  true,  false, false, false, false},
    {true,  true,  false, false, true,  false, true,  false, false, false},
    {true,  false, true,  true,  false, false, true,  true,  false, true },
    {false, false, false, false, false, false, false, true,  false, true },
    {false, false, false, false, true,  true,  false, false, true,  false},
    {true,  true,  true,  true,  true,  true,  false, false, true,  false},
    {true,  true,  true,  true,  true,  true,  false, true,  true,  false},
    {false, false, false, true,  true,  false, false, false, false, true },
    {true,  false, false, false, false, true,  false, true,  true,  true },
    {false, false, false, false, false, false, true,  true,  false, true },
    {false, false, true,  false, true,  false, true,  true,  false, true },
    {true,  false, true,  true,  true,  true,  true,  false, true,  true },
    {true,  true,  false, false, true,  false, true,  true,  true,  true },
    {false, false, false, true,  true,  false, true,  true,  false, true }
  };

  int cap[10][2] = {
    {3, 5},
    {3, 5},
    {3, 5},
    {3, 5},
    {3, 5},
    {3, 5},
    {3, 5},
    {3, 5},
    {3, 5},
    {3, 5}
  };

  int mem[10];
  bool used[60];
  int wariate[60];
  Fill(used, false);
  Fill(mem, 0);
  Fill(wariate, -1);

  for (int i=0; i<60; i++) {
    for (int j=0; j<10; j++) {
      if (opinion[i][j] && mem[j] < cap[j][1] && wariate[i] == -1) {
	mem[j]++;
	used[i] = true;
	wariate[i] = j;
      }
    }
  }

  bool allFull = true;
  for (int j=0; j<10; j++) {
    if (mem[j] < cap[j][1]) {
      cout << "Exp No." << j << " is not satisfied : " << mem[j] << endl;
      allFull = false;
    }
  }
  if (allFull) {
    cout << "All Experiments are filled by max capacity";
  }

  return 0;
}

実行結果

/Users/suzukitomohiro/srm% ./a.out

All Experiments are filled by max capacity

サンプルデータなら、偶然全部の実験に5人を割り振れたよ!

めでたしめでたし?