AtCoder Beginner Contest 107 B - Grid Compression

提出へのリンク

なんか汚いな…と思って提出して解説読んだら案の定エレガントで、削るんじゃなくて残す行と列マークして交差する文字だけ出力すれば良かった。

書いてるときに basic_string::erase で一瞬ハマった。

for (auto &l: ans) {
  l.erase(j,1);
}

ans は vector<string> です。range-for で参照すれば要素が変更できるのはいいとして、 erase は引数が int 1つだけだとそれ以降の要素が全部消えちゃうんですよね。何個消すか指定する必要がある。普段イテレータで指定してたから気づかなかった。

参考: cpprefjp basic_string::erase

AtCoder Beginner Contest 082 B - Two Anagrams

AtCoder ABC 競技プログラミング

提出へのリンク

  string s,t;
  cin >> s >> t;
  sort(ALL(s));
  sort(ALL(t),greater<char>());
  if (s<t) cout << "Yes" << endl;
  else cout << "No" << endl;

任意の順に並べ替えて s' < t' であるような文字列が作れればよいので、s をめいっぱい辞書順で早く来るよう昇順でソートして、 t をめいっぱい遅く来るよう降順でソートするだけ。文字列の大小比較まで含めて「なんとなくこう動きそうだな」と思って書いたら通った。C++の仕様を作った人えらい！（コウペンちゃん）

イカはやらずに就寝。

AtCoder Beginner Contest 043 B バイナリハックイージー

提出へのリンク

A問題ばっかやってたら AtCoder Problems のリコメンデーションが簡単な問題ばかりになってしまった。すみません（誰に？）。

この問題は素直に受け取った文字列通りに文字列をつくるだけですね。何でもいいと思いますが僕は vector<string> で作りました。 vector が空のときに pop_back しないようにだけ気をつければ大丈夫だと思います。

イカは最近ガチマッチサボリ気味なのでちょっとそろそろ体調整えてやっていこうと思います。最近睡眠リズムが後ろにずれちゃって研究室滞在時間も夜遅くになってしまっていたので、帰宅後ガチマッチやる体力がね…朝無理くり起きて生産性ゼロになっても許されるお盆休みで調整しよう。

ABC137 A,B,C,D 反省会 -- priority_queue と料理

競技プログラミング AtCoder ABC

提出一覧へのリンク

A: max 2 回やったけど initializer-list 使えば解説のとおり 1 回で済むね

B: i < -1000000 || i > 1000000 だったら除外しなきゃとかやったんだけどいま制約条件みたら 0 <= X <= 100 だったわ

C: 最初は sort して multiset<string> に放り込むときにダブリをいちいち数えるコードにしたんだけど、提出するときに制約的に TLE しそうだなーと思ったら案の定 TLE した。 map<string,int> にして少し工夫したら通った。あと解説放送みてたら同じく map<string,int> ではあるものの、ペアの数ではなく同じ文字列の個数のみ記録して最後に個数から i*(i-1)/2 の総和取ってて頭いいなと思った。あとこういうときは unordered_map でいいねって言ってた。確かにハッシュ化されてればよくて、ランダムアクセスは不要な問題。

D: 終了間際に解法は思いつくも、自力実装30分やってもバグったので諦めて解説放送みた。解説放送みたら v[M-a].pb(b) していて、何日目に実行可能な仕事であるかという情報を vector のインデックスに入れてしまうのは、取得がバグりにくくてめちゃめちゃ頭いいなと思った。

D の実装で vector から条件を満たすものを探して取得して削除して、なんてことを何行もかけて書くと必ずバグることを痛感した。インデックスでアクセスしようがイテレータでアクセスしようが、要素を削除するとずれる。それよか、解説放送のように vector の vector にしてしまって、削除の必要がないデータ構造にしてしまうほうが安全。

  int N, M;
  cin >> N >> M;
  vector<vector<int>> v(M);
  REP(i, N) {
    int a,b;
    cin >> a >> b;
    if (a > M) continue;
    v[M-a].pb(b);
  }

  int ans = 0;
  priority_queue<int> que;

  DEC(i, M-1, -1) {
    for (auto b: v[i]) que.push(b);

    if (!que.empty()) {
      ans += que.top();
      que.pop();
    }
  }

  cout << ans << endl;

priority_queue の使い方だが、pair<int,int> みたいに複雑なものを入れて Compare をがんばって自力で書いてバグらせるよりは、条件満たしたものを単に int で突っ込んで最大値をそのまま top で取り出して pop で消すだけ、としたほうがいい。料理と同じで下ごしらえをちゃんとやる方がシンプルに書けるし手が楽。

料理と同じといえば、今回は最終的な状態から時系列的に逆行して貪欲法やればよいという点も料理に似ている。まあ何でもかんでも逆算すればよいというものでもなくて、今回たまたまそうだっただけで、料理も逆算ばかりが重要なわけではなく、途中行程の特に1箇所がとても重要な料理もあり、競プロも TLE しないための工夫が大事だったり、とにかく台所に揃えておきたい選択肢が多いという意味のほうがむしろ料理と競プロの似ているところかもしれない。

おいしい料理も競プロも僕はまだまだ手探りです。

すべての数字が異なるような日付を探す

リンク切れたときのために問題文引用しておくと

問題 本日は2019年8月7日だが、この日付に使われている数字はすべて異なる。次にこのような日になるのはいつか。

月とか日付がゼロフィルされてないところが微妙に面倒な問題。

C++で日付扱うのめんどくさいなーと思ったのでとりあえずJSで書きました。

let d = new Date(2019,7,7);
let flg = true;
while(flg){
  d.setDate(d.getDate()+1)
  const str = d.toISOString().replace(/-/g,"");
  const set = new Set();
  for (let i = 0; i < 8; ++i) {
    if (i == 4 || i == 6) {
      if (str[i] == 0) continue;
    }
    if (!set.has(str[i])) {
      if (i == 7) {
        flg = false;
      }
      set.add(str[i]);
    }
    else break;
  }
}
console.log(d.toISOString());

JS は JS でフォーマットが ISO と各地域の独自表記しか対応してないんですね。まあそういう npm モジュールあるだろうしね。