AtCoder緑色になりました
はじめに
2020/05/31のABC169(https://atcoder.jp/contests/abc169)で緑色になりました。まあまあ長かった……かな？
新しくできるようになった/持ったもの
- DFS(BFS)
- 各種小物ライブラリ
- UF木
- Bit全探索
- 尺取り
- にぶたん
- 組み合わせ(パスカルの三角形をDPするやつとか、逆元取るやつとか前処理するやつとか……)
- WF法
- それっぽいライブラリをggって貼る
こう見ると結構多いですね……講座でシバかれただけはあります(その節はありがとうございました)
まあ実際実戦投入したものはこの中でもわずかなので、それよりはちゃんと頭が使えるほうが大事なのかな、と思います。
緑になるために必要そうなこと
- 茶Diffを逃さず通す
- あわよくば緑、水色も狙う
- 本番は頭がデバフされるので、精進で考察系の問題に出会ったらじっくり考える
多分茶色になるためにもこれを-1色したものが重要になってくると思います。ほんとかな。
やんなきゃいけないな〜って思ってること
- グラフのお勉強
- セグ木をお迎え(できれば抽象化したい)
- DPのお勉強
精進状況
サボりにサボっています。ごめんなさい。
ぼちぼちこんな感じです。水色になったら(なれるの？？)また色変記事を書くと思います。そのときはよろしくお願いします。
ABC162-D RGB Triplets
コンテスト終了後にACできて虚無になった記念。次こそは……！
ACコード:
Submission #11861378 - AtCoder Beginner Contest 162
考えたこと:
・N<=4000
O(N^2)が限界だから添え字を一つ消したい→二つ目の条件をうまく使いたい→なんか書こうとする(10分)
・≠が条件なのでうまく使えない
数え上げるよりも条件を否定して包除した方がよさそうだ(10分)
・条件の把握
一つ目の条件の否定は「s[i]==s[j]||s[i]==s[k]||s[j]==s[k]」…①で、二つ目の条件の否定は「j-i=k-j」…②だな！(3分)
・実験
①かつ②の数え上げは簡単だけど、①、②は……？
②はまだわかりそうだから実験してみよう！→わかった！端っことの位置関係か(5分)
①が難しい。。。ここにも包除を使って……言い換えは出来たけど難しいなあ……ほんとにできるのか？(5分)→式が立たない！！！！(20分)→わかった！！！実装！！！(罠)(20分)
・バグる
コンテスト終了→なえる→いろいろ質問してみる
ここで頭が冷えて考察用紙を見直す。①を日本語で言い換えると「(s[i],s[j],s[k])に対して、少なくとも二つが同じ文字になる(i,j,k)の場合の数」だった。(15分)①の立式が嘘だったことが分かった。ぴえん。
・直してサンプル投げてもまたバグる
コードを見直したらk>nのときの処理が抜けてた→直してAC。
今日の学び:ちゃんと落ち着いて考えよう。特によくわかんないときは文字や言葉にして何をしようとしているかはっきりさせよう。
AtCoder茶色になりました
はじめに
タイトルの通り、20/03/08に開催された日立コン2020(Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 - AtCoder)で茶色になりました。わぁい。
やったこと
まずAPG4bの一章を終わらせて、ABC143に出ました。このころは本当に右も左もわからぬ状態で3完しただけです。Perfは218でした。
APG4bの二章が終わった頃にABC144がありましたから、これにも参加しました。Perfは468でした。
このころから過去問を提出し始めて、虚無でもなんでもいいから1日1ACする生活を一月弱続けました。昨年12月には受験の関係もあり、完全にAtcoderから離れていました。
2月には受験が終わりましたので復活して、過去問の提出を再開しました。提出した問題は専ら灰Difのみでした。(ほかは解けないので)
その他には、これ厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】 - Qiitaとか、これレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiitaを読みました。おすすめ問題は一切解いてません。
できるようになったこと
- 累積和
- nCk(mod p)を求めるライブラリを探す
- ちょー簡単なDP
おしまい。
これは本当です。逆(対偶？)に言ってしまえば、茶色になるのに高尚なアルゴリズムやデータ構造はいらなくて、for文が書けてちょっと頭が使えればそれでいいのです。「〇〇わかんないよ〜〜」などと泣く必要はありません。
できるようになりたいこと
- にぶたん
- DFSBFS
- Bit全探索
- よくわかんないDP
ほかにもいっぱいあります。これからいろんな色になりたいので。
茶色になるために必要だったもの
- ペンと紙
考察をするときに大変重宝しました。サンプルの意味がわからないときや、自分の考えを言語化したいときにかなり役立ちます。
- 考察をする力
名前ほど大層なものではなくて、要はnやaが小さい場合ならどうなるかな〜と実験してみることです。問題解決の糸口になっていることが多いですからね。解説が見たくなってもそこはぐっと我慢してあと5分考えてみるのもいいと思います。
- APG4b二章くらいまでのプログラミング知識
私はC++なので他の言語についてはよくわからないですが、まあどの言語もこれくらいは必要だと思います……
- 実装で詰まったときにググる力
私は「コンテスト中にググるなど言語道断！！！！」などと勝手に思っていたので、ググれば解決する問題に無限時間かけてパフォーマンスを溶かしてしまったことがありました。自分のやりたいことが実現できるコードが基本的に存在して、それを知らないだけというケースが大変多いですから、無理せず調べて吸収していきましょう。
- (ちょっとの早解き能力)
これは別に重要ではなくて、茶になるまでが早くなりますよ、というやつです。灰Difを60分くらいで全部通せば茶Perfくらいは出ますから、そんなに気にする必要はありません。
しばらくの目標
- 茶Difの問題を通せるようになる
実際はそのために必要なアルゴリズムとデータ構造を学ぶというところでしょうか。「〇〇を知っていますか？」をされて最近無限につらいです。
- コンテストで緑Perfを出す
今回はまぐれだったので、実力で取りたいところです。
この記事はこれでおしまいです。ありがとうございました。これからもがんばります。
ABC154-D Dice in Line
初めて茶Diffを解いた記念。
提出コード:
https://atcoder.jp/contests/abc154/submissions/10555998
考えたこと
- 問題文、制約を読む(3分)
期待値か、とりあえず定義に従って期待値を返す関数を作ろう！→関数を実装(2分)
NとKがまあまあ大きいから、愚直に二重ループじゃ駄目そうだなあ……どうしよう(3分うなる)
- 自分の関数を眺める(2分)
期待値は(1+p)/2→期待値には加法性があるから、結局部分数列の和の最大化問題だ！
どうやったらいいだろう……そういえば累積和を使えばできそうだなあ……？
- 累積和を書く(10分弱)
まあこんな感じでいいかな？数列の和の最大を求めてからkを足して2で割ることに注意して……Submit！
- バグる(10分)
サンプル通ったからまあまあ合ってると思うんだけど……→出力部分をよく読むと「誤差10^-6までならOK」って書いてある→ってことは小数点以下の桁数が足りてないのかな→直してSubmit！→AC！
大雑把に逆元を理解したい
筆者はおつむが残念なので、厳密性に欠けた部分があるかもしれません。また、高校数学までを理解していれば多分読めます。
競プロの実装については一切記載していません！
- 単位元とは
ざっくりいうと、その演算を右からしても左からしても元の値を変化させないようなものをいいます。
加法の単位元は0です。例えば5+0=0+5=5なので。
乗法の単位元は1です。例えば5*1=1*5=5なので。
- 逆元とは
ざっくりいうと、ある数xに対してある演算を行ったとき、右から演算しても左から演算してもその結果が単位元となるものをいいます。
xに対して…
加法の逆元は-xです。
乗法の逆元は、x^-1です。x=0のときは定義されません[要出典]。
- 逆元を求めてみたい
法は素数とします。だいたい10^9+7ですし。知らんけど。また、aとpは互いに素とします。互いに素じゃなかったら困るので。
さて、先程述べたことを思い出すと、除法は乗法の逆元をかけているとみなすことができます。
つまりmod p上での除法は、もとの数に逆元をかけてあげればいいことになります。
ですから、私達のしたいことは整数aに対して
ax≡1(mod p)…①
なるxを求めてあげることです。このxがaの逆元となります。
ところで、不定方程式
ax+py=1…②
を考えてみましょう。不定方程式にmodをとって解いた経験はお有りでしょう。この不定方程式にmod pを取れば①に一致します。
なので、②を満たす(x,y)を求めてあげれば、xはaの逆元となります。
特殊解を(x',y')とすれば、媒介変数k(∈Z)を用いて
x=pt+x',y=-at+y'となりますから、結局特殊解を求めるだけで用は済みます。aとpが互いに素であるとき、この方程式は無数に解があることが知られています(あとで証明します)から、必ず逆元が存在することがわかります。
- ax+py=1型の方程式には、aとpが互いに素なときには解が無数に存在する証明
(i):まず、「a,2a,3a,……,(p-1)aをpで割ったあまりはすべて相異なる」を示します。あまりが同じになる組があるとすれば、これをkaとla(1≦k<l≦n-1)とおきますが、2つの数の差はpで割り切れることになります。つまり、
(k-l)a≡0(mod p)…③
となりますが、aとpは互いに素であるため、③が成り立つには、k-l≡0でなくてはいけません。kとlの範囲を考えてあげると、このような(k,l)は存在しません。したがって背理法によって(i)が示されました。
(ii):次に、(i)で扱った{a,2a,3a,……,(p-1)a}の集合を考えます。
(i)で示したことから、この集合の要素をpで割った余りには、1からp-1までの(p-1)種類の数がそれぞれ一回だけ登場するはずです。ですからpで割ったあまりが1になるような数が(i)で考えた集合の中に存在します。うまいこと(s,t)を選べば、
sa=tp+1
とできます。
これを移項して式を見比べることによって、ax+py=1には、(x,y)=(s,-t)という特殊解が存在することがわかりました。
また、「a,2a,3a,……,(p-1)aをpで割ったあまりはすべて相異なる」ことと、「a,2a,3a,……,(p-1)aをpで割ったあまりには1からp-1までの(p-1)種類の数がそれぞれ一回だけ登場する」ことを考えると、mod pの世界では、
{a,2a,3a,……,(p-1)a}の集合と、{1,2,3,……,p-1}の集合は合同であることがわかります。
要素を全部掛け合わせてしまえば、
(p-1)!a^(p-1)≡(p-1)!
ですから、(p-1)!で両辺割れば
a^(p-1)≡1
となります。これをフェルマーの小定理といいます。
これを、
a*a^(p-2)≡1と変形して、
ax≡1と見比べたら、
a^(p-2)が逆元であることがわかりました。嬉しい！
DaでTrueを見てみよう(シャニマス)
ざっくり要点だけ。雑誌と手帳持ち込み推奨。
①手札を揃える。
スタートライン。サンセットとメロビを4凸します。最低限の投資だと思って頑張ってください。
次、あと3人は秘密のがんばり甘奈、夏配布真乃、スタァライトめぐる、ヒーロー果穂、特訓夏葉、レイニー三峰とかなんかDaマスタリーが高いかコミュがDa寄りなサポを適当に(いい具合に)選びます。サポスキルがDaじゃなかったらゲストに入れておきましょう。SRは凸を稼ぎたい。
②オーディションの基礎知識
敵は一定の行動ルーチン(遷移、スピア)に則って行動します。また得意属性が存在しており、得意属性の審査員へのアピールはExcellentとなるので、ダメージが半減しません。ダンベルをダンベルたらしめる原因です。詳しくはWiki参照。この記事では見なくても(覚えなくても)問題ないです。(嘘)
あと、思い出アピールは思ったより弱いです。Lv2以下なら基本的に使い物になりません。Lv3でもあんまり信用できません。どうしても1stを取りたい(かつ低火力で問題ない)ときにだけ使いましょう。火力が足りなかったらパフェすれば1stです。目押しを頑張りましょう。練習あるのみ。プロ根性の一個前以外は90%くらいの確率でパフェが欲しいです。
③シーズン1
ラジオとトーク。人がいっぱいいればDaも一考。オーデは受けなくてもいいし、むしろ最初の週に受けてもいいと思います。終わりまでにMe,SPが150,Daが200行くと順調？
④シーズン2
上に同じ。もう少しDaに振ってもいいかもしれません。終わりまでにDa300、Me175あると良い？あとは金枠バフとアピが1つは欲しいところ。
⑤シーズン3
ここでは4万オーデを1回、5万オーデを少なくとも2回、できれば3回勝っておきたいです。
ある程度サポのレベルが高ければ、まあ流2でも勝てると思います。シーズン終わりまでにDaは500行っててもいいです。そうじゃないと10万オデが流1で殴り勝てません。Meはいくつあっても死ぬときは死にますが、とりあえず260は確保しておきたい。
⑥シーズン4
ちょっと安定しません。WINGよりマシですが。
10万オデを3回(+5万を1回)勝つ必要があります。
10万オデは、まあまあのステータス(Da500)と平均Lv60以上のサポ、少しの運(具体的に言うと2.5倍以上をを金バフ付きで打てるくらいの)があれば流1でも殴り勝てます。なかったら大人しく流2のときに挑みましょう。が、審査員が帰るまでのターンが延びるので、必然的にメン死の可能性が高くなります。安定しないので、祈りましょう。
5万オデは流1でも2でも死ななきゃ受かります。かんたん。
⑦WING準決
まずはお祈りです。流1がVoかDaなら流1スピアでほぼ勝てます。パフェミスったりサポしか来なかったりするとたまに(特にVoの時)負けます。残念。
流1がViなら雑誌を使いましょう。基本的に流1Viは勝てないものと思ってください。勝ちたかったらWiki参照。
⑧WING決勝
もう一回お祈りです。準決でVoが流1だった人は多分お祈りする必要がありません。Daだった人は祈りましょう。ダメなら雑誌を使いましょう。準決で使ってたら諦めましょう。
流1がViかDaならスピアすればまず勝てます。
流1がVoのときは負けです。泣きましょう。
⑨優勝、True
おめでとうございます。
