はまやんはまやんはまやん

hamayanhamayan's blog

2020-05-02から1日間の記事一覧

Japan Tech News #020 2020/05/02

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest 障害対応時にまずはissueを作ると良い - そーだいなるらくがき帳 良い記事。issueのテンプレートを行動指針にするという流れは素晴らしいと思う 障…

LIS on Tree [AtCoder Beginner Contest 165 F]

https://atcoder.jp/contests/abc165/tasks/abc165_f 前提知識 座標圧縮 セグメントツリーを使ったLIS解法 永続セグメントツリー(部分永続でOK) 解説 https://atcoder.jp/contests/abc165/submissions/12637772 データ構造ズルをして解いた。 自分は手元に…

Rotation Matching [AtCoder Beginner Contest 165 E]

https://atcoder.jp/contests/abc165/tasks/abc165_e 解説 https://atcoder.jp/contests/abc165/submissions/12644257 頑張ってスマートな方針を考える。 最も厳しいパターンで方針を考えるのが良いだろう。 今回であれば、対戦相手が少ないほど、再戦の可能…

Floor Function [AtCoder Beginner Contest 165 D]

https://atcoder.jp/contests/abc165/tasks/abc165_d 解説 https://atcoder.jp/contests/abc165/submissions/12646306 D問題にしては難しい問題に見えるし、計算過程に実数も入ってくるので、とりあえず実験コードを書いてみる。 xを[0,N]に動かして何か発見…

Many Requirements [AtCoder Beginner Contest 165 C]

https://atcoder.jp/contests/abc165/tasks/abc165_c 解説 https://atcoder.jp/contests/abc165/submissions/12649721 メタ読みをする。 制約を見ると、数列Aの全探索ができそうな感じ。 dfsを使って数列を全探索していこう。 dfsを使った数列の全探索方法が…

1% [AtCoder Beginner Contest 165 B]

https://atcoder.jp/contests/abc165/tasks/abc165_b 解説 https://atcoder.jp/contests/abc165/submissions/12650100 制約が1018となっている、C++ではintではオーバーフローするので、long longで受け取ること。 入力例で1000000000000000000は3760とある…

We Love Golf [AtCoder Beginner Contest 165 A]

https://atcoder.jp/contests/abc165/tasks/abc165_a 解説 https://atcoder.jp/contests/abc165/submissions/12650463 ジャンボ高橋君の出せる飛距離のパターンは103通りくらいなので、全部試してKの倍数があるか探そう。 体感としては全列挙したときに107通…

直方体大学 [yukicoder 1045]

https://yukicoder.me/problems/no/1045 前提知識 bitDP 解説 https://yukicoder.me/submissions/475059 制約からbitDPを感じるので、その方針で考えるとできる。 遷移込みで状態を考えると、以下のようにすればいいと分かる。 dp[msk][lst][hei] := 使用済…

正直者大学 [yukicoder 1044]

https://yukicoder.me/problems/no/1044 解説 https://yukicoder.me/submissions/475051 説明のため、N人の正直者を正直者1, 正直者2, ..., 正直者Nと呼ぶことにする。 円の数え上げの典型テクを使う 「1つを先頭として固定することで、列の数え上げにする」…

直列大学 [yukicoder 1043]

https://yukicoder.me/problems/no/1043 前提知識 動的計画法 累積和 解説 https://yukicoder.me/submissions/475040 初手がなかなか難しいし、色々なテクを必要とするので、少し難しい問題。 逆に言うと理解すれば色々な技を得られるだろう。 制約を見ると…

愚直大学 [yukicoder 1042]

https://yukicoder.me/problems/no/1042 前提知識 二分探索 解説 https://yukicoder.me/submissions/475012 N^2 <= P + QNlogNを満たす最大のNを求めよという問題。 ★の感じから二分探索すればよさそう。 普通に二分探索する。 テクニックとして小数の比較に…

直線大学 [yukicoder 1041]

https://yukicoder.me/problems/no/1041 解説 https://yukicoder.me/submissions/475004 考えられる直線は無限にあるのだが、最大個数の点を通すであろう直線に絞って考える。 最大個数の点を通すであろう直線は少なくとも2点は通っている直線であることが言…

垂直大学 [yukicoder 1040]

https://yukicoder.me/problems/no/1040 解説 https://yukicoder.me/submissions/474982 答えは、90度、270度、450度、630度、…であるが、手計算で既に間違えそう。 Nは360で割った余りを使えば、全部の角度を[0,360)の間に入れることができる。 すると、条…