※注意
自分（雑魚）のメモなので解説は恐ろしく雑です。ご了承ください
Members
1
Posts
20
Active Today
0
Created
3 yr. ago
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me B - Many Oranges（AtCoder Beginner Contest 195）
- 問題URL
https://atcoder.jp/contests/abc195/tasks/abc195_b - 問題メモ
A(最小の重さ) B(最大の重さ) W(合計の重さ) - 重さがキログラム単位だと扱いにくいのでグラム単位に変換（1000を掛ける）
- みかんの数を全部探索する。
重さにあったオレンジの数が用意できる条件は
A * (みかんの数) <= W <= B * (みかんの数)
である。よってこの条件のときの数の時に最大数と最小数を更新すれば良い。 一回も更新されてなかったらどの数でも用意できなかったということになるのでUNSATISFIABLEを出力 - ソース https://github.com/mofrun/Competitive-programming/blob/main/AtCoder/ABC195/B%20-%20Many%20Oranges.cpp
- 余談
題名がオレンジなのに日本語問題文はみかんにするのね
- 問題URL
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me 10→2進数変換
undefined
N = 17 #10001 ans = "" while N > 0: ans = ans + str(N % 2) N //= 2 ans = ans[::-1] print(ans) # 10001と出力 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me E - Get Everything（AtCoder Beginner Contest 142）
atcoder.jp E - Get EverythingAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
基本的にナップサックDPだが宝箱の状態をbitで管理する
dp[i][j] iは鍵番号、jはbitが立ってる番号が宝箱開封済とする解答例（C++） https://atcoder.jp/contests/abc142/submissions/27600466
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me B - ATCoder(AtCoder Beginner Contest 122)
atcoder.jp B - ATCoderAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
文字列が短いので左端と右端をすべて探索しても間に合う（解答例1)
左から数えて一番大きいACGT文字列を出力するほうが計算量少ない（解答例2）
解答例1だと1000文字以上から間に合うか怪しそう。今回は関係ないが。計算量は文字列をNとして、解答例1がO(N^2)で解答例2がO(N)
解答例1(C++)
https://atcoder.jp/contests/abc122/submissions/27599924
解答例2(C++)
https://atcoder.jp/contests/abc122/submissions/27599955 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me B - Play Snuke(AtCoder Beginner Contest 193)
atcoder.jp B - Play SnukeAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
X - A <= 0の場合は売り切れ、売り切れでない場合は最小価格になるか判定すればよい。
答えの変数が初期値のままの場合はどの店でも買えなかったということなので-1を出力。初期値以外の場合はそのまま答えの変数を出力すれば良い。
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me B - Find Symmetries（AtCoder Grand Contest 023）
atcoder.jp B - Find SymmetriesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
愚直にやると縦の座標×横の座標×A×Bで計算量は300×300×300×300>10^9にはなりそうなので間に合わない。
座標の全探索はどうにもならなそうなのでA×Bを改善したい。 実はAだけ加えたものが良い盤面であればBはいくつでも良い盤面である。 よってA方面だけ探索して良い盤面一つにつきN個良い盤面として答えの変数に加えれば良い
解答例(C++)
https://atcoder.jp/contests/agc023/submissions/27597329 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me A - STring(AtCoder Grand Contest 005)
atcoder.jp A - STringAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
特定の連続する文字列を消す問題
今回のように短い文字列を消す場合は典型的な方法がある。
空の文字列の後ろに入力した文字列を左から追加していく。追加毎に後ろの文字が消す文字になっているか確認する。(今回の場合は後ろ二文字を確認すれば良い。)消す文字だった場合は消す文字の数を後ろから消せば良い。
解答例(C++)
https://atcoder.jp/contests/agc005/submissions/27596768ちなみに公式解説ではstackを使った方法を紹介しているが、3文字以上になった場合は煩雑になるのでC++で短い文字列を消すなら解答例の方が汎用的で良いかなと思ってます。
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me C - Reorder Cards(AtCoder Beginner Contest 213)
atcoder.jp C - Reorder CardsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
座標圧縮するだけとしか言いようがないw
座標圧縮はこのようなソートと二分探索をつかう方法と解答例のようなstd::setとstd::mapを使う方法がある。(他にもあるのかな？)
解答例(C++)
https://atcoder.jp/contests/abc213/submissions/27596747 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me A - 和風いろはちゃんイージー（AtCoder Beginner Contest 042）
atcoder.jp A - Iroha and Haiku (ABC Edition)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
「5が2つだけあること」「7が1つだけあること」の両方の条件がそろっていたらYESである。
条件の判定は色々あるが、数列でカウントして判定した。（下記リンク参照）
解答例（C++）
https://atcoder.jp/contests/abc042/submissions/27596651 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me A - ABC Preparation（AtCoder Beginner Contest 185）
atcoder.jp A - ABC PreparationAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
コンテスト毎に必ずすべての問題を一つずつ使うので、一番少ない問題の数しかコンテストを開けない。 よって一番少ないAを出力すれば良い。
解答例（C++） https://atcoder.jp/contests/abc185/submissions/27596643
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me B - Grid Compression(AtCoder Beginner Contest 107)
atcoder.jp B - Grid CompressionAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
#のY座標とX座標をそれぞれ座標圧縮する
その際に解答の高さと幅もわかるので解答用のリストを作る#の座標を圧縮した座標に#を解答用リストに入力後に出力すればよい
解答例(C++)
https://atcoder.jp/contests/abc107/submissions/27575249 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me C - Tax Increase(AtCoder Beginner Contest 158)
atcoder.jp C - Tax IncreaseAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
学校の数学のように解くことも可能だが、これは競技プログラミングなのでコンピューターの計算力を頼ってみる。
該当する数字をXとする。Xの数字を総当りしたい。どこまで総当りすればいいかが知りたい。
Aだけで考えるとA <= 100なのでX<= 1000まで総当りすればよさそう。Bだともう少し増えそうだが1100よりは小さそう。 正直10000にしても計算は間に合うので適当に100000まで総当りする。判定については切り捨てや誤差が気になるのでx * 8 / 100のように先に掛け算して数字をふくらませると防止できる。
解答例（C++） https://atcoder.jp/contests/abc158/submissions/27573156
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me A - Multiplication 1（AtCoder Beginner Contest 169）
atcoder.jp A - Multiplication 1AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
- 変数を宣言
- 変数に入力
- かけた数値を出力
正直やるだけ問題。競プロ初心者にはよいかもしれない。
なれない言語の出力、入力の練習にも使えそう。解答例(C++)
https://atcoder.jp/contests/abc169/submissions/27570280解答例 (Python)
https://atcoder.jp/contests/abc169/submissions/27571148解答例(Ruby)
https://atcoder.jp/contests/abc169/submissions/27571405 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me E - Graph Destruction(AtCoder Beginner Contest 229)
atcoder.jp E - Graph DestructionAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
サンプル1(出力例1の下にある)図を右からやっていく形
連結成分を数えるint cnt = 0;と
解答用の配列vectorintans;
を用意しておいて- 一番右は頂点無しなのでansに0を挿入
- 次は頂点6が一個加わるのでcntに1を足しansにcntを挿入
- 頂点5以降だが、まず頂点が一つふえるのでとりあえずcntに1つ足す。現在の頂点より大きい頂点と今まで連結しておらず新規に連結するようだったら連結成分が減るのでcntから1引く。 その後ansにcntを挿入する
連結してるかどうかの判定はUnionFindを使えばよい。
ansは順番が逆になっているので、C++であればreverseで順番を戻して出力
解答例（C++)
https://atcoder.jp/contests/abc229/submissions/27568298 -
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me D - Longest X(AtCoder Beginner Contest 229)
atcoder.jp D - Longest XAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
愚直にやるなら左端と右端を決めて探索していけばよいが…
文字列の長さをN（最大2 * 10^5）として愚直に探索する擬似コードを書くと
for left = 0 ; left < N; left++
for right = 0; right < N; right++となるがこれは計算量が最大でN * N(4 * 1010)となり実行時間制限: 2 sec内で探索はできない。(大抵は108以下でないと間に合わない)
よって工夫する必要がある。rightのループ文を高速化できればN *(高速化したやつ)にできるぽい
やり方としてパっと浮かぶのは累積和としゃくとり法を使う方法。もう一つは Twitterで教えてもらった累積和と二分探索法。これらの説明は難しいのでソースで。
解答例（C++、愚直に探索、計算量が多すぎてTLE(制限時間オーバーによる誤答)になってます ） https://atcoder.jp/contests/abc229/submissions/27567341
解答例（C++、累積和、しゃくとり法） https://atcoder.jp/contests/abc229/submissions/27565090
解答例（C++、累積和、二分探索） https://atcoder.jp/contests/abc229/submissions/27565460
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me C - Cheese(AtCoder Beginner Contest 229)
atcoder.jp C - CheeseAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
美味しさが大きいほうから選んでいけば良い
実装的にはvector<pair<long long, long long>>に入力して大きい順にソートすれば良い。
あとは数え上げるだけ。（解答例みてください）
解答例（C++） https://atcoder.jp/contests/abc229/submissions/27564478
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me B - Hard Calculation(AtCoder Beginner Contest 229)
atcoder.jp B - Hard CalculationAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
1の桁から足し合わせて調べていく
手順としては
- 一番下の桁は10で割ったあまりなのでA%10 + B%10を求める
- 1で求めた数字が10以上であれば繰り上がりがあるのでHard出力
- 上の桁を求めたいので1番下の桁を消す。10で割れば消すことができる
これをすべての桁を調べるまで繰り返す
-
まくるの競技プログラミングメモ @lm.korako.me macle @lm.korako.me A - First Grid (AtCoder Beginner Contest 229)
atcoder.jp A - First GridAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
