atcoder.jp 所見 そういえば解くだけ解いて記事書いてないことに気づいて紅白見ながら慌てて書いています、横ではサザンが歌っておる 問題概要 座標平面上にN = 105個の町がある。その町をノード、min(x座標の差, y座標の差)をコスト、としたときの最小全域…

所見 解説見ると明らかに結論ありきの証明で笑ってしまう 問題概要 2つの山があり、それぞれX個とY個の石が置いてある。イカの操作を先手後手が交互に行っていき、先に操作ができなくなった方が負けの時、先手後手のどちらが勝つかを求めよ。 - 片方の山から…

この記事は【IQ1 Advent Calendar 2018】18日目の記事です。 はろー、ymduuさんです。 先日(と言っても三か月前くらいだけれども)、Splatoon2というゲームでウデマエX(一番上のランク的なもの)になったので、よくある(？)それまでにやったこと系記事を書いて…

所見 Submission #3770946 - AtCoder Regular Contest 069 固定すると見通しが良くなるシリーズ 問題概要 N匹のどうぶつが輪になっている状態を考える。羊は左右のどうぶつが同じ種類の時'o'、違う種類の時'x'と答え、狼はその逆を答える。N文字の'o' or 'x'…

Submission #3727392 - AtCoder Regular Contest 064 所見 11月まるまる引退してしまったね、最近残業が増加しており悲しい 問題概要 文字列が与えられる。端を除く文字を先手と後手が順番に取っていく。ただしその文字を取り除くと同じ文字が隣り合うときは…

所見 この問題のように式が与えられてそれを変形するだけで解けると余裕だが、AGC017Bみたいに条件を式にするフェーズがあるとそこで死亡することが多い？ 紙を用意しような (企業コン除く)400点埋まりました 400点終わりです https://t.co/ggRrzZ8q7j pic.t…

beta.atcoder.jp 所見 数学 問題概要 N個のマスがあり、左端にA、右端にBが書かれている。隣り合うマスの数の差がC以上D以下になるようにN個のマスを埋めることができるかを答えよ。 取った方針 2つの隣り合うマスの差の列をY_iと置くとY_iの総和がB-Aになれ…

beta.atcoder.jp 所見 変数を一つ固定すると見通しが良くなるパターン。こういうのは回数って感じだ 問題概要 N色のスライムが存在する。色iのスライムはつかまえるのにa_iの時間がかかり、魔法を使うとxの時間を消費して色iのスライムを色i+1に変えることが…

所見 与えられた手順で"上書き"というのがあるときは手順を逆順にして一つ一つ確定させていくと見通しが良くなる。かしこい。 問題概要 N個のマスに数列が書かれたものが与えられる。以下の操作を好きなだけ繰り返して、黒く塗られたマスに書かれた数の和を…

構築じゃなくとも愚直を書いてから高速化するのって強い動き？教えて強い人 問題概要 要素数2N-1個の順列が与えられたとき、その数(i番目とする、2<=i<=2N-2)の一つ上にi-1番目、i番目、i+1番目の中央値を書き込む、という操作を考える。 この操作をN回繰り…

Minimum Sum Submission #3330734 - AtCoder Grand Contest 005 | AtCoder 問題概要 要素数Nの順列が与えられる。すべての区間の最小値の和を求めよ。 取った方針 N=200000なので、すべての区間を列挙すると間に合わない。a_iが最小値になる区間の個数を数え…

所見 知識はいらないから100%思いついてね、という問題だとほかに持ち出せる知見が無いので解けてもおいしくない。 問題概要 N個の箱があり、1-Nの番号が振られており、1番の箱には赤玉が入っている。2-N番目の箱には白玉が入っている。 操作(xi, yi)を以下…

https://beta.atcoder.jp/contests/abc106/submissions/3067332 問題概要 列車が走っている区間l,rがN個与えられる。クエリp,qがQ個与えられる時、各クエリにおいて[p,q]に完全に含まれる列車の数を求めよ。N<=500、Q<=100000である。 取った方針 dp[l][r]に…

問題概要 数列が与えられる。その連続した区間を取り出すとき、その区間に含まれる数の和がMの倍数である区間はいくつあるか。 取った方針 連続した区間の和を高速に求める->累積和 累積和から区間[i,j]の和を計算する際はj番目の累積和 - i-1番目の累積和 …

所見 気づけてもいいレベルの貪欲だけども、最大流のライブラリが全世界に公開されている今なら最大流したほうが早そう 問題概要 グリッド上に赤い点と青い点がある。赤い点の座標を(rx,ry)、青い点の座標を(bx,by)としたとき、rx<bx && ry<byならばその点はペアになることができる。 最大いくつのペアが作れるか。 取った方針 二人組をたくさん作る->二部グラフの最大マッチング</bx>…

所見 想定された思考パスは前から順番に見ていって区間が閉じる直前にその区間が解決されていなければ処理すればいいよね->これをNlogNくらいでやりたい->開いてる区間を覚えておくのだとNMでつらそう->ソートしておけば貪欲に右端の橋を破壊すればよい くら…

Submission #2868393 - AtCoder Regular Contest 091 所見 さんすう 問題概要 aをbで割った余りがK以上になるN以下の整数の組(a,b)の個数を求めよ。 取った方針 bを固定すると、aをbで割った余りはaが1の場合から順番に1,2,...b-1,0,1,2...とループする。 1,…

所見 グラフに見えるかどうかゲー 問題がグラフに見える程度の能力は類題を解いた直後2週間程度は急上昇する(だがこれは罠でFalse Positiveも増える)ことが知られているので精進って感じだ 問題概要 x軸上にN人の人が居る。これらの人間の位置に関する情報が…

所見 中 学 入 試 (1) aab ccb (2) aabd ccbd (3) aabde ccbde (4) RvvttdWIyyPPQFFZZssffEEkka RLLwwdWIxxNNQUUXXVVMMooBBa を塗り分ける場合の数を求めなさい とかだとむちゃむちゃ中学入試っぽいと思います 問題概要 2*Nマスの範囲に1枚の面積が1マスのタ…

問題概要 1番が黒、N番が白く塗られた木に対し、自分の色に隣接しているノードに先手は黒、後手は白を塗っていくゲームをする、先に色が塗れなくなったほうが負けの時、両者が最適な動きをした場合勝つのはどちらかを求めよ。 取った方針 木はあるノードから…

所見 解説の方針頭良すぎワロタ 問題概要 N枚のカードに整数が書かれている。その中から任意の3枚を取り、最大の数と最小の数を食べ、カードの集合から同じ数がなくなることを目指す。最大で何枚残せるかを求めよ。 取った方針 同じ数が3枚以上あるとき、そ…

所見 グラフ上で連結かどうか->unionfind。そこから先で迷ったが、unionfindがどういうアルゴリズムかを考えると、同じ親を持つノードの数を数えればいいことがわかる。 高速な(経路圧縮した)unionfindを使えばO(K+L+NlogN)。 問題概要 N個の街が、K本の道路…

問題概要 N個の街におけるりんごの価格が与えられる。左から順に街を訪問し、りんごを売買し最大の利益を上げる人がいる。コストcでりんごの売買価格をcだけ変化させることができるとき、最大の利益を1以上下げるのに必要なコストを求めよ。 取った方針 最大…

所見 制約がやばそうな時はやばくなさそうな制約に目をつける。 今回は特に迷わなかった(故に得たものは少ない)のに考えるのに10分、実装に20分かけており虚無。何食ったらじっそうはやくなるんですか 問題概要 HWのグリッドのうちNマスを黒く塗る。グリッド…

D いろはちゃんとマス目 所見 高校数学。 問題概要 H*Wの座標平面がある。 左上のマス目から右下のマス目まで最短経路で移動する方法のうち、下からA個以内、左からB個以内のマスに入らないものを求めよ。 取った方針 高校数学が世界一できないので高校数学…

所見 な～にが算数的センスじゃ 問題概要 数値Nが与えられる。どの5つを選んでも和が合成数となるN個の素数の組を答えよ。 取った方針 何もわからなくて死にたくなる。 頑張って考えると、そういえば素数は4n+1だの6n+5だの色々な必要条件があることを思い出…

Submission #2702414 - AtCoder Beginner Contest 089 所見 クエリがたくさん来る問題が来たら脳死事前計算。制約を読み違えて無限にREした。眠かった(言い訳) 問題概要 H行W列のグリッドに1-H*Wまでの数字が重複なく書かれている。数Dが与えられるとき以下…

所見 ABC100回目らしい。めでたい。 Bで悲しみのコーナーケースに引っかかって悲しみが生まれた。Dが20分で解けたのは成長を感じる？今回みたいな思いつく速度が毎回得られればよいのだけれど。思いつくまでの速度が安定しないと青色は遠そうだなあという感…

所見 ドラマチック。 C Strange Bank https://abc099.contest.atcoder.jp/submissions/2649978 問題概要 1円、6n円、9n円しか引き出せない銀行がある。N円引き出すのに必要な最小手数を求めよ。 取った方針 最初貪欲で行けるような気がしてしまうが、サンプ…

D AtCoder Express 所見 0.5秒ずつシミュレーションすればよいのはすぐにわかるが、1.次の区間の制限速度を守るよう減速できてもその次以降の区間の減速に間に合わない場合がある2.グラフの傾きが変わる際の最高速度の扱いを考える必要がある3.coutの出力で…