ABC175 参加記
AtCoder Beginner Contest 175に参加してABE 3完で1449位だった。つまらん くやしい
それぞれC++とPython(PyPy)でのACしたコードを載せます Pythonはコンテスト後に思考を整理したりshortestを参考にして書いたので読みやすいと思います
A. Rainy Season
三文字のなかに連続する'R'はいくつあるかという問題 if文を書いた
https://atcoder.jp/contests/abc175/submissions/15966999
Python3
https://atcoder.jp/contests/abc175/submissions/15976656
B. Making Triangle
問題文を適当に読んでるので三角形が作れる組は何通りあるかだけ数えてサンプル合わねーーーーー！！！って叫んでた。がすべて異ならないといけないらしい
sortしてi,j,kを全探索する。三角形にできるのは二辺の長さがもう一辺の長さより長い時で、sortすると >
と書けて、うれしい(
が一番長いので)
←これtex:a_i+a_j + a_kって書いたら壊れるんだけどなんで？
https://atcoder.jp/contests/abc175/submissions/15967094
Python3
https://atcoder.jp/contests/abc175/submissions/15976837
C. Walking Takahashi
コンテスト中にACすることっができなかった(は？)
座標の絶対値を小さくするためにはXから0にむけて進んでくのがよくて、k*DがXよりも小さい時はX-k*Dが答え。
floor(X/D)回、座標の絶対値を小さくするほうに動くと符号が反転しない範囲で動くなかでは座標の絶対値が最小になるもう一回動くと座標が反転し、座標が反転した状態で動ける中では座標の絶対値が最小になる。
k-floor(X/D)が偶数ならX-floor(X/D)*Dが答えで奇数ならabs(X-floor(X/D)*D-D)が答えになる。
floor(X/D)をするときにXをabs(X)にしないとだめなんだけど、忘れていた
https://atcoder.jp/contests/abc175/submissions/15967314
Python3
https://atcoder.jp/contests/abc175/submissions/15976941
D. Moving Piece
これ最近のABCになかった？笑 あれの上位互換っぽい
ループに入る前までの部分、ループ部分、余り部分にわけてそれぞれ計算してmaxをとる。とWAになった。n周+αできるときにn-1周+βのほうがつよいときがある
(これPが順列なのでループに入る前までの部分とかはないですね(入次数が2になることがあると思って解いてたけどそんなことはないらしい))
https://atcoder.jp/contests/abc175/submissions/15967363
PyPy3(Python3で提出すると、TLE....)
https://atcoder.jp/contests/abc175/submissions/15977998
E. Picking Goods
dp[k][i][j] := pos(i,j)でk個選択したときのmaxというdpをすると、AC
dpは全部0で初期化して遷移は
dp[k][i][j]に対してa[i][j](アイテム)を使わないときはdp[k][i][j-1]から、使うときはdp[k-1][i][j-1]から遷移してくるのでdp[k][i][j] = max(dp[k][i][j],dp[k][i][j-1],dp[k-1][i][j-1]+a[i][j])
縦に遷移するときは行で3個までの制限がリセットされるのでdp[0][i][j] = max(dp[k][i-1][j])
https://atcoder.jp/contests/abc175/submissions/15967422
PyPy3(Python3 TLE)
https://atcoder.jp/contests/abc175/submissions/15987538
