AtCoder Daily Training EASY【灰】2025_0122_2000【C++】
Вставка
- Опубліковано 10 лют 2025
- 鍛錬。
手法が分からないなら
今の自分ならどう解くか、という事を考えながら
C問題の練習をする
デイリークエスト
目標はC問題レベルを今の自分のレベルで考えてみる事
そういえば1文字目と2文字目が同じであった場合を想定していなかった
次回 →
前回 → • AtCoder Daily Training...
AtCoder Daily Training EASY ――――――――――
2025/01/22 20:00start
atcoder.jp/con...
出題された過去問題 ――――――――――――――
ABC 349 C問題 : 2024-04-13 (Difficulty 219)
atcoder.jp/con...
―――――――――――――――――――――――
4:40 開始
6:45 問題を読む
10:35 入力例１を見る
13:55 入力例２を見る
15:45 入力例３を見る
16:05 どう考えていくか、思考する
17:15 用語：部分列を調べる
順番があるか ⇒ ある
間隔は関係あるか ⇒ 検索で見つからず
23:00 考える
複数あったときどう考える？
25:45 ２つの条件を考える
何をしたい？
28:30 大文字小文字の変換
stringsで考えるか、vectorで考えるか
30:10 同じ文字が複数あるとき
文字が同じならどうなる？
31:25 set を考える
32:27 set ソート問題
ソートは無しにしたい。
33:35 何番目に見つかった？
発見した時の関係性を考える
コードを書く ▶ ――――――
36:20 ソートしない unordered_set （検索）
37:55 入力を書く
想定外（逆順で要素が入った）
45:10 大文字 ⇒ 小文字変換（検索）
51:40 判定部分を考える
57:15 要素の順番を配列に格納する
1:02:15 意図通りのデータになっているか確認（修正）
1:04:45 時間終了 ▶ ――――――
判定部分を考える
1:17:25 入力例をすべてチェック ⇒ 提出（WA）
1:2040 間隔が影響するのか？ ▶ ――――――
再考
2:04:30 ギブアップ
貪欲・・・貪欲法ならどう解決できるのか、またあらためてやる
―――――――――――――――――――――――
手法の勉強ですね（解けない）
でもC問題文にも慣れていきたい
少しずつ・・・
――――――――――――――――――
◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆く
――――――――――――――――――
アバター：nizima.com/Ite...
ボイスチェンジャー：www.roland.com...
歌唱曲 ――――――――――――
@otakara_BGM ： • 【フリーBGM / 歌あり】Frozen F...
BGM ―――――――――――――
なぐもりずの音楽室：
/ @nagumorizu
音楽：zippy
/ @zippysound
Neighbor Eight Sound
neighbor-eight...
BGM えんぶらー ――――――――
the path of my life - mini album
bluembler.boot...
Ocean in Call - Embler 3rd album
bluembler.boot...
Eternity Ravine revelated Embler 1st album 完全版
bluembler.boot...
Embler
/ bluembler
つきこ
/ tsubaki_hachi
くーにゃん
/ maplevanilla30
rune
/ 0x0rune0x0
まめらー
/ mamera1129
Miu.
/ sr_miumiu
とーず
/ tomatoze_
乃葵
/ noa14236
Slushy
/ slusluslushy
www.foriio.com...
兎角Arle
arlequin.chiman...
【曲タイトル/エルム凪】 ――――――――
・販売先BOOTHのURL：
【ミニアルバム】心紡ぎ：
erumunagi.boot...
Ents'tr vol.1 /ミニアルバム
erumunagi.boot...
・エルム凪UA-cam： / @erumunagi
いろいろ迷子になったり変な道を爆走したりしていたようなので、アシストっぽい内容をいろいろ。
4:20
素晴らしいとこその1。
自分ができない問題を、きっとできないとわかっていても挑戦するって、意外と難しいんですよね。
一番成長につながることだとわかっていても、どうしても腰が重くなる……。
それをこんなにも当然にこなせるwillowさんの心の持ち方を、私含めみんな見習うべきですね、本当に。
17:15
悩んでたとこその1。
部分列は、「適当にいくつかの文字に印をつけて、それらの文字だけ前から読む」くらいのイメージがわかりやすいでしょうか。
定義で間隔についての言及がないというのは、間隔についてはどんな様子でも構わないということです。
今回の問題をわかりやすく言い換えれば、
「Sの文字列の中で3つの文字に印をつけて、それらを左から順に読んで大文字化することでTに一致するものを作れますか？あるいは（以下略）」
という問題だったわけですね。
部分列の例もいくつか挙げておくと、 “willow” の部分列には “wil” とか “iw” とか “willw” とか “o” とか “ww” があります。
定義上、全部印をつけた “willow” と、印を1つもつけない “” も部分列です。
元々ない文字を含んでいる “wa” や、元々の個数を超えている “www” や、順番を変えないとできない “wlwl” などは部分列ではありません。
n文字の中の部分列を全探索すると、個数の制限がなければ O(2^n)、r文字の部分列に限るなら O(n^r)。
いずれの場合でも単純に全探索すると計算量が爆発しがち。
今回はr=3なので、部分列を全部作ってみるのはO(n^3)になって御陀仏です。
28:30
悩んでたとこその2。
vectorはおそらく使いどころがないです。
少なくとも私は、水色昇格までに一度も使ったことがないです。
vectorでできる処理はおそらく全部stringでもできるので、わざわざ下位互換を使う理由が……。
31:25
やらかしその1。
重複がなくなっちゃうのはダメですね。
同じ文字が2回目や3回目に出てきたところを使う必要があるかもしれないからです。
例えば “willow” に対して “ILL” や “IOW” が空港コードの条件を満たすかどうかは、どちらも正しくはYesですが、重複を消すと誤ってNoとしてしまいます。
今回のWAの大半はこれが原因じゃないかな？
36:20
やらかしその2。
unordered_set はソートしない、の意味を誤解していますね。
ソートしないというのは、順番に関する作業と保証を全て放棄するという意味です。
C++くんの気まぐれ順に並べられると言い換えてもいいと思います。
willowさんの手元のC++くんは完全な逆順にしがちだったようですが、AtCoderの方でも同じ挙動になるかどうかは不明です。
1:53:13
素晴らしいとこその2。
10^5が、1重ループは回せても2重ループは回せないという感覚を持っているのはすばらしいですね。
まだTLEと戦った経験量が少ないうちからその感覚を持てるなら、3完常連もそんなに遠くないかもしれませんね。
今回も、目の前にぶら下がってる超単純な3重ループを最初からスルーしてますけど、灰色でそれできる人はそう多くないと思います。
2:06:00
悩んでた（？）とこその3。
差分の吸収だけが目的なので、大文字に揃えても小文字に揃えてもいいです。
短い分Tを小文字にする方がいいと考えられたのはセンスあり。
たくさんのアドバイスありがとうございます😳！
unordered_set は前に、あまり良くないとコメントであったのは思い出して履いたのですが
使ってみたことはなかったので、このときの自分の要求する動きをするかも？
っと思い使ってみて、思った挙動ではなかったですが、使えそうだな・・・
っとおもったのですが・・・そもそも消してはいけなかった😭
Sについてケースを色々考えてみたのですが
Tのケースの考えが足りなかったです
ぼこぼこにやらかしましたが、良い点のご指摘で少し元気になりました、ありがとうございます！
お疲れ様です！
Tは3文字。T = C1C2C3とする。
C1,C2,C3の小文字をそれぞれc1,c2,c3とする。
(i) C3 == 'X'の場合
c1,c2がこの順でSに含まれているならばtrue
(ii) C3 != 'X'の場合
c1,c2,c3がこの順でSに含まれているならばtrue
文字列Sを先頭から1文字ずつ走査していって、文字c1と合致するか判定する。
合致すれば、照らし合わせる文字をc2にする。
録画を終え、アップロードしている間にタイムスタンプを振り返りながら作り、公開したあとで携帯で再度見て・・・
重複・・・のケースを失念していたっ！！！＼(^o^)／悶絶
T３文字、変数に入れてチェック！！
その思考にたどり着けるよう、この衝撃を次への気付きへの経験値として積み重ねていきたいです😇
おつかれさまでした。序盤でsetの沼に入ってしまったのが敗因でした。
３文字側で、同じ文字を扱う可能性を完全に失念してしまいました😇
おつかれさまです！
そういえばこのチャンネルで貪欲法って登場したことなかったですね。
BFSとか尺取法なんかよりずっと前に習得すべきものな気がしますがｗ
貪欲法の解説、いります？
貪欲法、解説動画で名前をお見かけすることはありましたが
問題として解く問題に登場することはなかったと思います
（もしくはあってもわからないor忘れている）
貪欲法も含めて自分が理解するには、結構動画や画像を使った説明サイトを複数見ないと、自分には難しいので書かれた内容を理解するには予習が必要になるかもしれません。
ABC389で紹介していただいたAOJ（onlinejudge.u-aizu.ac.jp/home）でまず試してみようと思っています！ご提案ありがとうございます！🙇
あ、そうそう。
貪欲法はABCとかで使うタイプとAHCとかで使うタイプがあります。
今回必要なのは前者。
単純にググるとごちゃ混ぜになって出てくるのでお気をつけて。
別の目的の作業ついでに、最近の出題のAからCまでの問題で貪欲法を使うやつを探してきました。
意外といっぱいありました。
ABC379B - Strawberries（難易度39）
willowさん正解済、しかも貪欲法を使う解法をしています。
ABC386B - Calculator（難易度42）
willowさん正解済、ただし貪欲法は使わない解法で答えています。解法が複数あり、解説の解法1が貪欲法を使っています。
ABC363B - Japanese Cursed Doll（難易度32）
willowさん過去挑戦で誤答。わりとシンプルな貪欲法です。
ABC376C - Prepare Another Box （難易度366）
willowさん未解答。解法が2種類あり、片方が貪欲法です。
（貪欲法とは関係ないですが、以前撃沈したABC377Cが、setさんと仲良くなった今なら行けるのではないかと思ったり）
また、AOJの貪欲法のところを解いてみました。
ALDS1_15_A
ABCのB問題レベルです。
willowさんでも雰囲気でコードを書いてAC取るまではできるでしょう（所要時間はさておき）。
ただし、これがその解法でいい理由まで説明できて初めて合格とするならわりと大変です。
問題文の「25セント」を「26セント」に変更するだけで急に激ムズ問題になる、と聞いて「そりゃそうだよ」と思えたら、貪欲法を理解できていると判断していいと思います。
ALDS1_15_B
ABCのB問題レベルです。
こっちはしっかり貪欲法を理解していないと難しいでしょう。
でも貪欲法でうまくいく理由を考えるのはAより簡単。
若干数学的（というか算数的）要素あり。
ALDS1_15_C
ABCのD問題レベルです。
問題の意味するところはわかりやすいので、お絵描きはしやすいと思います。
ただ、実装が簡単かは……？
貪欲法だというヒントをもらってスタートならABCのB問題かC問題レベルかも。
ALDS1_15_D
ABCのE問題レベルです……たぶん。（このレベルになると自信なし）
数学的ないろいろがわからないとまず問題が意味不明じゃないかと思います。