だらだら競プロ適当解説：AtCoder Beginner Contest 002
AtCoder Beginner Contestの第２回。
まあこつこつやってく。
というか公式の解説があるからこういう雑な解説記事は必要あるかどうか怪しい。
解説で分からなければ、この記事でも結構分からないのでは？
どういう思想でコードを書いたか、みたいなのに注視して記事を書いた方がいいのかもなあ。
総評
ABC001に比べて非常にとっつきやすい問題であり、D問題はかなり典型的な問題で初級者であれば解いて得るものも大きいだろう。
D問の類似は他のコンテストではもちろんのことながら、業務でもそこそこ出てきそうな類の問題である。
A - 正直者
XとYのうち大きいほうを返す。
標準入出力とif文が書ければ問題ない。
略解
int X, Y;
cin >> X >> Y;
cout << ((X < Y) ? Y : X) << endl;
ポイント
特にない。
if文の代わりに三項演算子を使ったが、ifでももちろん問題ない。
競プロだと入力速度を気にする節があるので単に短めのを記載しただけである。
max(X,Y)という記述が実際には一番短い気がする。
B - 罠
文字列がやってくるので母音がなくなった文字列を返すとか。
略解
string W; cin >> W; for (int i = 0; i < W.size(); i++) { switch (W.at(i)) { case 'a': case 'i': case 'u': case 'e': case 'o': break; default: cout << W.at(i); break; } } cout << endl;
ポイント
文字列はcharで格納してもいいが、なんやかんやstringが楽なのでstringをお勧めする。
文字を一つずつ標準出力し、母音の時だけ出力しなければよい。
if文で一個ずつ切るよりswitchでやるほうがやや楽。
Stringにreplaceやremove系の関数がある言語ならそれを使って母音のない文字列を生成してもいい。
C#だと文字列操作が劇的に楽なので、こういう場合に得だなあと思う。
C - 直訴
三角形の面積を求める。
略解
pair<int, int> pos[3]; cin >> pos[0].first >> pos[0].second; cin >> pos[1].first >> pos[1].second; cin >> pos[2].first >> pos[2].second; pos[0].first -= pos[2].first; pos[1].first -= pos[2].first; pos[0].second -= pos[2].second; pos[1].second -= pos[2].second; double ret = abs(pos[0].first * pos[1].second - pos[1].first * pos[0].second) / 2.0f; cout << fixed << setprecision(3) << ret << endl;
ポイント
入力は頂点情報なので迷わずpairで読んでくるといいと思う。
原点を１頂点に含む三角形の面積が|ad−bc|/2っていう公式を使う。
どれか１頂点が原点に来るようにオフセットをかけてずらせばよい。
出力結果が大きくなりすぎるとe+ホゲホゲみたいな表記になりWAくらうのでfixedで明示的に小数点表記設定にする。
D - 派閥
お互い知っているもの同士なら派閥を作成できる。
作れる派閥のうちもっとも大きい派閥を返せばよい。
略解
//おいおいグローバル変数かよ. bool IsGroup[12][12]; int N, M; /// <summary> /// 全探索してすべてのありうる派閥を列挙し、最も大きいグループを返す. /// </summary> /// <param name="n">最大の人数.打ち切りに使う.</param> /// <param name="id">今見ている人の番号.</param> /// <param name="group">どのグループの存在確認をするのか.</param> /// <returns></returns> int Search(int id, int n, bool group[12]) { // 終了処理. if (id == n) //idは0からなので... { int ret = 0; //グループが作れるかの確認. for (int i = 0; i < n; i++) { // グループにいないやつは無視. if (group[i] == false) continue; // グループの人数を数えとく. ret++; for (int j = i + 1; j < n; j++) { // いないのは無視. if (group[j] == false) continue; //グループが作れないならおしまい. if (IsGroup[i][j] == false) return 0; } } return ret; } //再帰処理. group[id] = true;// id番目の人は参加している. int t = Search(id + 1, n, group); group[id] = false;// id番目の人は参加していない. int f = Search(id + 1, n, group); return max(t, f);//大きいほうを返す. } int main(){ //Input. cin >> N >> M; memset(IsGroup, 0, sizeof(IsGroup)); for (int i = 0; i < M; i++) { int x, y; cin >> x >> y; // それぞれの人にどんなつながりがあるか格納. IsGroup[x - 1][y - 1] = true; IsGroup[y - 1][x - 1] = true; } // 再帰部分. bool tmp[12]; int MaxSize = Search(0, N, tmp); cout << MaxSize << endl; return 0; }
ポイント
人数がたかだか１２人なのですべての派閥を全探索をしても２^１２=４０９６程度となり、時間に余裕があることに気が付くかどうか最初のポイントである。
前提として時間制限１秒に対し１００００００回程度の計算は余裕で間に合う。
４０９６派閥に対して、含有確認が略式で１２＊１２程度なので雑に計算して４０００００くらいの計算量になるがこれは十分間に合う。
そのため、すべてのありうる派閥を全探索で列挙し、それらが作成可能かを確認するという流れで実装できる。
全探索する一般的な方法はキューを利用する幅優先か再帰関数を用いる深さ優先の探索である。
ここではメモリ的にも実装的にも楽なので深さ優先を用いた。
再帰関数は終了処理と再帰処理で構成される。
id番目の人が派閥に属するかどうかで分けて再帰すればよい。
１番さんと２番さんにつながりがあるかどうかは、2次元配列で確保する。
他の方法で確保することもできるが、2次元配列であれば１２＊１２と小さいことと両IDを入力すれば一発で解が得られる速度の面で優れているためこれを利用する。
vector等でMをそのまま確保した場合、逐一すべての要素を確認し、IDが含まれているか検索が必要になる。毎回これをやると有意に遅い。おそらく今回の規模なら間に合うとは思うが……
全探索はビットとfor文を利用した方法でもいいらしい。昔そんな書き方した気もするわ。
// N人ならNbitで表現できる. for (int i = 0; i < (1 << N); i++) { // 例えばN=3なら000 001 010 011 100 101 110 111で8個である. // 1<<3はビットでいう所の1000になるので、iは000～111になる. //ここでグループが存在するかしないか判定する. //判定用のグループ情報はiそのものである. for (…) }
ある人のいるいないをビットの０1で解決する。つまり、N人はNビットで表すことができる。
何ループすれば十分であるかはビット数から分かる。
１ずつ足していけば、すべてのビットが1になっているときが最大値になる。
この値は人数分だけ１をビットシフトすれば簡単に求まる。
