-
- いいね！0
Pocala
@microkents
C、自分はmap<string,int>で登場回数を数えてから、予め最大登場回数を求めておき、vector<pair<int,string>>を昇順ソートしたものを左から順に見ていき、i番目の登場回数が最大登場回数と同じなら出力する…をしました
2020-02-16 22:55:05
アルメリア
@armeria_betrue
D→k番目にぶたんはよくあるけど負の数があるせいでつらかった E→最初に考えていたDPの状態定義が微妙に上手く行かないやつでつらかった F→UFで操作区間をシンプルにしてやればいいけどまさかの復元でつらかった
2020-02-16 22:41:45
keymoon
@kymn_
B 読解 C ABCっていつから有志コンになったんですか? C#のDictionaryでは通せなかった D 該当する値で二分探索 TLEがキツい E 繰り上がる場合とそうでない場合を持って下の桁から見る F まず座圧 端点を共有しているもの同士のグループはどの端点からどの端点までも解除できる 復元が辛い
2020-02-16 22:41:11
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「ABC155おつかれさま！ 今回は考察も実装も難しめだったね……。私も時間内に全完できるかどうかちょっと怪しいかも～」
2020-02-16 22:43:41
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「C問題は連想配列を使って、各単語が何回登場したか覚えておけばいいね。辞書順に出力する必要があることに注意だよ！ C言語には連想配列はないから、ソートして地道に数を数えるしかなさそー」
2020-02-16 22:44:41
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「D問題は「答えを二分探索」っていう典型問題……なんだけど、ちょっと大変だね。最初に正の数と負の数が何個できるか求めて、答えの符号を確定させてから二分探索を始めると実装がちょっと簡単になるよ！」
2020-02-16 22:46:01
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「E問題は、例えば価値1のお札を出す個数は、払う金額ピッタリか0かのどっちかしかないから、「下の桁に繰り下がりをしてるか」を状態に持って下から桁DPをすればいいね！ 前回のABC154Eより難しい問題だけど、ちゃんと復習してれば解けたよね？」
2020-02-16 22:48:07
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「F問題は、まず「区間操作は階差をとって2点操作にする」っていうのがポイントだね。そうして「操作で変更される要素を辺で結んだグラフ」を考えると……」 pic.twitter.com/CqmeMQSUhY
2020-02-16 22:50:46
拡大
拡大
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「 「頂点に0か1が決められたグラフがある。辺をいくつか選んで、0の頂点からは偶数本、1の頂点からは奇数本の辺があるようにできるか？」 っていう問題になって、あとはAGC035Bと同じ感じで解けるよ！ ……AGC035Bは700点だから、これもそのくらい難しそうだよ～」
2020-02-16 22:52:23
競技プログラミングをするフレンズ
@kyopro_friends
サーバル「グラフが連結とは限らないから全ての連結成分をチェックしないといけないことに注意してね。AGC035Bの解説では全域木をとってるけど、実際の実装ではわざわざ全域木を作らなくても、DFSを工夫してやればできるよ」
2020-02-16 22:54:53
きり
@kiri8128
D にぶたんでやるんですが、判定にbisectを使うとlogが2つついてPythonだときつそうです。尺取りにすればlog1つでできます。尺取りは実装が苦手なのでこれだけで体感難易度結構あがります。 正と負があるのでさらに複雑です。予め正・負・ゼロに分けて個数もカウントしておきます。
2020-02-16 22:42:53
きり
@kiri8128
x以下かどうかの判定では、xが0以上なら正と負の組み合わせやゼロを含む組み合わせは無条件にOKなのでその分のカウントを加算します。あとは正と正、負と負でそれぞれ尺取りします。 xが負なら正と負で尺取りします。
2020-02-16 22:43:54
きり
@kiri8128
尺取りはバグりそうでしたが、えびちゃんの教えを思い出してなんとかACできました。 twitter.com/rsk0315_h4x/st…
2020-02-16 23:01:47
平積もみる🕢Momiru Hirazumi
@hirakich1310354
ABC155 お疲れさまでした！私は問題セットを組んでいました． A: 難しめ，writer です B: 簡単め C: 難しめ D: 難しめ，writer です．どうして... E: 簡単め F: 簡単め，writer です
2020-02-16 22:40:07
筒隠月子
@otera_locked
E、最初大きい桁からgreedyかなって思ったけど、下の桁の繰り上がりが影響してくるなって思って、逆に小さい方の桁から見ると、小さい方は大きい方に影響されないから、繰り上がるか上がらないかで二者択一dpでできるなってなった
2020-02-16 22:55:59
Hideyuki Tanaka
@tanakh
AtCoder Beginner Contest 155 A: (a == b && a != c) || (a == c && a != b) || (b == c && a != b) とか書いてしまったけど、length(nub)==2で良かったかな B: 全要素について a%2==0?a % 3 == 0 || a % 5 == 0:true C: mapで集計して一番多かったやつしらべてそれでフィルタしてソートして出力
2020-02-16 22:59:03
Hideyuki Tanaka
@tanakh
D: 積がより小さい物がK個未満な数を二分探索で求める。ある数に対して、それ以下の積の数を求めるには、あらかじめ配列をソートしておいてさらに二分探索すれば良い。負の数の場合は範囲が逆になるのに注意。正の数だけなら実装は多少楽だったんだけど、AtCoderもこういうめんどい問題出るのかあ
2020-02-16 22:59:04
Hideyuki Tanaka
@tanakh
E: 上のケタから計算して、余分に＋1払うのを考えたら良くて、各ケタで前のケタで余分に払ってるかどうかの2通りに対してDPすればなんかもとまる。 F: 解けず(´･_･`)
2020-02-16 22:59:04
maspy
@maspy_stars
D： まあ二分探索でできるのですが。非順序対なのが邪魔。これは順序対(i,j)を数えて、i=jを除いて、2で割ります。 iに対してjの個数を数えるわけですが、「1次不等式 ax <= b を解け」ができればよいでしょう。aが正、0、負で場合分けしますよね。
2020-02-16 23:01:50
maspy
@maspy_stars
E：36円差を作る場合 1の位で場合分けしましょう。 ・4円、0円で割り振ったあと、10円以上で40円差を作る ・0円、6円で割り振ったあと、10円以上で30円差を作る 左 n 桁（x）に対して、x円差を目指す場合と(x+1)円差を目指す場合の2値を持てばdpできますね。
2020-02-16 23:07:03
maspy
@maspy_stars
F： 区間加算を疎な情報で処理するのがimos法。2点更新の繰り返しで1111→0000みたいなのをするゲームに帰着。 (a,b), (a,c)について更新できるならば、(b,c)でも更新できて、連結成分ごとに自由な偶数ヶ所を更新できます。構築は全域木をとって根側から切るかどうか決めます。
2020-02-16 23:08:50