0.はじめに
今年最後のABCということで気合を入れて取り組みました。
とこらがB問題で大ブレーキ。
Cも一筋縄でいかなそうだったので、まさかのAだけフィニッシュかと
諦めかけましたが、Dは簡単で気持ちを取り直せました。
そのあとはB,Cも時間をかけて解き、時間一杯でA~DをACして
2023年を締めくくりました。
レートは+35で半年ぶり2回目の緑コーダとなりました。
1.A - Christmas Present
BとGを比較しBが大きければバット、Gが大きければグローブを表示
BatとGloveのスペルを正しく書けるかが一番の間違えポイントな気が
しました
https://atcoder.jp/contests/abc334/submissions/48736001
2.B - Christmas Trees
最初は、RとLの差をMで割り、そこに、Rにツリーが立っていれば
1を加えてはい終了。と思いましたが、例題３が1差で合いませんでした。
おそらく、AがLとRの間にある場合とか、ALRが-とか+とかいろいろ
関係あるのかと、ALRに10**18を足してみたりいろいろしても解けず
最後は以下の考え方で解きました。
【考え方】
・Aはツリーが立っている場所ならどこでもよい。
・AがLの左にあれば、A~R間のツリー数-A~L間のツリー数に
Aにツリーが立っていたら+1を加えれば答えが求まる。
上記に従い、新Aを算出してからそれにしたがいツリー数を求め
無事ACでした。
解説を見たら、Pythonは4行で解けてたので愕然としました。
https://atcoder.jp/contests/abc334/submissions/48788455
3.C - Socks 2
初見時は時間がかかりそうなのでスルー。
戻ってきた時は残20分でしたが、なんとか行けそうかとトライ。
一見残った靴下全部をどうにかするような問題かと思いきや
結局両方残ってるのはそのまま使うのが最善なので、リスト内で
どう組み合わせる問題なんだと気づきました。
さらに、偶数余っている場合は全部組み合さざるを得ないので
単純に先頭から組み合わせて差を集計すればOK
奇数余ってる時は、どの靴下を使わないかを求める問題となりますが
組み合わせは、靴下を抜く前後でずれるだけなので
前からの差の累積和と後ろからの差の累積和を求めておき
抜いた靴下によるずれが生じる前後で累積和を足した値を求め
その差が一番小さい時が答えとなります。
アルゴリズムの問題集とかに割とあるパターンですね。
ギリギリ残り3分でACが取れたので喜びもひとしおでした。
https://atcoder.jp/contests/abc334/submissions/48796541
4.D - Reindeer and Sleigh
D問題にしては簡単な気もしましたが、難易度というよりは
よくある問題なので解きやすかったのかもしれません。
【考え方】
・与えられたトナカイ数で引けるそりの最大数を
素早く求める
・事前準備でそりごとのトナカイ必要数リストを昇順ソートし
i台目までのそりを引くのに何頭のトナカイが必要かのリストLを
生成しておく
・Q毎にリストLを2分探索し、何台引けるかを求め出力
苦手だった2分探索もbisectを知ってから、楽になりました。
https://atcoder.jp/contests/abc334/submissions/48774758
以上