PAST1

PAST1

■A - 2 倍チェック (3分)
string→int

■B - 増減管理(4分)
配列を舐めるだけ

■C - 3 番目(2分)
配列のsort

■D - 重複検査 (5分)
配列舐めるだけ

■E - SNS のログ(20分+1WA)
愚直にやるだけなんだけど1WA

■F - DoubleCamelCase Sort(11分)
大文字のまま持ってるとsortが期待通りにならないので
大文字と小文字をpairで持つか、一旦小文字に直したものを一部大文字に直すとかが必要

■G - 組分け (15分)
bit全探索の2^nではなく3^nのver

■H - まとめ売り(30分)
遅延セグ木
遅延セグ木になれないと。。

■I - 部品調達(15分)
ditDP

■J - 地ならし(10分)
３方向からダイクストラ

■K - 巨大企業(15分+１WA)
LCA。rootが0固定と勘違いしてWA

■L -グラデーション(15分)
最小全域木のライブラリを持っているかどうかそれだけ

■M -おまかせ
典型的な二分探索

■N-整地
イベントソートとか言うらしい。
結果が変わるタイミングのみmapで記録しておいて後で累積和チックに処理
両端の処理だけ注意する

■O -持久戦

確率DP。サンプルの数字がどうやって出るかがわかれば出せる。

PASTは教育的セットなのでやったほうが良さそう。

前回のABC-EがPASTにあったとか聞いたので

それならやっとこうと思ったけど思っていた以上に良問揃い。

ABC184：リアルタイム参加

ABC184：リアルタイム参加

■A - Determinant (1分)
内積
cout << a*d - b*c <<endl;

■B - Quizzes(2分)
書いてるとおりに実装

■C - Super Ryuma(20分+1WA)
0になるケースを忘れてWA
maxでも3なのは簡単に示せるけど
2になるケースが意外と面倒。

■D - increment of coins (11分)
確率DP
dp[i][j][k]　= (dp[i + 1][j][k] + 1) * i / (i + j + k);
+ (dp[i][j + 1][k] + 1) * j / (i + j + k);
+ (dp[i][j][k + 1] + 1) * k / (i + j + k);

■E - Third Avenue(44分+2TLE)
23分ぐらいで解けてたはずなのに。。
通常のBFSを少し変更したものを提出したらにTLE
priority_queueをqueueにしてもTLE(当たり前)
一度使ったテレポートを使わないようにしてO(HW)に抑えるとAC

■F - Programming Contest(17分)
bit全探査を普通にすると2^40 = 10^12なので無理。
前半後半に分けるとそれぞれ2^20 = 10^6に収まる。
それをしゃくとり法してAC

◆結果
Fまで94分+1WA+2TLE(109分)
パフォーマンス1732

◆感想
水diffとはいえABC6完はリアルタイム参加だと初めてなので嬉しい。

◆反省
CのWAと10分は削れるはず
Eの20分と2TLEも削れるはず
1TLEは仕方ない？としても無駄な15分は削れるはずなので

Fまで64分(64分)
パフォーマンス2098

Fまで69分+TLE(74分)
パフォーマンス1981

ぐらいは頑張れば出せたはず。

ABC130(二回目)

ABC130：二回目

■A - Rounding (1分)
if

■B - Bounding(3分)
足し算

■C - Rectangle Cutting(3分)
長方形を二分割するには中心を通る必要がある

■D - Enough Array (15分+1WA)
long longにしないとWA
尺取法

■E - Common Subsequence(13分)
二次元累積和風

■F - Minimum Bounding Box(7分)
最近やった。
結果が変わるときのみ見る。

◆Eまで35分+WA(40分)
パフォーマンス2102

ABC129(二回目)

ABC129：二回目

■A - Apple Pie(1分)
std::sort

■B - Balance(7分)
問題文を読み間違えた
absが使えれば十分

■C - Typical Stairs(6分)
変速フィボナッチ

■D - Lamp (9分)
参考：HHKB プログラミングコンテスト 2020
E - Lamps
実装するより自分の過去からパクってきたほうが早い。

■E - Sum Equals Xor(8分)
桁DP
条件に対してn桁まで見て
確定と未確定でDP[0][n]とDP[1][n]を持つ

■F - Takahashi's Basics in Education and Learning(24分)
橙diff
行列の掛け算に落とし込めるか。
繰り返し二乗法を使わないとTLE。
X^7 = X^4 * X^2 *X;
行列の掛け算はたまに使うので、ライブラリ化しておくと早い。

◆Eまで31分
パフォーマンス2317
◆Fまで55分
パフォーマンス：2400

ABC128(二回目)

■A - Apple Pie(1分)
割り算

■B - Guidebook(3分)
tupleが使えますか？

■C - Switches(12分)
全探索

■D - equeue (22分+1WA)
全探索

■E - Roadwork(21分)
青diff
難しい。
lower_boundとupper_boundをsetに対して行う

■F - Frog Jump(30分)
橙diff
問題文をちゃんと読む。
進んで戻って進んで戻ってを繰り返すしかできないことを
読み違えて大幅ロス。

◆Dまで38分+1WA(43分)
パフォーマンス1694
◆Eまで60分+1WA(65分)
パフォーマンス2141
◆Fまで90分+2WA(95分)
パフォーマンス：2400

二回目なのにDでEに手こずり過ぎ。

ABC127(二回目)

■A - Ferris Wheel(1分)
if else が使えますか？

■B - Algae(1分)
forが使えますか？

■C - Prison(8分)
min maxとコーナーケースが処理できますか？

■D - Integer Cards(11分)
mapが使えますか？

■E - Cell Distance(22分)
青diff
あなたのmintはchooseが使えますか？

■F - Absolute Minima(25分+2WA)
青diff
作図をすると
N個数の配列の真ん中をクエリごとに取り出したいことがわかる
毎回ソートしているとTLEするので
前半部と後半部とpriority_queueで保持して管理しておく。

◆Eまで43分
パフォーマンス1954
◆Fまで68分+2WA(78分)
パフォーマンス：2400

ABC126(二回目)

ABC126
ジャッジトラブルのためUnrated

■A - Changing a Character(2分)
大文字を小文字にできればOK

■B - YYMM or MMYY(7分)
charをintにできればOK

■C - Dice and Coin(6分)
doubleが使えればOK

■D - Even Relation (10分)
辺に情報を持たせたDFSが使えればOK

■E - 1 or 2 (2分)
UnionFindが使えればOK

■F - XOR Matching(23分)+2WA
0 = 0;
0 xor 1 = 1
以下、
0 xor 1 xor 2 xor ,,,,,,,,,,,, 2^N -1 = 0

Eまで27分
Fまで50分+2WAの60分