所見 505解は自明だが、108はよほど軽くないと通らない、と思っていたので嘘高速化を始めてハマった。この問題から学ぶことは多くないが、505でも十分通るという事実は大いに学びである。 問題概要 座標平面上にN個の点がある。内部にK個以上の点を含む長方…

A Fairness 問題概要 高橋君、中橋君、低橋くんがそれぞれ数A,B,Cを持っている。「3人が同時に他の2人が持っている整数の和を求め、それを自分の持っている数に置き換える」という操作をK回行った時、高橋君の持っている数-中橋君の持っている数を求めよ。 …

D Maximum Average Sets Submission #2516578 - AtCoder Beginner Contest 057 所見 解説はなんだか頭よさそうなことをしているけれども、nCrをメモ化すれば愚直にやっても通る。doubleの精度が足りなくて死ぬやつを初めてやった。n時間やって1WAが消えず絶…

D Mixing Experiment Submission #2508458 - AtCoder Beginner Contest 054 所見 二次元DPの表を薬品の回数だけ更新することを思いついたが、解説の三次元DPではやっていることは同じようだ。(多分)三次元になると脳内での構成が不可能になるのでなんとかし…

C K-th Substring Submission #2500157 - AtCoder Beginner Contest 097 | AtCoder 問題概要 文字列sと整数Kが与えられる。sの辞書順K番目のsubstringを求めよ。 取った方針 setはソートされており順番に要素を取り出せ、かつ重複を許さないデータ構造である…

D Candidates of No Shortest Paths 所見 ワーシャルフロイド+ちょっと。更新される辺の数え方を間違えて1WAしたけど40分なので本番でも解けるだろうか。 ワーシャルフロイド周りのバグり方に詳しくなっていくのを感じる(？) 問題概要 自己ループと二重辺を…

D おいしいたこ焼きの焼き方 Submission #2481293 - AtCoder Beginner Contest 005 所見 必要な要素は二次元累積和とテーブル生成による再計算の省略。二次元累積和は見た瞬間思いつけたが、テーブル生成は思いつかず結局1時間50分かけてしまった。とはいえ…

Submission #2454102 - AtCoder Beginner Contest 073 所見 見た瞬間ワーシャルフロイド+next_permutationだということは分かったが、ワーシャルフロイドをバグらせて迷宮入りした。(ありがとう: @rian_tkb) 問題概要 N個の町、M個の道、があって、道にはそ…

Submission #2437277 - AtCoder Beginner Contest 023 所見 二分探索はすぐに思いつくことができるが、高速にスコアPを達成できるかどうかを判定するのが難しかった。ここを典型として処理できるのが上手い人なんだろうと思う。とはいえ、解説を見ずに思いつ…