No.411 昇順昇順ソート

Quiz https://yukicoder.me/problems/no/411 Submit https://yukicoder.me/submissions/341357 サンプルを理解する (N=5, K=3) K!=1の場合 一般的であるK!=1である場合を考える 下がる時に使う数字は1固定となる サンプルのようにK=3のときは、下がる前にK+1…

構文解析

Quiz https://yukicoder.me/problems/no/49 Submit https://yukicoder.me/submissions/340022 参考 https://gist.github.com/draftcode/1357281 すばらしい。新たな世界が見れた 経緯 たとえば 1234+5678 最初の数字1234は読めたとして、+も読めたとして、56…

No.701 ひとりしりとり

Quiz https://yukicoder.me/problems/no/701 Submit https://yukicoder.me/submissions/339984 解法 a????a をN-1回出力し、最後はanで締める ????の部分は26進数で列挙すれば衝突しない 264 > 100000なので ???? は長さ4で十分 学び N=1000などの大きい時に…

No.74 貯金箱の退屈

Quiz https://yukicoder.me/problems/no/74 Submit https://yukicoder.me/submissions/339953 解法 1枚だけでflipできるコインを調べておく 2枚flipのとき a, bを一緒にflipできるなら、Union Findでunite(a, b)しておく 「一緒にflipできるグループ」ごとに…

No.811 約数の個数の最大化

Quiz https://yukicoder.me/problems/no/811 Submit https://yukicoder.me/submissions/339908 解法 公式解説の通り 約数の数 素因数分解できたとして、そこから作れる約数の数はいくつか {2, 2, 2, 3, 3} を例に復習してみよう

No.416 旅行会社

Quiz https://yukicoder.me/problems/no/416 Submit https://yukicoder.me/submissions/339563 解法 破壊される辺以外を張っておく 破壊クエリを逆から読みながらその辺を復活させていく 木がつながったかはUnion Findで管理する 辺を繋げる前に、今回の接続…

セグメント木 再訪

Quiz https://atcoder.jp/contests/arc033/tasks/arc033_3 Submit https://atcoder.jp/contests/arc033/submissions/5012167 解法 「X番目の値」をlog(200000)くらいの高速で見つける必要がある セグメント木を使う 各値のカウントを持っていて、[0, 指定の…

No.458 異なる素数の和

Quiz https://yukicoder.me/problems/no/458 Submit https://yukicoder.me/submissions/339334 解法 dp[i] : i を異なる素数の和で表した時の最大の和の回数 答えはdp[N] 考察1 dp[i]をより小さいdpで埋めていく よくあるDP しかし今回はダメ dp[7] != dp[2]…

No.105 arcの六角ボルト

Quiz https://yukicoder.me/problems/no/105 Submit https://yukicoder.me/submissions/339320 解法 回転が50度未満なので、(1, 0)の回転後の点はyが正のもののうちxが一番右 その1点だけだけから角度を求める atan2(y, x)を使う 注意点 与えられるデータに…

C - ABCAC 〜はじめてのZ Algorithm〜

Quiz https://atcoder.jp/contests/arc055/tasks/arc055_c Submit https://atcoder.jp/contests/arc055/submissions/4992693 解法 editorialの通り ACまでに踏んだステップ 部分点 20点を狙う |S| > 2000 のときはすぐ終了してテストをすぐ終わらせる a, c …

ローリングハッシュにより文字列検索をO(m*n) => O(m+n)に高速化

参考 蟻本第二版 p332 プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: マイナビ発売日: 2012/01/28メディア: 単行本(ソフトカバー)…

Macで#include<bits/stdc++.h>を導入

環境 Mac + Visual Studio Code + VSC内のTerminalでg++ 設定 ここに書いてあるとおりにやった https://www.kodefork.com/questions/16/fatal-error-bitsstdch-file-not-found-mac-os/ 動機 includeという本質じゃない部分がコードの大きな部分を占めていた…

累積和クラスを作ってみた

作成動機 元となる配列サイズ+1で作ったり、範囲の和を取る時に添え字でミスりそう いつも同じ作成をしているので省略したい Code struct AccSum{ vector<ll> Ac; ll L; AccSum(vector<ll> &A){ L = A.size(); Ac.resize(L+1); FOR(i, 0, L){ Ac[i+1] = Ac[i] + A[i]</ll></ll>…

C - Infinite Grid

Quiz https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_c Submit https://atcoder.jp/contests/s8pc-6/submissions/4981908 解法 editorialの通り 感想 100個くらいつなげて到達可能なら行けそう 迷路で到達可能かどうか、ということで幅優先で解いたらTLE…

No.390 最長の数列

Quiz https://yukicoder.me/problems/no/390 Submit https://yukicoder.me/submissions/19573 解法 公式解説の通りではあるが、各dp[i]についてiの約数を列挙してdpを更新してACした 配るDPがオススメされていたが、制限時間ギリギリそうな列挙でトライした …

3つ組を重複なしで数える tuple + set

用途 (1, 5, 3)と(1, 3, 5)は同じものとして数えたいのでsetに入れて重複除去したい 値が3つあるのでpairには収まらない そこでtuple! Submit https://yukicoder.me/submissions/338555 Code #include <tuple> // new ! set<tuple<ll, ll, ll> > se; se.insert(make_tuple(a, b, c)); </tuple<ll,></tuple>…

Codeforces Round #551 (Div. 2) サーバルセット

A. Serval and Bus https://codeforces.com/contest/1153/problem/A 解法 サーバルがバス停に着く時刻 t 以降(ちょうども含む)で最初に来るバスを各ルートごとに求めればよい B. Serval and Toy Bricks https://codeforces.com/contest/1153/problem/B 解…

フロイドの循環検出法 Floyd's cycle-finding algorithm

始点からうさぎ(fast)と亀(slow)を走らせる fast += 2; slow += 1; 出発からm秒後に出会ったとする ループがあるときは上記の状態になっている ループの始点をOとする ループの一周の長さ:μ ループに入るまでの道の長さ:λ Oからd進んだところでうさぎと亀…

No.726 Tree Game

Quiz https://yukicoder.me/problems/no/726 Submit https://yukicoder.me/submissions/337152 解法 Xの次の素数を見つけ、pxとする。間隔(動けるスペース)はpx - X - 1 Yも同様 (1)+(2)の偶奇で勝敗が決まる 公式解法 X, Yの偶奇を見るだけでよいそう これ…

No.477 MVP

Quiz https://yukicoder.me/problems/no/477 Submit https://yukicoder.me/submissions/336588 解法 他の人は数式で解いていたが、私は二分探索で解いた left = 0 (絶対にMVPが取れない) right = inf (絶対にMVPが取れる) center = (left + right) / 2 cente…

No.123 カードシャッフル

Quiz https://yukicoder.me/problems/no/123 Submit https://yukicoder.me/submissions/336529 解法1 そのままに実装する 制約が緩いので通る 解法2 操作を逆順にたどる この解法で解いた 解法1より速い 星1.5よりは難しい Code int main(){ // input cin >>…

No.64 XORフィボナッチ数列

Quiz https://yukicoder.me/problems/no/64 Submit https://yukicoder.me/submissions/336402 解法 F2 = F1⊕F0 F3 = F2⊕F1 = F1⊕F0⊕F1 = F0 (同じ値をXORすると0になるため) F4 = ... = F1 周期性が見えるので解けました その他 すごく大きい値で直接には解…

No.22 括弧の対応

Quiz https://yukicoder.me/problems/no/22 Submit https://yukicoder.me/submissions/336370 解法 Stackで解いている人が多いけれど、私は別の方法で。 K番目が指すのは ( だと仮定する K以降に読み進めながら、(が来たらcount++, )が来たらcount--していき…

No.111 あばばばば

Quiz https://yukicoder.me/problems/no/111 Submit https://yukicoder.me/submissions/336368 解法 まず、aから始まる回文の数を考える サンプル2の場合 ababababa abaは4つ ababaは3つ abababaは2つ ababababaは1つ 取れる。 一般に1+2+3+...+Nとなりそう …

No.312 置換処理

Quiz https://yukicoder.me/problems/no/312 Submit https://yukicoder.me/submissions/336225 解法 解説の通り 素数を探すときはsqrt(N)まででいい、という定石 落とし穴 N = 大きい素数 x 2 のとき、解はNではなくN/2 この問題の設定により、2で割るチェッ…

No.228 ゆきこちゃんの 15 パズル

Quiz https://yukicoder.me/problems/247 Submit https://yukicoder.me/submissions/336214 画像 テストケース2 解法 シミュレーションする 0の置かれている位置にあるべき数字を考える 画像で言えば「12」(3行目4列目なので) そのあるべき数字は上下左右に…

No.561 東京と京都

Quiz https://yukicoder.me/problems/no/561 Submit https://yukicoder.me/submissions/336212 解法 動的計画法を使う dp[2][N] dp[i][j] i : 0:東京 1:京都 j : j日目 (0-index)の仕事を終えた後のお金 とする 前日の稼ぎと当日の稼ぎの関係は 前日東京→ 当…

B - 交通費

Quiz https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b Submit https://atcoder.jp/contests/bitflyer2018-final-open/submissions/4881138 解法 editorialの通り 感想 lower_boundでiteratorを取ってきた後、+1, -1をした…

No.198 キャンディー・ボックス2〜三分探索〜

Quiz https://yukicoder.me/problems/no/198 Submit https://yukicoder.me/submissions/335991 解法 キャンディーの目的値を決めると操作回数が決まり、これは下に凸の関数になる 三分探索すればいい 学び while(right-left>3){ ll p0 = (2 * left + 1 * rig…

No.65 回数の期待値の練習

Quiz https://yukicoder.me/problems/no/65 Submit https://yukicoder.me/submissions/335985 解法 振る回数の更新式は提供されている E(K)以降は、もうK回を達成しているので振る回数は0であることに気づけば、後ろからのDPができる