方針

今までは覚えておきたいトピックや小ネタなどをKobitoに蓄積/Qiitaに投稿していたが、

  • Qiitaだとプログラミング関係の話(研究など)やコードを書きにくい
  • Qiitaは短すぎるエントリーに向いていない
  • Kobitoだと検索機能が物足りない、PDFの埋め込みができない
  • Evernoteは大げさすぎる

などの理由から、ブログ形式が良いのではないかとの判断に至った。

なので、今後はこちらに移行したい。

  • まとまった一連のプログラミング関連の話
  • 個人的な研究の進捗状況などの細かい話

などは今まで通りKobito/Qiitaを使う予定。

SRM674 Div2 Medium

整数の組の点集合が与えられて、任意のxy軸を設定したときに両軸上に乗っている点の数の最大値を求める。 点の数の最大値が50なので全探索で大丈夫。

任意の2点で片方の軸を固定した後、追加でもう1点指定すれば両方の軸が固定されるので、 固定された軸に対して全点がそれぞれ軸上にあるか判定していけばOK。

コードはハンドルネームHalfSummer11さんのものを少し改変(軸に乗っているかどうかの判定の1つ目の式を変更)して引用。

int bestShot(vector <int> x, vector <int> y)
{
    int n = x.size(), ans = 0;
    if (n <= 2) return n;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            for (int k = 0; k < n; ++k){
                if (k != i && k != j){
                    int cnt = 0;
                    int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j], x3 = x[k], y3 = y[k];
                    for (int p = 0; p < n; ++p){
                        int xx = x[p], yy = y[p];
                        if ((1ll * (x2 - x1) * (yy - y1) - 1ll * (y2 - y1) * (xx - x1) == 0) || (1ll * (x3 - xx) * (x2 - x1) + 1ll * (y3 - yy) * (y2 - y1) == 0)) ++ cnt;
                    }
                    ans = max(ans, cnt);
                }
            }
    return ans;
}

SRM674 Div2 Easy

与えられた2つの集合が全単射かどうか判定。

struct RelationClassifier {                                                                                                                                                                                     
    vector<int> domain;                                                                                                                                                                                         
    vector<int> range;                                                                                                                                                                                          
    string isBijection(vector<int> _domain, vector<int> _range) {                                                                                                                                               
        domain = _domain, range = _range;                                                                                                                                                                       
        multiset<int> d, r;                                                                                                                                                                                     
        if (domain.size() != range.size() ) {                                                                                                                                                                   
            return "Not";                                                                                                                                                                                       
        }                                                                                                                                                                                                       
        REP(i, domain.size()) {                                                                                                                                                                                 
            d.insert(domain[i]);                                                                                                                                                                                
            r.insert(range[i]);                                                                                                                                                                                 
        }                                                                                                                                                                                                       
                                                                                                                                                                                                                
        REP(i, domain.size()) {                                                                                                                                                                                 
            if(d.count(domain[i]) > 1 || r.count(range[i]) > 1) {                                                                                                                                               
                return "Not";                                                                                                                                                                                   
            }                                                                                                                                                                                                   
        }                                                                                                                                                                                                       
        return "Bijection";                                                                                                                                                                                     
    }                                                                                                                                                                                                           
};

コードはGreedで生成しています。