F - Strivore

Quiz

https://atcoder.jp/contests/abc171/tasks/abc171_f

有益なTweet引用

Fは昨日のAGCのおかげで割と速く解けた．
「操作列の結果としてあり得るものの個数」を求める時は，結果に重複が生じないように操作列に制約を加えてから操作列の個数を数える，というのは定石っぽいですね．

— opt (@opt_coder) June 21, 2020

アライグマ「今回みたいに、「Sを部分列に持つ文字列」を考えるときは、前や後ろから貪欲にSの文字列だったことにするとうまく1対1対応が作れることが多いのだ！」

— 競技プログラミングをするフレンズ (@kyopro_friends) June 21, 2020

その他

• 自由すぎるときにはこちらから制約を課す

C - One Quadrillion and One Dalmatians 26進数っぽいもの

Quiz

https://atcoder.jp/contests/abc171/tasks/abc171_c

Submission

https://atcoder.jp/contests/abc171/submissions/14599113

解説

• editorialの通りなのですが、26¹, 26², ..., で分割されるグループごとに考えて、答えが何桁かを求める（それをX桁とする）
• X桁内で0-indexedで数えて何番目かを考えて、26進数表記する

その他

• 問題文に704ならaabなどのサンプルが沢山書かれているのでテストケースを追加しやすい
• 「グループ分けして番号を振り直す」という発想

文字列の落とし穴 C++ 「リテラル文字列はそのアドレスを返す」

// そもそもできない
string s = "aaa" + "bbb";

// できるけど、sには謎の文字列が入る。"a"は入らない
string s = ""+'a';

• 「リテラル文字列はそのアドレスを返す」を意識すると、2つ目のコードは""でどこか領域が確保され、+'a'によってアドレスがオフセットされ、そのアドレスがsに入るのだろう。なのでsをcoutなどで確認すると謎の文字列が出力される
• 参考
  • ロベールのＣ＋＋教室 - 第７７章 リテラル文字列 -
  • http://www7b.biglobe.ne.jp/~robe/cpphtml/html01/cpp01077.html
• Pythonとは違うね

B - fLIP O(N)解法

Quiz

https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_b

解説

• editorialにO(N)でも可能と書いてあったのでやってみた
• 行への操作を全探索する
• 縦への操作をa回行って、Kが実現できるかを考える
• 下記画像の最後の式を変形してa=の形に変形し、aが範囲に収まっていれば答え

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M,K;cin>>N>>M>>K;
    if(N>M) swap(N,M);

    if(K==0) yes();

    rep(i,N+1){
      if(N-2*i==0){
        ll blk = M*i;
        if(blk==K) yes();
        continue;
      }
      
      if((K-M*i)%(N-2*i)==0){
        ll a = (K-M*i)/(N-2*i);
        if(0<=a && a<=M) yes();
      }
    }
    no();

    return 0;
}

• AC https://atcoder.jp/contests/code-festival-2017-quala/submissions/14399064

multiset erase (数値指定 / iterator指定)

sorted

• 適当に突っ込んでからprintしてみると、ソートされていることが分かります

#include<bits/stdc++.h>
using namespace std;

int main(){
    multiset<int> se;
    se.insert(5);
    se.insert(3);
    se.insert(5);
    se.insert(2);
    se.insert(7);

    for(int v : se){
        cout << v << endl;
    }

    return 0;
}

// 出力は
2
3
5
5
7

値指定のerase

• 値指定のeraseは、複数あると全部消します

#include<bits/stdc++.h>
using namespace std;

int main(){
    multiset<int> se;
    se.insert(5);
    se.insert(3);
    se.insert(5);
    se.insert(2);
    se.insert(7);

    se.erase(5);

    for(int v : se){
        cout << v << endl;
    }

    return 0;
}

// 出力は
2
3
7

iterator指定のerase

• 複数あっても1つだけ消すことができます

#include<bits/stdc++.h>
using namespace std;

int main(){
    multiset<int> se;
    se.insert(5);
    se.insert(3);
    se.insert(5);
    se.insert(2);
    se.insert(7);

    auto it = se.find(5);
    se.erase(it);

    for(int v : se){
        cout << v << endl;
    }

    return 0;
}

// 出力は
2
3
5
7

まとめ

• うまく使い分けましょう！

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～