drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ アナグラム nC2 数え上げ問題 解空間:O(N^2)個のペア 解空間:O(N^2)通りの選択肢 AtCoder AtCoder300点 茶色diff ABC-C NoviSteps4Q setやmap:検索や削除が速いこと 計算量改善：setやmapの活用 連想配列(setやmap) 集計処理 ソート:標準形を用いて考察する 単純化：標準形を考える そのまま覚えたい典型問題 考察：操作・条件・目的関数を言い換える 鹿本の例題 すごく面白い問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。 制約 考えたこと まずは、問題の条件をわかりやすく言い換えることを考えよう。つまり、「2 つの文字列 が互いにアナグラムである」という条件は複雑なので、これをわかりやすく言い換えたいのだ。 互いにアナグラムかどうかを判定する簡単な方法として、 をアルファベット順にソートして、一致するかどうかを調べる というものがある。これに気づきさえすれば、あとは簡単だ。与えられた各文字列 について、それぞれソー… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2024%2F11%2F23%2F133149" title="AtCoder ABC 137 C - Green Bin (4Q, 茶色, 300 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1730992592391452 Hatena Blog https://hatena.blog 2024-11-23 13:31:49 rich https://drken1215.hatenablog.com/entry/2024/11/23/133149 1.0 100%