ABC172に挑んだ回

ちょっと今回異様に難しくないですか?
B止まりはめちゃくちゃ悔しい。
発想力というか、柔軟さに欠けている。

C - Tsundoku

最初愚直に少ない方を加算してた。
その後問題文見返して、あぁDPか。DP理解できないって逃げた。
そして蓋を開けたらDPじゃない。なにこれ。

解答は解説通り。

D - Sum of Divisors

約数の情報を保存して計算回数減らしたりするかなー。
でも面倒だし、DPの勉強してこよって逃げた。
仮に約数に着目して続けてたとしても、時間的に間に合わないように作られてたらしい。
ある意味逃げてて正解。
そういう部分も計算量からぱっと理解できるようになりたい。

約数うんぬんから目をそらして、普通に計算式としてどうなりそうかに着目すべき?だった問題らしい。
(解説PDF見てもあんま理解できなくて、他の人の答えを見ながら考えて理解した。

例題ケースの[4]の場合、約数の件の詳細は以下のような感じ。
1:1→1個*1
2:1,2→2個*2
3:1,3→2個*3
4,1,2,4→3個*4

1は1,2,3,4…のすべてで登場するし、2は2,4,6…の2の倍数、3は3,6,9…の3の倍数で登場する。
ので、これらの登場回数を配列でカウントして、最後に配列のインデックスで掛け算すれば答えになる。

DP

↓見ながらお勉強中。
蛙は飛ばしたよ。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a

ABC171に挑んだ回

今回で通算10回目。
うち2回は数年前のこと&週1開催だから最近2ヶ月はAtCoderと共にいたことになる。
お前とも長い付き合いになってきたな。

今回はDまで突破。

C - One Quadrillion and One Dalmatians

むしろCの方が細かい計算ミスして時間食った。
テスト書きながらでもやったほうが良いんだろうか…。

26(z)、27(aa)、51(ay)、52(az)、53(ba)近辺の値が怪しかった。
1の位、10の位がaになる計算をとち狂いがち。

D - Replacing

絶対愚直に計算したらTLEだろうなぁ。まぁTLEケースも試そうかなぁと思ったけど面倒で、思いついてた方法を書いたら一発通過。
うれしみをかんじます。

E - Red Scarf

にゃんにゃん。
こうかも!って思ったときに思考ロックしちゃって他の考えに及ばなくなるのはよろしくない。
先にソース見て完全なる間違いを理解した。

A xor Bの結果は、1:奇数回出現 0:偶数回出現 の意味になる。
2進数表示(cout << std::bitset<6>(k) << endl;)しながら考えると、
すべての値をxorしたkは01110
2^4が偶数(0)、2^3が奇数(1)、2^2が奇数(1)、2^1が奇数(1)、2^0が偶数(0)回出現する。
猫②③④をxorした値が10100
①以外の出現回数で、2^4が奇数(1)、2^3が偶数(0)、2^2が奇数(1)、2^1が偶数(0)、2^0が偶数(0)回出現する。

①+②③④で出現回数をkにしたいので、
 偶数(0)と偶数(0)→出現の必要なし(0)
 奇数(1)と奇数(1)→出現の必要なし(0)
 偶数(0)と奇数(1)→出現の必要あり(1)
という変換を噛ませたい。つまりこれ、xorと同じ。
k xor ②③④すれば良し。

上記を踏まえてコメント追加。考えるべきはここだけだった。
これ突破率高かったのに超えられなかったの悔しいなぁ。

ABC170に挑んだ回

今回はD突破ならず!迷走した!

D - Not Divisible

エラトステネスの篩的なことはやってたけど、素直に計算してると時間がかかるそうな。

篩に掛けた済フラグリスト(checked)的なものを用意して、対象の値をひたすら埋めていく方が速いらしい。
数が少ないときは逆に遅いけど、多くなってもそれなりに一定っぽい?

この先早く処理するためには計算しない(フラグを取っておく)みたいな対処も必要そう。
(これに気付けなかったのでエラトステネス自体が間違いかと思って因数分解とか見てた

E - Smart Infants

↑で詰まってたので軽く見たけど面倒そうだったので撤退した。
敗因としてはmultisetとかいう便利なやつを知らなかったので、それ知ってたら存外解けたかも。rbeginで末尾の値も取れるのね。便利。
あとは「1人も園児がいない園は計算対象外」とかを読み忘れてたり、インデックスのズレが怖いなぁとかやってたり。

ABC169に挑んだ回

今回も幸運にもD突破。
勉強したソースは残しておくもんだぜ。

B - Multiplication 2

確か 10^15 10^15 になった場合の値がおかしくて死んだ。
以下のケースに当たったら途中抜け、そうじゃなければ続行できる。
①数値リストに0がいたら答えは0
②掛け算する値が指定値超えたら-1
③a
b > 指定値 は-1 → 指定値 / a < b は-1

C - Multiplication 3

doubleの丸め誤差に殺された。
偶然double 1.98 →1.9777777…9みたいなことが起きてそのことに気づけた。
小数第2位まで有効とのことだったので、じゃあいっそ文字列で取得して/100したらいいのかとたどり着けて事なきを得た。

0.001の微小値を加算すると回避できたらしい?
https://drken1215.hatenablog.com/entry/2020/05/31/224300

D - Div Game

素因数分解した結果を保存してるmapのソースを残してたのが役立った。
AtCoder 版!マスター・オブ・整数 (素因数分解編)

同じ数字は使えないので、2の累乗だと2=2^1、4=2^2、8=2^3…。
1~nを足し合わせたときの数までが使えるので、8まで使いたいときは2^6が素因数分解に含まれてればOK。
素因数分解して、例えば例にあった24は2^3 * 3^1。x^3だと2回、x^1だと1回で計3回。
ちなみにx^2だと既出の数値を使ってしまうので1回…みたいな丸め込みが必要になる。

1~nまで足し合わせた数式リストを作って、

↑の素因数分解ソース参考にした因数分解mapを取ってきて、
因数分解した数値の乗数の回数を足してくと完成。

100で足りなかったらリスト追加で作ろう…と思ってたら意外と通ってしまった。

E - Count Median

入力例1ケースで4種類で3なのに入力例2ケースが答え9991になるって言われて頭パーンなってしまったので撤退した。
でも冷静に見たら問題を読み違えているね。かわいそう。

問題

数値X1はA1~B1の間になる。(A1=2,B1=4ならX1=2,3,4のいずれか)
数値XxはN個定義されている。
すべての組み合わせを検証して、答えの数を計算する。

理解する

解説してくれてる動画があるけど理屈がまだ理解できない…
https://www.youtube.com/watch?v=JDc-T9j7hZo

理解したかも?

重複しない答えの数を数えるだけなので、中央値の最小値と最大値がわかれば、その差分が答えになる。

例えば、例として↓。奇数個の配列を作りたかったので例題とはちょっと違います。

中央値の最大値は、XxがすべてBの場合の中央値が該当する。2,3,4→3
中央値の最小値は、XxがすべてAの場合の中央値が該当する。1,2,3→2

この例の場合は中央値が取りうる値が2~3なので、取りうる答え=3-2+1=2個。

偶数個の場合は中央値の取得条件が変わるのでそのへん注意。

というわけで、まずminとmaxのソート済み配列を作る

偶数・奇数で解答ケースを分ける。
奇数の場合は中央値は実数だけだから素直な計算になる。
例えば2と3で2個。
偶数の場合は0.5を考慮するので答えが2倍の数になる。
例えば例題ケースは3個。
maxCenter(2+3)-minCenter(1+2)+1 = 5-3+1 = 3(実態は1.5・2・2.5の3つ)

所感

なんとか理解したぞぅ…!解説動画に感謝。
一見愚直に計算しそうに見せかけてそうでもない問題って難しそう。

ABC168に挑んだ回

今回はDまで突破出来てパフォーマンス890。
ついにRateも茶色に到達しました。やったね。
今回の問題のタイトルがなんだかおしゃれで素敵。

数式が書けるプラグイン入れて記事書いてる最中は数式で表示されるけど本番だと表示されなくて悲しんでる。
そのへんは心折れてしまったのでそのままです。
WordPressでKaTex記法(≒Latex記法)で入力して数式をレンダリングする 【WP Githuber MD】

C : (Colon)

愚直なので座標計算して長針・短針の間の距離を計算してました。
でも余弦定理で計算できたそうな。なるほど。
こういう計算式についてはすっぱり忘れてるので良くない。

余弦定理

$$(三角形の面積)=\frac{(底辺)\times(高さ)}{2}$$

時針・分針=bとc、θは2つのなす角度で求まる。
角度は時針が{(H/12)+(M/60/12)} *2π、分針が{M/60}*2π
時針-分針で求まる。

引っかかりポイント

  • いつもの癖で浮動小数点の値を12.fとかFloat型にして死んだ(精度が下がる)
  • 普通にcoutすると出力桁数が足りなかったのでfixed << setprecision(20)で出力調整が必要

愚か者の解法

本戦中は座標計算してた。まぁ間違っちゃいないよ。通ったんだもん。

座標回転の計算式

D - .. (Double Dots)

BFS(幅優先探索)問題だそうな。
BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜

再帰で解いたけど、キューを使って解いたほうが頭良さそう。
再帰が619ms、キュー版(下)が331msだったので実行時間も優秀。

引っかかりポイント

  • 解答を入れてた配列がunordered_mapで、実行環境とABC環境で出力順が違う原因に気づかず死にまくった。

E - ∙ (Bullet)

残り10分くらいだったので諦めた。
イワシの問題。解きたかったですね、閣下。
Ai+AjとBi+Bjが~なときは~みたいな問題は先にそのケースとか計算を列挙しとけ的な知見を得たけど、肝心のその問題、何だったっけなぁ…。

いつもお世話になってる解説を参考に後でお勉強する。
(ここまで書くのに1時間かかって疲れた
(Bullet) [AtCoder Beginner Contest 168 E]

ABC167に挑んだ回

AtCoder初心者なのでまだ参加回数6回のCかD問題で死ぬ人。
その上で新しいアルゴリズム勉強して、忘れないようにメモってるだけです。

C - Skill Up

N<12だから全探索でいいよね?でやって正解できた。
買わなかったケース・買ったケースで再帰組んでます。

回答例もググってみた。
この手の重複なしの組み合わせ探索にはbit探索が使えたらしい
bit全探索について簡単にまとめる
値を1ずつ増やしてbit単位で値を見ると、確かに全パターン列挙できるね。

D - Teleporter

駄目だった。(ループをゴリ押し計算したりした)

ので、回答例をググってみて再挑戦。

ダブリングについて初めて知った。
今回みたいに同じ要素を重複して回るときには使うことになるようだ。