全探索

はじめに... こんにちは～ この記事は初心者向けのものとなっております あの有名な精選100を分野別に解いていきます 今回は全探索：全列挙の4問です 1 ITP1_7_B - How Many Ways? 問題サイトはこちらです！ 問題文↓ 1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。 ループするものの制約が3≦n≦100かつ、数字の重複がない場合なので、普通に全探索すればいいですね こちらが作成したコードです！ #include <bits/stdc++.h> using namespace std; …

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) 問題の性質 まずは問題の性質から探る． 同じ種類の寿司なら，美味しさが高い物から食べるのが最善． 同じ種類を食べるときは，最初の 1個だけは種類ボーナスに影響するが， 2個目以降は影響しない． 簡単な問題 種類ボーナスは無視すると， 全ての寿司をまとめて，おいしい順に並べて選べばよい． 今回の問題 種類ボーナスも考慮すると， 種類毎に類別しておきたい． また，同じ種類であっても，最初の 1個と残りは区別する必要がある． そこで，美味しさと種類ボーナスが増えるか = \(\ (d, k) \), \(k \in …

ABC315D あまり綺麗な解法がない．全探索によるシュミレーションを高速化する問題． 基本は， 何を全探索するか． 升目の全探索は，削除の処理を考えると TLE である． たとえば，aaaaabccccbdeeebdfghのような形が最悪ケース． 対策：色が 26種類と少ないことを利用して， 色を全探索する方針． それを行と列に分けて，それぞれ行うが， まずは簡単のため，行と列の一方だけ考えるとよい． 注意 行を消したとき，対応する色の個数も減らす． もう一つの注意は，行と列を同時に消すということ． 別々に消すと WA. 例えば，Input 2 の様にaaaaaabcdeの形が反例．行を先に…

atcoder.jp・参考 AtCoder ABC 161 D - Lunlun Number (緑色, 400 点) - けんちょんの競プロ精進記録 ・説明 参考記事のように、再帰関数で実装した。最大10桁までのルンルン数を求めてallにルンルン数を入れていく。あとはソートしてK番目を出力する。 また、再帰関数の次のルンルン数を求める部分は for val in range(1,10): for j in range(-1,2): add=(val%10)+j print(val,j,add,val*10+add) #val*10+addがvalの1桁上のルンルン数になる。 #out 1 -…

ABC305C 角が欠けているときだけ注意．もとの長方形の大きさが，1辺が2以上であることにも注意すると， もとの長方形の辺にあたる部分が特定できる． 言い換えると， 一番小さい行， 一番大きい行， 一番小さい列， 一番大きい列 の番号が手に入る． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll h,w; cin >> h >> w; vector<string> s(h); cinv(s); ll a,b,c,d; a = b = INFL; c = d = -INF…

ABC195B 実数は全探索できないので，整数部分を全探索する． \(x\)個で可能であるかを判定して， \(x\) を全探索する． \(x\) 個で可能であることは， \(xA \leq W \leq xB\) であることと同値． あとは \(x\) の範囲に注意． \(W\) はグラムに変換するために \(1000\) 倍しておく． \(x\) の最大は， \(A = 1\)のとき \(1000\times 1000\)． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

ABC292C 何を全探索するか，探索する範囲を小さくすること， 前計算すること． 基本通りにやればAC． まず \(a,b,c,d\) のどれかを \(N\) の範囲で全探索する． 次に \(b\)は \(N/a\) 程度なので， \(a,b\) で \(O(Nlog N)\) 程度． あとは， \(c,d\)を高速に数えたい． \(cd = N - ab\) であるから， 約数を求める問題に近い． \(M\) の約数を求めるときは，\(M^{1/2}\) まで求めれば良かった． それと同様にして， \(M \leq N\) に対して \(cd = M\) となる個数を 前計算すれば \(O…

この記事は、 素数大富豪 Advent Calendar 2024 - Adventar 3日目の記事です。 昨日の記事はこちら↓ prm9973.hatenablog.com 2022年からシリーズ作となっている素数音楽の記事。 素数音楽とは何か、というところは過去の記事に記載しています。 prm9973.hatenablog.com prm9973.hatenablog.com 素数音楽を量産するようになって久しいですが、素数大富豪で多くの枚数を一気に出す機会も増えていますので、案外役に立ってます。カマトト後の24枚なら、結構高確率で音楽素数が出せるようになってきました。 あとはマスプライ…

KCPCの山田です。なんと参加記担当回に入青しました。 ABC382 A問題 B問題 C問題 D問題 E問題 F問題 実質全完 コンテスト結果 ABC382 今回のABC382は別名 ☨AtCoder プログラミングコンテスト2024☨ で、自分をスポンサーする特殊な回ということで話題になっていました。 山田のコンテスト前のレーティングは1561でした。1901以上のパフォーマンスを獲れば入青です。 ところが最近はABCの調子が悪く、一ヵ月以内のABCでの勝ちは０回でした。いつもの二分探索、いつものbitDPがコンテスト中に思いつけなくなっていました。 そういうこともあり今週で入青する可能性は…

11/25(月) 午後3時半起床。インターン先定例会に出席した。 研究における特大のイベントは先週で一段落したはず、ということで今週から稼働を再開したい。とりあえずタスクの確認のために1on1をお願いした。ただ、来週一週間はYandex Cupに参加しているのだが……。勉強会はCursorというAIと連携したエディタの紹介だった。自分はそもそもAIをほとんど使わないので、まともなコードが生成されていくのを見るだけでびっくり仰天してしまう。 午後9時半まで先週の週記を書いて、投稿し、TROC #41に出た。もともと日曜日午後6時からの予定だったが、CFの5hと被ったのでずらしたらしい。この5hは…

チーム zoozer で出ていました！ [crypto] reiwa_rot13 問題 解法 [crypto] dual_summon 問題について 最初に H2を求める Tagの衝突 PoCコード [crypto] reiwa_rot13 問題 以下のような感じで計算されたn,e,c1,c2が与えられるので、keyを頑張って特定する問題。（本当はこの後にAES暗号化処理が書いてあるのだが、keyを特定する所が本質なので割愛） p = getStrongPrime(512) q = getStrongPrime(512) n = p*q e = 137 key = ''.join(random…

atcoder.jp コンテスト時間: 2024-11-30(土) 21:00 ~ 2024-11-30(土) 22:40 (100分) A - Daily Cookie Difficulty: 10 解答時間: 1:50 横一列に並んだ 個の箱のいくつかの箱にクッキーが入っており、その状態は文字列 によって与えられる (@ならば、左から 番目の箱にクッキーが1枚入っている) 。これから 日間、箱のいずれかに入ったクッキーを1枚選んで食べることを1日1回行う。 日間経過後、空き箱であるものの個数を求めよ。 内の@の数を とすれば、 が答え。 B - Daily Cookie 2 Difficu…

クリアしてやりましたよ。ゾーマ倒すところまで。 www.dragonquest.jpやってみた感想ですが、「案外かなり楽しめた」です。 始めこそ現代のゲームからすると異常に高いエンカウント率や金欠に悩まされ続けましたが、思考を転換して「これは街もダンジョンも隅から隅まで探索を楽しむゲームなんだ」と気づいてからはかなり楽しめるゲームになりました。ダンジョンも街も入ってすぐに完全なマップが出てきたり、おもいでシステムで会話を覚えられるシステムも、現代的なサポートが入っていてプレイ感は悪くなかったですね。（もちろん現代のゲームからするとダメなところ多いと思いますが）また、ダーマ神殿入って転職が解禁さ…

11/18(月) 午後3時過ぎ起床。 JOI一次予選の第3回が公開されていた。そこそこタイミング良く発見したらしく、FAではなかったものの0msでのFastestは4問とも獲得できた。コードゴルフも行ったが、数日後に確認したらB以外すべて縮められていた。どれも書き方だけの問題でなく、そもそも短く書けるアルゴリズムを思いつけていなかった。 JOI 2024/2025 一次予選 (第3回) 過去問 - AtCoder 午後3時半からインターン先定例会。先週伝えたように稼働はしていない。論文は無事書けて、今週金曜日の学内での発表も何とかなりそうだと報告した。勉強会はヘッドマウントディスプレイの紹介。…

この論考（って呼んでもいいですか？！？！？！💢💢💢）は、思考原理とかあのあれあれです一般的？っていうんですか？あ！一般的な論理学を！前提としています！でも！それについての気持ちも書！（←ここで小ジャンプ）かせていただいております！ アンクラーーーーーーーージュ！！！！！ 了解！！！！！ ・「AはXである」≠「AのみXである」 ・「Aという思い」「Aという気持ち」「Aと考える」などは、「A」と主張しているわけではなく、例えば「Aという思い」自体を主張しています！！！！！心のバージョン10ってな～んだ？こころてん（夏祭り）（「分からない」「自信」などの語を含め、主観にとって自由なものを指しています…

ABC379E 考えた事 素直に考えれば，累積和を使えば解ける． 今回は，その方法だと桁が大きくなるのが問題で，足し算にO(1)でなくO(N)程度かかる． 何を全探索するか考えると，10 の指数 \(k \in N\) になる． 繰り上がりを無視すれば，答えは \(N\) 桁の自然数で書ける． 答えの \(k \in N\) 桁目の値は 累積和で求まる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; string s; cin >> s; r…

AtCoderの過去問対策です。ABCで解けなかった問題、ためになった問題のコードを備忘録として残します。 問題 解説 考え方 解答例1 解答例2 メモ デモ1 デモ2 問題 B - Sum of Three Integers 解説 https://img.atcoder.jp/abc051/editorial.pdf 考え方 各変数を 0 から K まで回す 3 重ループだと、時間計算量は O(K3) となる。ただし、K の上限は 2500 であるため、このままでは間に合わない。 2,5003 = 15625000000(約156億) X + Y + Z = S の式を Z = の式に変形す…

ランニング 週一で整形外科に通って薬も飲んで、少し脚の状況良くはなった。 悪いときは15分でやばくなって走れなくなっていたのが、7.5分/kmペースではあるけど6kmくらいなら走れるように。 ただ参加予定だったえちごくびきのウルトラマラソンはさすがに無理そうで泣く泣くキャンセルした。2年に1度の大会なのに残念…。 競プロ 長期のAHC038は素直に全探索からのビームサーチを書いて15位。 トップもそんなに方針に違いは無さそうだけど1割くらい差が付いている。ビーム系の細かい工夫で差を付けられること多いなあ Rustで初めてビームサーチを書けたのは良かった。 それとARCのJapan Open予選…