久々の更新ですが，メモを書いておきます． 深さ優先探索において，母親を指定しておくと一回行ったかどうかを判定しなくてもいい．

問題 D - Wide Flip はじめに あけましておめでとうございます。 今年も精進していきます。 考え 計算量をまず考えると，O(NlogN) の解法を思いつかないといけないことに気づく。logNの計算量を持つ解法としてニブタンぐらいしか知らない（）ので，とりあえ…

問題 D - トランプ挿入ソート 感想 最長増加部分列むずい..... 考え方 どの要素を取り出してもよくて，それからどこに挿入してもよいということなので，取り出さなくてよい数（組）はどのようなものなのかを考えると良い。 要素を取り出して挿入するというこ…

問題 D: サプリメント - AtCoder Beginner Contest 017 | AtCoder 考え方 動的計画法を用いる。 AtCoder Beginner Contest 017 解説 の言葉で言う，「dpで足せる区間」を求める際に自分はlatest[i] = jを使った（i というサプリメントが直近で一番最初に出て…

問題 D - 語呂合わせ 考え方 深さ優先探索でぐるぐる回す。n の数だけクエリがあるが，これを全部足し合わせて一つの文字列 sum_v, sum_w について深さ優先探索をすると楽に解ける。 計算量が気になったが，各語呂合わせの文字の制約で3文字以下に収まるとい…

問題 C - 菱型カウント 感想 やるだけではあると思うのですが，実装が重いのでめんどくさかったです。 こういう問題苦手。自分はプログラミングが向いてないなと実感する問題ですね笑..... 考え (i, j) 点に関して全探索をする。そして，上下左右に Kの幅を…

問題 C - 収集王 感想 飴があるところとないところを分けて考えることが難しかった。この分け方を思いつくまでにかなりの時間を要しました。 難しかったけれどその分解法を思いついた時の嬉しさはひとしおでしたね。 考え まず，(i, j) について二重ループを…

問題 C - 数式の書き換え 感想 フェルマーの小定理と繰り返し二乗法を使った。 とてもためになった問題でした。 昔のC問題むずすぎないか....笑 考え フェルマーの小定理 を利用します。 のときは，求める解は組み合わせを考えて となります（これを としま…

問題 C - たくさんの数式 / Many Formulas 考え 入力を文字列として受け取り，それについてどこに+を入れるか全探索すればACとなる。 例えば"125"を受け取った時， "1" + "25" "12" + "5" "125" ... のように+を挟んでいくが，これは文字列"125"に関して数字…

問題 D - Checker 感想 これがコンテストに出てたら、時間以内に解けなかった気がする。というか、二次元累積和とかいろいろ省略するためにまとめてライブラリ作っておこうかな。 考え まず、x, yの上限から、x, yについて全探索するのは得策ではないと考え…

問題 D - Practical Skill Test 感想 D解けた（小並感） 考え Dの剰余で整理することが大事です。Dの剰余について、各移動をしていき、ans[D]に移動した時に使った値を追加していく。 Accepted Program #include <iostream> #include <string.h> #include <set> #include <vector> #include <map> #</map></vector></set></string.h></iostream>…

問題 Marked Ancestor | Aizu Online Judge 感想 最初は、Disjoint Set（Union-Find木）を使う意味がわからなかった。 単純にクエリごとに親をたどっていきばいいのでは、と思っていました。（愚直解） しかし、愚直解では、根を調べた後にパスを短縮化する…

問題 Disjoint Set: Union Find Tree | Aizu Online Judge 感想と雑多なこと かなり更新遅くなりました... いろいろと重なっていて忙しかったり、AtCoderのD問題が解けなくて記事にできなかったりと、ここ一週間くらい自分の思うように実装できなかったです…

問題 C - Ito Campus 感想 はじめてBPS（幅優先探索）を実装してみた。 割とTLEになる条件が厳しかったので厳格に実装する必要があるんだなあと思いました。 BPSの中で、四方へ進む際に一回一回その方向でいいのか考える必要がない（つまり、その四方へ進む…

問題 1330 -- Nearest Common Ancestors 感想 pojってなんか緊張する。わかる人いませんか笑？ 英語の問題文読むのって英語の勉強にもなるのかな... 考え まずは、子に対して親がどうであるか、map<子, 親>のようにして記録していく。そして次に、求めたい2…

問題 Restrictive Filesystem | Aizu Online Judge 考え 愚直に書くと、map<セクタ番号, 識別子>を作って，逐一更新して行くということになるでしょう。しかし、109までのセクタにアクセスする可能性があるので、これではメモリ不足（MLE）と時間不足（TLE）…