公式

B - 花園の列 / Flower Garden Columns 解説 by physics0523 印刷ページ


以下を実装することで、この問題に正解できます。

  • 各列にある花の数 \(cnt=(0,0,\dots,0)\) と初期化する。
  • 以下の流れを \(H\) 行ぶん繰り返す。
    • 現在見ている行のうち、花がある列 \(k\) 全てについて、 \(cnt[k]\) に \(1\) 加算する。
  • \(cnt[k]\) のうち最大値を取る \(k\) (同点があれば、最小のもの)が答えとなる。
    • 最初答え \(res=1\) としておき、 \(cnt[res]<cnt[k]\) なら \(res=k\) と更新することを \(k=2,3,\dots,W\) の順に試すと便利です。

一連の流れは、 if 文や for ループなどを組み合わせることで実装できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int H,W;
  cin >> H >> W;
  vector<int> cnt(W,0);
  for(int i=0;i<H;i++){
    string s;
    cin >> s;
    for(int j=0;j<W;j++){
      if(s[j]=='F'){cnt[j]++;}
    }
  }
  
  int res=0;
  for(int i=0;i<W;i++){
    if(cnt[res]<cnt[i]){res=i;}
  }
  cout << res+1 << "\n";
  return 0;
}

投稿日時:
最終更新: