- やった回: ABC343
- 成績: ABCD4完 / 1ペナ / 28:14(ペナ込み)
- パフォーマンス: 1002(unratedなので推定)
1ヶ月ぶりどころじゃなかったので今回もunratedにしました。でもパフォーマンスだけ見ると比較的良かったほうとは言えそうなんですが、DとEに若干の悔いが残る感じではあります。
チラッと読んでそっ閉じしたFはセグ木が分かればシュッと解けたという噂も見たような…?そろそろもう一段階上の解法をやらねばと言い始めて何か月経ちましたかね、という気持ちです。
A問題: ABC343-A Wrong Answer
0から9までの間でa + b
じゃない値をfindする。出力例が(もちろん正しいんだけど)地味に惑わせに来ている。
ついついLaravelの Collection::first
のノリで Array#first
にブロック突っ込んじゃうんだけど、条件付けたいときは Array#find
なんだよね。
B問題: ABC343-B Adjacency Matrix
配点を見ずに解いたので、B問題にしてはシンプルすぎて「これでいいの…?」と戸惑いながら提出した問題。
提出コードではmapしてcompactして、ってやってるんだけど、これを纏める過程で「いやいやこれ一気にやるメソッド絶対あるでしょ」って調べてみたら Enumerable#filter_map
がありました。
C問題: ABC343-C 343
どちらかと言うと数学問題。
最初に3乗根を求めて探索上限を決めるか、 while i**3 <= n
するかのどっちかなんだけど、いずれにせよ3乗根の方を管理していかないとTLEするいつものやつ。
ループ回数さえしっかり管理出来れば後はto_sしてreverseした結果と比較するだけ。
D問題: ABC343-D Diversity of Scores
これもデータ構造方面でよく見るパターンのやつというか、そこまで言える割に個数管理をサボって1ペナ食らっているのが悔しい。
この手の問題はもうひとひねりあって計算量がシビアなやつが時々E問題に出てくるイメージが個人的に強い。
E問題: ABC343-E 7x7x7
(upsolveコード) atcoder.jp
問題文を読んだ直後は半ば諦めムードがあったものの、とりあえずaの立方体を原点に固定した上でb,cを全探索する時間はありそうだ、というところまではたどり着く。
謎に3次元いもすを引っ張り出してきてまで頑張ってみたんだけどサンプルすら途方もない時間がかかる*1状態のままコンテストは終了。
解説の実装例と他の人のRubyでのACコードのほぼ写経でとりあえずAC。解説コードの素朴な写経だとRuby(というか私の実装)では3ケースほどTLEが取れず、他の人のACコードを見せてもらったところbの立方体の探索範囲を全部の座標が正数*2の範囲に収まるところだけに絞ることで間に合うようになるらしい。
全体的な方針はともかく、立方体の重なり範囲を計算する処理(*_length
を求めているところ)がさっぱり頭に入らず、今後のコンテストで似たようなことをする必要が出てきたら当面はこの記事を引っ張り出すしかないな、という気持ちでいます。
ということで、今週も対ありでした!