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 のメンテをした
- メンバーも管理するように
- lib/union_find.rb にファイルを作った
- まぐまぐの を参考にさせてもらった
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月に来てくれた人が競プロ始めると言っていたから私も再開🚀
「明日のABC出ようかな〜」って言うようなバックエンドエンジニアの人が今月入社してくれて、非常に嬉しいです私🥹
— 朝型のジェシー@MNTSQ (@Jessica_nao_) 2023年3月10日
日頃会う人でやる人がいるって、やっぱり格別だね!!!明日はリアタイでは出られないけど、少なくとも解くぞ🚀自分もちょっとRubyでやってみたかったのと、その人に合わせて、せっかくなのでRubyを使ってみる
- 調べてみると、Rubyで青になった人が居るのを知ってびっくり!
- 久しぶりにやると、ちょっと解いただけでも、競プロと業プロの違いを痛感する……!
- 名付けとか、わざわざインスタンスを新しく作らないとか
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も必要やんけ!
- 元々その2本が同じグループに入っていて繋がりcycleになるのか、そうでないのかの判定が必要だ〜!
- 参考
- 条件がかなり優しいから、両端がどうとかの管理は不要だった〜!
- すでに結ばれている端が登場することがないとか
- つまり、両端を区別しないでよかった。。。
- すでに結ばれている端が登場することがないとか
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
*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()
を初利用!- ref. popcount
- 次を考えられれば解けた!!
- 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人が順に使っていく様子をそのまま実装しても解ける
- 最初に、使い切る直前まで3人の合計分を引いてしまうともっと速い!
- と思ったら、改善したはずの方が遅くて笑った🤣
- 最初に、使い切る直前まで3人の合計分を引いてしまうともっと速い!
- 解説見て。
%=
の存在忘れてたんだけど。。。リハビリがまだまだ必要だ😭 - Pythonなら
sum(array)
でかけるのになぁとか思いながら実装してた🤔
B: Hit and Blow
- 2重ループと、setを利用して解いた!
- 1つ目と2つ目を同時にやって行った方が、無駄がなくて良いよね😏
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しても良いね🤔
- 初めてreverse_iteratorを使った!
- string にも push_pack 使えるの、string はcharの配列なんだから、当たり前なのに忘れてた😱
E: Edge Deletion
- ワーシャル・フロイド法、最初に使ったときは自明じゃんって気持ちになってたけど、今回また忘れてた!
- snukeさんの説明ものすごくわかりやすかった!
- 後から考えたら、
>=
とすべきところを=
にしてたのに、通ってしまった- まだなぜかわかっていない
- この提出
ABC244:Eまで埋めた!
ABC244
埋め埋め
Cがインタラクティブでびっくりした!コンテスト外で出会えたのはラッキーって思っておこう😏
Eでは、Modintがどれだけ便利かを再認識させられた!!今から使います…🔥
A: Last Letter
- String.back() で最後の文字が取れることを知らなかった…!!勉強になる🥺
B: Go Straight and Turn Right
- Bにしては難しいと思った
- よくある、4つの方向をどうやって管理するのかが勉強できて良いってことなのか!
- なんて思ったけど、別に4方向を1つずつ数字に当てはめて管理するのが想定だった模様
- よくある、4つの方向をどうやって管理するのかが勉強できて良いってことなのか!
- ユーザ解説の、方向転換のやり方賢い…!
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使わないのアホだと気づいた。初めに定義しちゃえば、あとはよしなにやってくれるのだから、これは使うべき
- というか、型を定義するの…良いね🚀