Quiz https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_h Submit https://atcoder.jp/contests/iroha2019-day1/submissions/5207624 解法 各桁の和をsumとする sumを消費しながら、小さい方から9を詰めていけばいい できた値が入力と同じの…

Quiz https://yukicoder.me/problems/no/462 Submit https://yukicoder.me/submissions/343542 解法 公式解説の通り ハマった所1 最終状態である1が全部立った値を配列に追加する際、シフトを使うがintを使ってしまいオーバーフロー 1<<60 ダメ 1LL<<60 OK …

Quiz https://atcoder.jp/contests/abc125/tasks/abc125_c Submit https://atcoder.jp/contests/abc125/submissions/5171443 解法 A[i]を除外した場合の左右のgcdを高速に求めたい 累積gcdもいいが、平方分割でも解ける sqrt(N)で配列を分割し、ブロックと呼…

Quiz https://atcoder.jp/contests/abc041/tasks/abc041_d Submit https://atcoder.jp/contests/abc041/submissions/5137686 解法 公式解説の通り メモ化再帰を使用 感想 この問題は昔も解説ACしたもの。解説pdfを見て「難しい、よく解けたな」と思う 「メモ…

Quiz https://yukicoder.me/problems/no/658 AC https://yukicoder.me/submissions/342366 解法 公式解説の通り コンパイル vector<vector > を初期化子リストで初期化するにはオプションが必要 g++ -std=c++11 answer.cpp その他 行列ライブラリと言えるほどではない</vector>…

Quiz https://yukicoder.me/problems/no/496 Submit https://yukicoder.me/submissions/342341 類似問題（一次元） https://tdpc.contest.atcoder.jp/tasks/tdpc_contest https://tdpc.contest.atcoder.jp/submissions/5127160 解法 上記一次元のDPと同じ解…

Quiz https://atcoder.jp/contests/abc099/tasks/abc099_c Submit https://atcoder.jp/contests/abc099/submissions/5118558 感想 けんちょんさんの記事 https://qiita.com/drken/items/ace3142967c4f01d42e9 を読んでいたらStrange Bankを「配るDP」で解い…

Quiz https://yukicoder.me/problems/no/527 Submit https://yukicoder.me/submissions/342051 解法 普通にナップサック問題を解く dp[i][j] i : i番目に着目 j : 残りの容量 その時の最大の価値 dpテーブルを埋めた後、dp[0][各重み] == Vなる重みをリスト…

環境 C++ Mac 普段の動き コードを書いた後 g++ answer.cpp && oj t としてテストケースもチェックしている REになると、どこで発生したかわからない どうする？printf? gdb? こうすればいい g++ -g -fsanitize=undefined answer.cpp && oj t オプションを付…

Quiz https://yukicoder.me/problems/no/718 Submit https://yukicoder.me/submissions/341945 解法 公式解説の通り 行列ライブラリ 持ってない・・・。とりあえず必要な掛け算とpowを書いた 2x2限定 using ll = long long; using VV = vector<vector<ll> >; VV mul(VV </vector<ll>…

// 構文解析セット typedef string::const_iterator State; class ParseError {}; ll number(State &begin) { ll ret = 0; while (isdigit(*begin)) { ret *= 10; ret += *begin - '0'; begin++; } return ret; } ll term(State &begin) { ll ret = number(b…

Quiz https://yukicoder.me/problems/no/297 Submit https://yukicoder.me/submissions/341911 解法 公式解法の通り その他 最小値、最大値を式の文字列を作ってから、最後に構文解析で数値にした 例： s = "1+2+3" こうすると式が確認できるので間違いを見…

Quiz https://yukicoder.me/problems/no/447 Submit https://yukicoder.me/submissions/341798 解法 アカウントクラスを作る。メンバは、 各問題のスコア 名前 スコアの合計 sum 最終提出時刻 time ソートしたいので比較operatorも定義する sumで比較 sumが…

Quiz https://yukicoder.me/problems/no/442 Submit https://yukicoder.me/submissions/341618 解法 A*Bが消えたので、long longに収まるようになり、C++でも解くことができました A, Bが互いに素のとき、A+B, A*Bも互いに素である というのを初めて知った。

普段はC++ long longを使うが9 * 1018ほどまでしか表現できない それを超えちゃう時、Pythonで多倍長を使うとその制限を意識せずに済むことがある ということで使いたいときは使えたほうがいい サンプル https://yukicoder.me/submissions/338966 import mat…

Quiz https://yukicoder.me/problems/no/593 Submit https://yukicoder.me/submissions/341442 N進数のmod たとえば4進数1000桁のmod 3を求めたい時 入力を文字列で受け取る 文字列を1文字ずつ受け取りながら処理していくことで求められる ll f(string s, ll…

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…

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

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できるグループ」ごとに…

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

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, 指定の…

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]…

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

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

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

環境 Mac + Visual Studio Code + VSC内のTerminalでg++でコンパイルしている 目的 include<bits/stdc++.h>ができるようにする コードを短くするため 設定 ここに書いてある通りにやった https://www.kodefork.com/questions/16/fatal-error-bitsstdch-file-not-found-mac-o</bits/stdc++.h>…

作成動機 元となる配列サイズ+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>…

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