ABC292 ~Rubyで解いてみた2~

ABC292

2023/03/18, 2023/03/19

  • このセット、Fが数学問題だったからかなりパフォ貰えそうで、(リハビリ終えた上で)リアタイで解きたかったなぁ〜という気持ちに!
    • と一瞬思ったが、Rubyで書いていたらE問題で絶対ペナってただろうから、そんなことないか😐
    • 引き続き精進頑張る🔥

A

  • 自然に解いても1行なの嬉しい!笑

B

  • case, when 自分では最近書いてなかった気がするから久々の登場

C

  • 約数の個数を先にカウントしておけば良い
    • めっちゃ見覚えのあるやつだ〜
      • この計算量が意外と少なくて済むの懐かしい……!

D

  • map!(&:uniq!) と、 map!(&:uniq) と、 map(&:uniq!) の比較、面白いかも!
    • (私が)通常やりたい!と思うであろうものは、3つ目で実現できる
    • と思ったけど、これ不要そうだった泣
  • has_seen = [false] * n と、 edges = Array.new(n) { Array.new(0) } の差を再確認した
  • とりあえずUnionFindで連結成分出しておいて、後から点の個数と線の個数数えるのが良さそうと思った
    • 計算量も足りている感じがするし
  • Array#inject を使うときに、初期値を入れないとよくわからない挙動になった
    • 先頭の要素のループに入らない?
      • TODO: 確認する
  • TODO: ngtkanaさんの解説 の考え方で、私の実装の後半部分は大幅カットできるからやる
  • UnionFind のメンテをした

E

  • 任意の点から、到達できる点全てに辺を引くようにすればok
  • Thread::Queue 初めて使ってる!
    • pop が、空で実行したら勝手に止まってくれるのは良さそうだけど、Thread.start をしないといけないぽいね……?
      • だったら、普通にempty?か見てから進むほうが簡単かな
  • Queue#new に引数入れられるのは、今のAtCoderのv2.7じゃダメだった〜!
    • 提出したら ArgumentError で落ちてガン萎え 😭
    • EasyTest の方は通ったから気づかなかった〜
      • コードテストで試すか、
      • TODO: 自分の手元のRubyのバージョンを合わせる必要があるね〜!

F

  • ただの数学問題で笑った
    • 完全に高校数学の三角関数じゃんね🤣
    • sinθcosθを消すの懐かしい
  • 長さの比が半端なく大きい時にだけ注意だ!

ABC293 ~Rubyで解いてみた1~

ABC293

2023/03/18

  • ブランクがありすぎる故にポンコツすぎて笑ったけど、弊社に3月に来てくれた人が競プロ始めると言っていたから私も再開🚀
    • 自分もちょっとRubyでやってみたかったのと、その人に合わせて、せっかくなのでRubyを使ってみる

      • 調べてみると、Rubyで青になった人が居るのを知ってびっくり!
    • kona0001.hatenablog.com

  • 久しぶりにやると、ちょっと解いただけでも、競プロと業プロの違いを痛感する……!

A

  • chomp しないといけないのを忘れてて、ちょっと止まった
    • Pythonの癖が抜けないのかな
  • 三項演算子使えばシュッとかけるの最初からは見えなかった
    • とても悲しい
  • 新しい配列を作り直さないで、順番に出力してしまえば良い
    • でもこれってかなり競プロ的だよね……!

B

  • String#split
    • 引数がデフォルトで ' ' なの忘れてた
    • 前後の空白を削除してくれるから、chompしなくて良いのも忘れてた

C

  • rubyではbit全探索よりcombination全列挙のほうが早かった を参照
  • Array#filter{hoge}.size は、Array#count{hoge} でOK
  • Array などを空で用意して each で追加していくのなら、初めから Enumarable#each_with_object を使うのが良い!
    • 以前業務でやったやつを使えた〜!
  • Set#add? も前に使った記憶あるなぁ(しみじみ)
    • require set しないといけないの悲しい
  • 縦と横を間違えて、1ペナもらったの痛すぎる〜!!!
  • debug 用に、pp をたくさん仕込んだ😎

D

  • 自分の端が、それぞれ繋がっているかだけ管理すれば良さそう
    • 最初、どのグループに所属しているかも考える必要があるかなと思ったけど、そんなことはなかった
      • 環状になっているもの、そうでないものの数だけ出せば良いから
    • 「最後にまとめて集計すれば良い」と最初は思ったけど、そうじゃなかったことには注意だ
      • 環状の方は、環状になった時にカウントしていけば良いね!
      • 環状になっていないものは、左端だけ数えればok
  • 2回と同じ端が出てこないのすごい嬉しい!
    • だいぶ実装を軽くしてくれている😭
  • 色々考えていたけど、結局UnionFindも必要やんけ!
  • attr_reader にすべきか、 attr_accessor にするかは悩むけど、とりあえず attr_accessor にしておいた!
  • いきなりUnionFindを準備できたのはラッキー!

*E

  • 周期性があるやつね!!と思ったけど、m が大きすぎるからこれはだめ
  • 割り算ができれば良いけど、 m と a-1 が互いに素かわからん
  • 繰り返し二乗法の応用を頑張る!
  • Ruby の場合は、Interger#pow がめっちゃ便利じゃないか!!
  • kyopro_friendsさんの解説 天才すぎる

ABC239 Fまで!

ABC239

2022/05/26まで。A~F

A

  • 展開して、xを外に出しておいたら誤差でサンプル合わなくてびっくりしてしまった…。
    • 反省

B

  • 数でやれば良いのに、文字列でやろうとしてわけわかんなくなった反省
    • ちょっと数を足して調整した
  • Nyaanさん解説にある、次は知らなかった
    • A / B - (A % B < 0) でも一発!

C

  • 候補になりうる点をちまちま入力したけど、近くの点だけ全部距離を確認していくというの方が楽だね📝

D

  • 制約も厳しいから、これは灰Diffでも納得
  • Dにしては、問題を正しく読むのが難しいだけのタイプと感じた

*E

  • 提出
    • snukeさんの解説内容もコメントに入れた!
    • ラムダ式に慣れていないのに、[&]の話だったり、更に再帰だったりで結構しんどかった!

*F

  • 最終提出
    • snukeさんの解説内容も取り入れてコメントした!
  • これコンテスト中に通せたら気持ちいいだろうなぁ〜〜!!という気持ち…!
    • とても面白い
    • 構成できるなら残りの最小次数は必ず1になるとか、考えたことない人が自分で気付くの無理では!?

ABC241:Eまで埋めた!

ABC241

埋め埋め

  • D問題キツかった
    • a.end()はだめ。a.begin()はok(その前はだめ)という気持ちがもっと必要だったと反省!
  • E問題をシュッと実装できたからよかった😆✨
  • DやEの別解は、積み残しということで米マークだけ付けて先に進む🚀

A

  • 数列の添字も0始まりだから親切!

B

  • multiset の erase は、数字を入れると1つじゃなくて全部消し飛ばすようで、iteratorを使った

C

  • 結構面倒だった
  • 問題に書いてある通りに6x6のマスを取り出して考えたけど、無駄が多いから縦、横、斜め3通りをそれぞれ別々に考えた方がよかったかな

*D

*E

  • k が大き過ぎるのが嫌なだけ!
    • ループに入る前、ループで回り切る分、ループの1周し切らないで余る分の3つに切って考えれば簡単!
  • [TODO] ダブリングの実装もしたい!!!

ABC242:Eまで埋めた!

ABC242

埋め埋め

  • Dは問題読んだとき、解けたと思ったら、tが大き過ぎて全然解けていなかった!!!

A

  • setprecision(10) を一生覚えないけど、今日で覚えたかな〜😏

B

  • え??こんなに簡単なことある??と思った!笑

C

  • ACLのmodint が便利すぎる!!!
    • .val() を使わないといけないのは覚えておきたい📝

D

  • 難しいと思ってしまった…!
  • t が大きくて訳が分からなくなり、動画を見てしまった。泣
    • __builtin_popcountll()を初利用!
  • 次を考えられれば解けた!!
    • tが大きければ、基本的に0文字目由来になっていると気付く
    • 0文字目だけを見ると、周期性がある
  • 解説の関数定義の仕方はまだ見慣れないから、普通に上で定義したものも書いた

E

  • WAを2回ももらったの痛い!!
    • よく考えずに、1文字だけのときを特別扱いしなければならないと勘違いしてしまった😭
  • 1文字ずつ進んでいき、「パターンX:境目の文字列と差がある」と、「パターンY:今まで考えているところまで全部一致」の2つの場合の表を考えると楽
    • Xからは、Xまでの26通りのみ
    • Yからは、(今見ている文字) - 'A' 通りがXに
    • Yはずっと1通り

ABC243:Eまで埋めた!

ABC243

埋め埋め

  • 電車で解いたり、理解しておいた問題を実装していった
  • 次の流れで精進していくのが良さそう📝
    • 考察する
    • 実装する
    • 通す
    • 文字の解説見る
    • snukeさんのコードを読む
    • 疑問があれば動画を見る
  • 今回Eまででかなり勉強できた🚀

A: Shampoo

  • 数が小さいから、3人が順に使っていく様子をそのまま実装しても解ける
  • 解説見て。 %= の存在忘れてたんだけど。。。リハビリがまだまだ必要だ😭
  • Pythonならsum(array)でかけるのになぁとか思いながら実装してた🤔

B: Hit and Blow

C: Collision 2

  • Cにしてはちょっと実装重め!
  • Lのときと、Rのときで、相手より大きいべきか小さいべきかの判断を変えないといけないことに注意!
  • リファクタリングしてだいぶきれいになった
    • 無理矢理まとめて書いたけど、よく考えたらLのとRのとで、そもそもmapを2つ用意した方が読みやすいかも!
    • if (mp[q] > x == is_r) は、かっこいいけど、読み易さが犠牲になった感じがあるよね😭

D: Moves on Binary Tree

  • 数が大き過ぎたらTLEするけど、10**18に収まる範囲だったら10**6回計算しても大丈夫というのが、感覚としてなかった
    • それでもTLEするんじゃないかと思ってた😭
  • 2進数に直していたら、末尾を操作するだけだよ、というのは確かに!!
    • 初めてreverse_iteratorを使った!
      • あとで使い回さないのなら、普通にreverseしても良いね🤔
  • string にも push_pack 使えるの、string はcharの配列なんだから、当たり前なのに忘れてた😱

E: Edge Deletion

  • ワーシャル・フロイド法、最初に使ったときは自明じゃんって気持ちになってたけど、今回また忘れてた!
  • 後から考えたら、>=とすべきところを=にしてたのに、通ってしまった

ABC244:Eまで埋めた!

f:id:Jessica_nao:20220414093820p:plain

ABC244

埋め埋め

Cがインタラクティブでびっくりした!コンテスト外で出会えたのはラッキーって思っておこう😏

Eでは、Modintがどれだけ便利かを再認識させられた!!今から使います…🔥

A: Last Letter

  • String.back() で最後の文字が取れることを知らなかった…!!勉強になる🥺

B: Go Straight and Turn Right

  • Bにしては難しいと思った
    • よくある、4つの方向をどうやって管理するのかが勉強できて良いってことなのか!
      • なんて思ったけど、別に4方向を1つずつ数字に当てはめて管理するのが想定だった模様
  • ユーザ解説の、方向転換のやり方賢い…!

C: Yamanote Line Game

  • インタラクティブ!?!?
  • flush も、exit も、初めて使おうとした…😱
    • けど、そんなのは不要で、普通にいつも通り break や return を用いれば良いだけだった〜!🤣
  • 対称戦略を用いた別解があった!?
    • 確かにすぎる…!これなら管理する必要もないし、かなり実装も簡単だ!
      • これでも書いた
  • コードテストは使い物にならないから、手元で実行しないといけないやつだ。。。😭

D: Swap Hats

  • 手元で試したら次がわかる
    • 並び方が6パターンしかない
    • aからbのパターンに移動できるのは、奇数回か偶数回のどちらかしかあり得ない
  • 回数はとても大きい偶数回だから、3つずつの2組に分けて、同じ組に属してたら変更可能!
  • 行受け取り知らなかった…😱
    • getline(cin, s);

E: King Bombee

  • これが緑パフォ(1125)は低くない!?
    • Dまでが簡単だったっていうのもあるかな?
  • 「Xを通った回数」に興味があって、偶数回、奇数回と区別をできるようにdpを作ったのに、遷移のところでカウントの仕方で混乱してちょっと手こずった😢
    • その結果直し忘れが発生して、mod計算し損ねのWAもらっちゃった😱
  • 流石に、Modint使わないのアホだと気づいた。初めに定義しちゃえば、あとはよしなにやってくれるのだから、これは使うべき
    • というか、型を定義するの…良いね🚀