競プロっておいしいの?(仮)

ABC172 参加記

お久しぶりです。

久々に競プロ界隈に戻ってきたのでいつもどおりアウトプットをします。これは自分の感じたこと,考えたやり方を記録するのが目的です。

もしそれが他の人の考えの手助けとなれたらそんなに嬉しいことはありませんが,それは狙ってませんので,かる~くログなんだなと眺めて欲しいです!

あくまで緑くらいの視点の考え方です。

A問題:Calc

C++erなので, cout<<A+A*A+A*A*A;をして終了。簡単な計算ができますか?ということですね。

B問題:Minor Change

文字列の一致問題なので1文字ずつ見ていくと解けます。 if(S[i]!=T[i])ans++; のような感じで

C問題:Tsundoku

ココから僕が解けなかったので,考えたことを書きます。 1. 貪欲だと思った。 これは,ABの一番上に詰んであるものが同じ時に困ります。以下の例なら下の方を取ればいいのがわかりますね。

10 1 5
10 1 4

2.DFS枝刈りをしようと思った C問題だし,全探索で通るでしょ!
もちろんTLE。

結論。

今回の問題の自分なりのポイントは
「2つ同時に考えずに1つ固定」
「取って選ぶを繰り返すは一気に選んで取ると同じ」
「単調性と二分探索」
です。 そのため,Aの配列に関して累積和をとり,Aを0つ,1つ....Nつとった時を考える。 それぞれについて,K-(Aの取った本を読む時間の合計)だけ B棚の本が読める時,何冊読めますかという単純な二分探索になります。
これで解けます。

D問題:Sum of Divisors

この問題の自分なりのポイントは
「約数より倍数が扱いやすい」
です。
倍数は規則性があるが,約数には単純にn倍などの規則性がないので,倍数を考えるように変換しようとします。するとループ順序が入れ替えるという発想が出てきます。 そこで問題を言い換えると公式解説pdfのようになってとけますね。という話です。

感想。

レートは972と3桁まで落ちましたが,これからしっかり水色になれるように精進していきたいと思います。 よろしくおねがいします!!!!!!