AtCoder Grand Contest 048
コンテスト前のレート:1719
レート通りのパフォーマンスが得られる順位:507位(300点、7分05秒)
A - atcoder < S
思考過程
- とりあえず、最初から条件を満たしていたら。
- "atcoder"とを先頭から比較していき、最初に前者の方が大きい文字となった位置をとする。
- の文字目を、~文字目まで移動させるということを全部試し、条件を満たす中で最小値を求める。全体でくらいの計算量。
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); int inf = 1000000000; char[] s1 = "atcoder".toCharArray(); label: for (int i = 0; i < t; i++) { String s = br.readLine(); if (s.compareTo("atcoder") > 0) { // 思考過程1 System.out.println(0); } else { char[] s2 = s.toCharArray(); int min = Math.min(s1.length, s2.length); // 思考過程2 int f = 6; for (int j = 0; j < min; j++) { if (s1[j] < s2[j]) { // このブロックいらなそう System.out.println(0); continue label; } if (s1[j] > s2[j]) { f = j; break; } } int ans = inf; for (int j = 1; j < s2.length; j++) { for (int j2 = 0; j2 <= f && j2 < j; j2++) { if (s2[j] > s1[j2]) { ans = Math.min(ans, j - j2); } } } if (ans == inf) { System.out.println(-1); } else { System.out.println(ans); } } } br.close(); } }
ここまで26分02秒+0ペナ。337位。
B - Bracket Score
問題
TLE解法しか思いつかず。
思考過程
- "(())"のような文字列を作るくらいなら"()()"でよいので、括弧が開き続けるとしたら交互になる。
- :番目まで見て括弧から始まって文字開いている状態の最大値
をしてみるとくらいかなと思いつつ、他に思いつかなかったので念のため実装してみて案の定TLE。
C - Penguin Skating
問題
残り時間数分でやっとサンプルが合ったがWA。
思考過程
- の箇所を動かすことはなさそう?
- 上記の箇所を除くと、が連続する区間とが連続する区間に区切れる。
- 以下、が連続する区間について見てみる。
- 個目はならばOK。 ※は左端のマスか、(区間内の最初の要素)のつ前の要素とする。
- 個目はか、ならばOK。
- 個目はか、か、ならばOK。
- ・・・のようになっている気がする。
- これはSetを用いて毎回要素をつずつ追加していっての部分を上手く合わせれば存在判定できそうと思ったが、可能かどうかだけでなく最小手数も必要だった。
- 追加要素は単調増加なので、何番目の要素に当たったかから必要手数がわからないかとかやっていたが、サンプルくらいしか合わず。
最終結果:Aの1完、26分02秒、615位、パフォーマンス1534
レート変動:1719→1702(-17)
今回はBとCの解法がかすりもしていないのでどうしようもない。
4連続冷えで、過去のLongest 冷え Streak(ABC161, 162, 164, 165)に並んだ。
なお、最高レートからの下がり幅が118となり、これも過去最悪。
ここ数ヶ月、コンテスト参加と解けなかった青diff以下の復習だけは欠かしていないのだが、それだけではレート維持もままならないのか・・・。
最近解けなかった問題が以前なら解けたかというと、あまりそうは思わないので、弱点を連続で突かれまくっているか、周りの成長が早すぎるかであると信じたい。