競プロ
問題 AtCoder Beginner Contest 218 - D 考えたこと (x, y) の座標を与えられるのでその中から 4 つ選択して x 軸、y 軸の両方と並行な長方形を作成する。 入力例を見る限り正方形でもいいっぽい。 最初は次のようなロジックで検討。 座標を 1 つ取得する。 …
問題 AtCoder Beginner Contest 219 - D 考えたこと 全探索は無理。弁当を食べる場合、食べない場合の 2 択で考えると最大で の計算量になってしまう。 ナップザック問題の応用で行けそう、までは思いつく。 DP[選択した荷物の数][たこ焼きの数][たい焼きの…
問題 AtCoder Beginner Contest 152 - D 考えたこと n が オーダなので, n * n のオーダにならなければ良さそう (1, 1) -> (1, 11) -> (1, 101)... と推移していって, xの種類 * yの種類を計算すれば良い (101, 101) の場合, 101, 111, 121...191 の10種類な…
問題 AtCoder Beginner Contest 146 - D 考えたこと 絵を書いてみる 最大の色の数は最も枝の多い頂点の数になる 色をどうやって分けるかが大きな課題 最初は各頂点に k 種類の set をもたせて 1個ずつ pop させていくか？と思ったけど, TLE しそうだし, 実際…
問題 AtCoder Beginner Contest 151- D 考えたこと オーダの制約が 20 * 20 = 4,000 = これなら 以内に収まるので全パターンで幅優先探索でOK と思っていたらどうしてもTLEが取れない！なんで！？となりました
問題 AtCoder Regular Contest 030 - A 考えたこと 問題の意味がわからなかったため解けなかった 連結成分 の意味を調べて理解できたので, きちんと備忘録として記録する 連結成分 = 1つの独立したグラフ の こと 今回の問題の場合, ノードが1つしか無いグラ…
問題 AtCoder Beginner Contest 135 - A 考えたこと 一瞬考えてしまったため備忘録として残すこととする a, b の2つの数字が与えられて, |a - k| = |b - k| となる k が存在なら表示する 絶対値なので2つの数字からの距離が等しくなる場所を探せば良い つま…
問題 AtCoder Beginner Contest 128 - C 考えたこと 問題文が異常に難解なのと入力パターンも難解 とりあえず全てのスイッチのパターン試す必要がありそう 制約が小さいため bit全探索 が頭をよぎる 途中で 配列同士のand演算を使いたかったので numpy も使…
問題 AtCoder Beginner Contest 127 - D 考えたこと 少ない数値を大きい数値に変換し続ければ良い カードをソートして, 入力値を二分探索, その中で小さい方から更新していけば良さそう？ 制約も だし行けそうな気がする 先にオチを言うと TLE でした
問題 AtCoder Beginner Contest 132 - D 考えたこと 組み合わせ系の問題 i = 1 を考えると 青いボールが連続して並んでいる場合だけ. 例えば赤いボールと青いボールがそれぞれ3個ずつあった場合には, 赤いボールの隙間に青いボール全部を入れることになるの…
問題 AtCoder Beginner Contest 129- D 考えたこと なので 意外と愚直でいけるかも 壁の位置を記録しておいて, 明かりをおく点で二分探索すると壁と壁の間の数がわかる 縦と横、両方やれば 縦 + 横 - 1 がその点の明かりの強さとなる 一度見た明かりと同じ列…
問題 AtCoder Beginner Contest 140- D 考えたこと 最初は左端から入れ替える、入れ替えないみたいな操作をすることを考えた 手計算でも計算量が多くなりすぎるので無理と判断 何かしらのロジックで一気に解けそうとは思ったがそれ以上進まず 残念ながらわか…
問題 AtCoder Beginner Contest 128 - B 考えたこと 配列を他要素でソートすることができるか python の 場合、以下のコードで可能
セグメント木 競プロer御用達のデータ構造の1つ 配列の範囲に対して値を代入したり, 範囲内の合計値や最大値/最小値等を 高速に 取得するためのデータ構造 AtCoder Beginner Contest 185 にてセグ木の問題が出題された 悔しいのでRustで実装することとした
概要 くじかつ で AtCoder Beginner Contest 147 D を解いたのでメモ
概要 くじかつ で AtCoder Beginner Contest 047 D を解いたのでメモ 実験的に わざと rust でNlog(N) のループを書いたけど TLE でした プログラミング言語が速いからといって計算量は甘えさせてくれないという良い教訓になりました
はじめに AtCoder Regular Contest 109 に参加 大会中にはACできなかったが C 問題 について無事 AC したためメモする
Union-Find Tree 競プロer御用達のデータ構造の1つ データとデータをグループ化したりする 同グループ内に何個のデータがあるか数え上げたりする グループがいくつあるか数え上げたりもできる
