ABC131-E スター/ウニというグラフ

提出へのリンク

1からそれ以外への頂点すべてに辺を生やしたグラフをスターやウニというらしい。考えた人頭いいな。ウニは頂点間距離の調節がしやすくて応用が効きそう。

構成可能かどうかの判定は、連結でなければいけないという条件から、ありえる頂点対の個数の最大値 N(N-1)/2 から最低限必要な辺の数(例えばパスグラフをつくるのに必要な数)である N-1 を引いた値が K の最大値になる。距離が2である組は1組ずつ減らしていくことができるので最小値は0かつその間の区間すべて可能。

はじめはパスグラフを起点にして完全グラフにするまで辺を加えていく方針で考えましたが、辺を加えたときに条件を満たす組の個数が増えたり減ったり変わらなかったりするので降参しました。条件分岐として整理するか、辺を加えるごとに条件を満たしているかチェックするよう実装して全探索すればできそうな気もします。


夜遅いのでイカはやらないで寝るかな…

コンテナからある値以上、以下、 more than, less than を探す

初稿では「ソートされてる必要はない」と書いていましたが、イテレータ-- している関係上やっぱりソートされてるほうがいいです。

以上

昇順のコンテナである値以上である最初の要素へのポインタ。

lower_bound()

以下

昇順のコンテナである値以下になっている最後の要素へのポインタ。

--upper_bound()

または対象のコンテナを v として lower_bound で右から走査する

lower_bound(
  v.rbegin(),
  v.rend(),
  i,
  [](const int &a, const int &b){
    return a > b;
  }
)

以上、以下ともに等号成立は自分で調べる必要がある。


more than

昇順のコンテナである値よりも大きい最初の要素へのポインタ。

upper_bound()

less than

昇順のコンテナである値よりも小さい最後の要素へのポインタ。

--lower_bound()

ABC136 A,B,C,D 反省会

提出へのリンク

終了直後にACした図
やったねACだよ

A: #define int long long してたので max(c - (a - b), 0LL) のようにリテラルつける必要があった

B: 桁数えるのに手間取っちゃって to_string(i).length() % 2 != 0 で全探索した

C: for 文手書きすると i が N になってたりして本当に良くない。懲りて DEC(i,a,b) マクロを追加した

D: 最初は各マスについてループするまで全探索したが TLE したため、20分ほど考えたら RL があるところにしか子供は残らないことに気づき実装した。が、lower_bound に関数オブジェクトを渡しても渡しても CE してしまう。 bits/stdc++.h を include してると思ったらしてなかったんですよね。無事気づいて AC です!


冒頭の画像を見て、おわかりいただけただろうか。提出日時が終了90秒後となっているのである。デバッグの途中で消された bits/stdc++.h の怨念がこのような悲惨な光景を作り出してしまったのだろうか。取材班はこのあと供養のためにスイカを食べてイカをやったという。

(なかなかに悔しかったので gcc 入れました。)


別の記事書いてるときに気づいたけどそもそも --upper_bound() 使えば D で CE することなかったわ。

ABC131-D ソートを考慮した vector<pair<int,int>> を作る

提出へのリンク

締切が遠いものから着手して他の締切をブッチしてしまってはしょうがないので、締切が近いものから手を付ける。 vector<pair<締切,所要時間>> を作り、素直に std::sort する(ABC128-Bでもやったように)。

締切が同じタスクがあれば、同じタスク同士ではどういう順番でやっても良い。すべて間に合うときはどんな順番でも間に合い、どれかが間に合わない場合はどんな順番でも間に合わない。


今日は研究に熱が入ったためイカはお休み。と思ったがナワバリだけやった。

ARC081-C map と multiset

提出へのリンク

長い方から2本1組ずつ取っていき、2組つくれた時点で終了です。

最終的には map<int,int> でやりましたが、途中までは multiset<int> でやっていました。しかし multiset だとソート済みとはいえ結局同じ値が複数個含まれているので、いちいち個数を調べるのは配列を使っているのと大差ないです。値からその個数への map を用いることで、走査をシンプルにしました。


イカはデュアルスイーパーカスタムでガチアサリ B+ 1勝0敗でした。あとナワバリはハイドラントカスタムで何試合か。ハイドラントといいダイナモローラーといい、ああいう重い武器が好きなんですよね。WoTもKV-2などの重い重戦車や駆逐戦車が大好きです。

ちなみに研究してたら使ってるライブラリのバグを見つけました。該当箇所は1995年に書かれて、2006年くらいまでたまに更新されていたようです。歴史を感じる。

ABC135-D DP 精進しよう / stack の大きさ

提出へのリンク

30分ほど考えてもTLEしない方針すら立たなかったため、解説を読んだ。が、眠い頭ではなかなかわからなかったのでとりあえず写経し、8ケースでバグったので最速正解者のコードに合わせて修正したら通った。

解法は動的計画法で、文字列を左から順番に見ていき、ある桁を見たときにその桁が i だったとして、その直前のすぐ左の桁までで構成される数字が n だったとすれば、単純に n * 10 + i を 13 で割った余りこそが、今見ている桁までで構成される数字を 13 で割った余り r となる。 d = n % 13 とすれば、すでに割り切れた部分を 10 倍してもどうせ 13 で割り切れるので、 r = (d * 10 + i) % 13 となる。この余りだけ足して 13 で割って、を最後まで続けると答えが求まる。


ちなみにバグの原因は main 関数内で配列を宣言したことによるサイズ不足だったと思われる。ローカル変数は stack に置かれるが、stack は あまり大きくないので大きな配列でおかしなことが起こるらしい。対策としては、関数外で宣言する、static つける、newmalloc で動的に宣言する、vector 使うなどがある。(参考リンク1参考リンク2

実際配列をグローバル変数として宣言したり static つけたりしたら通った。

バグったときに RE (runtime error) が返ってこなかったということは、配列のサイズが不足しても stack overflow にならないことがあるんだろうか。 vector 使うのが安全かなー。

ちなみに今夜のイカはナワバリのみでした。

ABC135-C

問題へのリンク

前から食っていけばいいのでは?と実装したらWA。

じゃあ後ろから食っていけばいいのでは?と実装したらWA。

解説読んでも前から食えとしか書いていない。

long long にしたら通った。109 を 3 回足すだけで int からあふれてしまうので、それもそうでした。

これを期にスニペットをつくりました。以前他の人のコードみたらいつも long long 使ってたので多分大丈夫だと思います。

精進グラフはまだまだ灰色です。

ちなみに 1000日 Splatoon は昨日ガチアサリが B から B+ になりました。ガチアサリ以外は A 帯なんですが、ガチアサリ苦手なんですよね、一気にKOまでもってかれやすくて…