AtCoder Beginner Contest 188

oooooo (47th)

非常にうまくいった

差の絶対値が 3 未満なら "Yes", そうでないなら "No" を出力してくださいと書かれているのでそれをやる

これも問題文に書いてあるとおり $A_1 B_1 + A_2 B_2 + ... + A_N B_N$ を計算して 0 かどうか判定する

問題名ちょっとすき

強い人が絶対勝つトーナメントで準優勝するのは誰か　

トーナメントの特性上、どう考えても前半の人のうち一番強い人と後半の人のうち一番強い人が最後に戦うのでそのうちの弱い方が答え

定義域が大きい imos 法をやって値をまるめて総和を求めてくださいみたいな問題

map を連想配列として扱えば区間の長さもその間の値もわかるので適当にやれば OK

DAG が与えられる　各頂点で金の売り買いができて、そのときの金額がわかっている　その頂点以外で買った金が売れて、DAG 上でのみ移動できるとき利益の最大化をしろ

脳内を高速でこれ (DPの話 - aizuzia) がよぎります

DAG 上で DP をするときに癖で次数を管理しつつ queue とかもって適当に処置してしまったが、辺が [tex: (X, Y) (X

X, Y が与えられる

1. X に +1 加える

2. X に -1 加える

3. X に 2 かける

の 3 つの操作が許されるとき、最小何回の操作で X を Y にできるか？

E の始点はどこでもいいのかの clar を投げている返答待ちで読んで考察したのが綺麗に刺さって高速に処理できた、嬉しい

Y→X を考えると、操作3は序盤にかなり出てくるはず　今の値が奇数でない限り 3 を選んで、奇数なら ±1 の遷移を両方試すとすると、各状態についてその状態に到達できる最小の操作回数 + Xとの絶対値　が操作回数になる

前者は map 持って bfs みたいにやる、後者はただの足し算　状態数は (多分) $O(logY)$ なので(ガバ議論)、書いてみる　通る　ありがとう

実装方針の選び方は非常によい　筋が悪かったのは E くらいだし、それもあまりボトルネックになった感じはしない

ただ、速解きが上手な FF 内のみなさんが冗長な実装をするのと同等の速さでしか実装できていないのはさすがにどうにかしたい

全体としては大勝利も大勝利なので落ち込みはしないが、調子も運もめちゃくちゃ良くて考察がほぼ0分なのにボロ負けするのはすごいびっくりしちゃうな

F はかなりガバ議論をしたので解説とか他の方針とかをちゃんと追った　再現性のある頭の使い方ができるように練習する

Luzhiled's memo