所見 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を達成できるかどうかを判定するのが難しかった。ここを典型として処理できるのが上手い人なんだろうと思う。とはいえ、解説を見ずに思いつ…

C 柱柱柱柱柱 Submission #2433397 - AtCoder Beginner Contest 040 問題概要 N本の柱の高さが与えられる。i番目の柱をa_iとすると、一つまたは二つ隣の柱に飛び移るときにabs(a_i - a_i+1)またはabs(a_i-a_i+2)のコストがかかるとき、N番目の柱に着くまでに…

A Zero-Sum Ranges agc023.contest.atcoder.jp 問題概要 長さNの整数列Aが与えられた時、空でない連続する部分列でその総和が0になるものの個数を求める問題。 取った方針 部分列の和を高速に求めたい場合は累積和の利用を考える。S[i] = A[1]+...A[i]なる累…

C Submission #2418387 - AtCoder Beginner Contest 017 問題概要 N(<100000)個の区間とスコアが与えられる。区間を選ぶとその区間に対応するスコアを得ることができる。選んだ区間の和集合が全体を覆ってはいけない時の最大スコアを求めよ。 取った方針 少…

C https://beta.atcoder.jp/contests/abc020/submissions/2411640 問題概要 H行W列(H,W<=10)のグリッドが与えられ、それぞれのマスは白か黒であり、白マスのうち2つがスタートとゴールとして与えられる。 白マスを通過するコストが1、黒マスを通過するコスト…

D Submission #2398508 - AtCoder Beginner Contest 095 所感 累積和をすぐ思いつけたのは成長を感じる。が、累積和だけでは足りない感 問題概要 円形の長さCのテーブルの上にN個のが置いてあり、iは評価値viを持つ。取ることができるの評価値の総和-総移動…

ABC084 D 2017-like-number writeup D https://beta.atcoder.jp/contests/abc084/submissions/2379051 問題概要 Nが素数 && (N+1)/2も素数 を満たす奇数Nを2017 like numberとするとき、Q個以下のクエリ(l,r)について、[l,r]に含まれる2017 like numberの数…

D 所感 ワーシャルフロイドを再発明した。ワーシャルフロイドの理解がふわふわしていたのでACした後ブログに書くのに時間がかかった。 Submission #2372327 - AtCoder Beginner Contest 079 問題概要 数字iをjに変えるときに必要なコストがc[i][j]に 書かれ…

社会人になったので、競技プログラミングを真面目に始めることにした。 自分の身の振り方にいろいろ思うことがあったので。 なにするの ・毎週コンテストに参加(今のAtCoderのシステム知らないけど、ABCもしくはARC)して知見を一定の規則で出力する。 出力規…