Quiz https://atcoder.jp/contests/arc017/tasks/arc017_3 サイズぴったりのナップサック問題。N=32 AC https://atcoder.jp/contests/arc017/submissions/27468319 解き方 前半後半で半分に分ける(N=16ずつ) 前半のみで、各荷物を使うかどうか0/1で全パター…

Quiz https://atcoder.jp/contests/arc005/tasks/arc005_2 Submit https://atcoder.jp/contests/arc005/submissions/4127074 補足 27x27のchar配列を作成 水平反転・垂直反転した9x9を貼り付ける 振り返り 今回の方針は、 正しく実装できていることが確認し…

『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ 効率的なアルゴリズムって何に役立つの？に対して分かりやすい解答

Quiz https://atcoder.jp/contests/arc002/tasks/arc002_2 Submit https://atcoder.jp/contests/arc002/submissions/4120342 補足 意外と大きくなりすぎてしまった 再利用する機会があるといいな struct MyDate{ int year; int month; int day; const static…

Quiz https://atcoder.jp/contests/arc052/tasks/arc052_b Submit https://atcoder.jp/contests/arc052/submissions/4119989 補足 普通に求めてもよさそう O(NQ) = 107 editorialを見ると、 輪切りにして配列に入れる それを累積和 この方法だとO(NH) = 106 …

Quiz https://atcoder.jp/contests/agc008/tasks/agc008_a Submit https://atcoder.jp/contests/agc008/submissions?f.User=peroon 補足 最初は+, -, 大小で場合分けで書いていたが書き間違えやすくてWA editorialのように発想を変えて書くと、バグりようの…

Quiz https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d Submit (TLE) https://atcoder.jp/contests/nikkei2019-qual/submissions/4108450 補足 コンテスト中、queueを使った幅優先をしつつ、距離dが大きくなるときは更新 しかしTLE dが…

Quiz https://atcoder.jp/contests/arc054/tasks/arc054_c Submit (WA) https://atcoder.jp/contests/arc054/submissions?f.User=peroon 補足 7つWAが出てしまうので撤退 doubleで行列を持っている 掃き出し法で上三角行列にして行列式を求めるが、N=200にな…

Quiz https://atcoder.jp/contests/arc054/tasks/arc054_b Submit (微分して０) https://atcoder.jp/contests/arc054/submissions/4082650 指数関数の微分や式変形でミスが入り込んで時間を食った 実装完了すれば探索なしに一発で解が出て速い Submit (三分…

LCS (Longest Common Subsequence) 文字列s, tの最長の共通部分を見つける naoyaさんの記事が分かりやすい http://d.hatena.ne.jp/naoya/20090328/1238251033 DPで解く 計算量O(N*M) // LCSセット const int S_LEN_MAX = 6000; ll dp[S_LEN_MAX][S_LEN_MAX];…

Quiz https://atcoder.jp/contests/abc005/tasks/abc005_4 Submit https://atcoder.jp/contests/abc005/submissions/4079770 学び 2D累積和を求める前に、行毎に累積和を求めておけば矩形和もO(N)で求まる その他 発想は難しくなく、きっちり実装すればいい …

Quiz https://atcoder.jp/contests/abc007/tasks/abc007_3 Submit https://atcoder.jp/contests/abc007/submissions/4074284 補足 基本の幅優先。アルゴリズムの実装はこういうサイトでテストケースの多い状態で確認した方がいい 意外と時間がかかってしまっ…

Quiz https://atcoder.jp/contests/abc008/tasks/abc008_4 Submit https://atcoder.jp/contests/abc008/submissions/4073952 補足 99点解法 普通のdpのように小さい方から積み上げていくのはイメージしづらいので、分割統治法＋メモ化の書き方で書いた

Quiz https://atcoder.jp/contests/abc010/tasks/abc010_4 Submit https://atcoder.jp/contests/abc010/submissions/4065384 意外とTLEにもならず一発で通って良かった パスを何度も求めるのを関数化したのが良かった 見やすい 変数名の自由度が上がる 学び …

Quiz https://atcoder.jp/contests/abc011/tasks/abc011_4 Submit https://atcoder.jp/contests/abc011/submissions/4062978 その他 パスカルの三角形でnCrを事前計算 nCrで持つと1000_C_500等の時に10300くらいの値になってWAになる long doubleで持っても…

const int N_MAX = 1001; ll pascal[N_MAX][N_MAX] = {}; void calc_pascal(){ FOR(i, 0, N_MAX){ pascal[i][0] = 1; } pascal[1][1] = 1; FOR(i, 2, N_MAX){ for(int j=1; j<=i; j++){ pascal[i][j] = pascal[i-1][j] + pascal[i-1][j-1]; } } } ll nCr(ll …

Quiz https://atcoder.jp/contests/abc116/tasks/abc116_d Submit https://atcoder.jp/contests/abc116/submissions/4062082 補足 コンテスト中に頑張ったけれど解けなかった問題 落ちついてやってみると、コンテスト中よりシンプルなコードになった 実装が…

1年くらい前にPythonで参加していて水色直前まで行っている 今回、ABC116のCまでを解いて、終了後、水色になっていた A, B, Cまで25分で解いて、残り75分をDにつぎ込んだが通せなかった D 美味しさ順にソートして第一候補を求める それと、ネタ数重視でも求…

Quiz https://atcoder.jp/contests/abc012/tasks/abc012_2 秒数が与えられるのでhh:mm:ssに変換する問題 時間hが決まったらその分を秒数から引いて・・・とやっていた。しかし！ 他の人の解答 https://atcoder.jp/contests/abc012/submissions/4017036 int m…

cout ver cout << setw(2) << setfill('0') << h; cout << ':'; これをcout, stringstreamで使えばいい printf ver int main(){ //cin.tie(0); //ios::sync_with_stdio(false); int a; cin>>a; int h=a/3600,m=(a%3600)/60,s=a%60; printf("%02d:%02d:%02d\n…

Quiz https://atcoder.jp/contests/abc013/tasks/abc013_4 Submit https://atcoder.jp/contests/abc013/submissions/4044947 補足 最初、あみだくじ1回分（連結なし）をそのままシミュレートしていたらTLE あみだくじを後ろからのSwapで書くことでO(M)になり…

Quiz https://atcoder.jp/contests/abc018/tasks/abc018_4 Submit https://atcoder.jp/contests/abc018/submissions/4036464 注意点 どの女子を選ぶかをnext_permutationで総当たりした ※next_permutationを使うときはその配列を事前にソートしておくこと ソ…

Quiz https://atcoder.jp/contests/abc022/tasks/abc022_d Submit https://atcoder.jp/contests/abc022/submissions/4031267 補足 「重心 - 最遠点」の方法で解いた 最初、max, minを書き間違えて「重心 - 最近点」で提出していた 部分的にWAになる editoria…

Quiz https://atcoder.jp/contests/abc024/tasks/abc024_d Submit https://atcoder.jp/contests/abc024/submissions/4028887 その他 逆元の考え方は知っていた サンプルでは通ったけれどテストでWAが一部出て困り、他の人のコードを見た 四則演算をするごと…

Quiz https://atcoder.jp/contests/abc020/tasks/abc020_d Submit https://atcoder.jp/contests/abc020/submissions/4025064 補足 101点満点の100点解法 N<Kもありうる その場合は等差数列の恩恵がないのでforでN分まわす N>100は諦めるので、大きいNが来たらWAでいいので何か答えを返す TLEがなくなるので、ジャッジ待ちが減</kもありうる>…

Quiz https://atcoder.jp/contests/abc020/tasks/abc020_c Submit https://atcoder.jp/contests/abc020/submissions/4023131 補足 xを二分探索。探索1回ごとにワーシャルフロイドで最短経路を求める 私の場合、今までワーシャルフロイドを使うときは双方向で…

Quiz https://atcoder.jp/contests/abc026/tasks/abc026_d Submit https://atcoder.jp/contests/abc026/submissions/4013817 補足 これは二分探索だな やってみると、単調増加ではないから二分探索が正常に動かない説 その後、ちゃんと動くと分かった テスト…

struct Node{ string name = "default name"; Node(){} vector<Node> children; }; int main() { auto node0 = Node(); auto node1 = Node(); node0.children.push_back(node1); node1.name = "new name"; cout << node0.children[0].name << endl; } default name</node>…

テストケースは1つの時もあるし、4つくらい豊富に用意されているときもある テストが多いと、問題の読み間違えや抜けに気づきやすい よって、ケアレスの傾向がある人はコンテスト中、テストケースの多い問題を優先して解くといい

Quiz https://atcoder.jp/contests/abc030/tasks/abc030_d Submit https://atcoder.jp/contests/abc030/submissions/3994273 補足 でかすぎる値k mod 123456 を求められれば満点 long longには収まらないのでstringで受けとる bigMod関数で処理してACした 借…