AtCoder Grand Contest(AGC) 021 レビュー
大爆死
と思ってたらなんとか生きてた
今回はAtCoder Grand Contest(AGC) 021のレビューです。
問題はこちらのAtCoder公式からどうぞ。
A - Digit Sum 2
N
以下の任意の値のうち、「各桁の数の和」が最大になるような値を見つけて、その値の「各桁の数の和」を出力する問題。
N
より大きくならないように、できるだけ9
で桁を埋めていきたい。
下処理
まず、N
を、桁ごとに配列digit[]
に入れる処理をしてみる。
ついでに桁数を表す変数length
も用意したい。
とりあえず書いてみる
こんなコードを書いてみた。
int length; long long power(int exp){//10^expを返す long long num=1; for(int i=0;i<exp;i++){ num*=10; } return num; } int digitinput(void){ int i=1; int remain; while(N>0){ remain=N%power(i); N-=remain; digit[i]=remain/power(i-1); i++; } length=i-1; }
こんな感じで、digit[1]
にlength
桁目、digit[2]
にlength-1
桁目、という風に値が入る。
しかし。
バグ発生
このコードを書いて、実際に数個のケースでACできることを確認したのだが、実行時にN
の桁数が多くなるとFloating point exception: 8
と表示されてしまう。
その名の通り浮動小数点周りのエラーみたいだが、原因特定できず。
しゃーない、別のコード書くか。
無理やり突破
void digitinput(void){ length=SN.length(); for(int i=1;i<=length;i++){ digit[i]=SN[length-i]-48; } }
なにをしたかお分かりだろうか……?
string
コンテナのSN
に入力を突っ込んで、各桁のASCIIコードをdigit[i]
に入れたあとに-48
して数値化するクソコードを書いた。
ACできれば何でも良いんだもんっ
ようやく本処理
int solve_sum(int i){ int sum=0; if(digit[i]==0){ return 0; }else{ int target; for(int target=length;target>i;target--){ sum+=digit[target]; } sum+=digit[i]-1; for(int target=i-1;target>=1;target--){ sum+=9; } } return sum; } int solve(void){ int max=0; int tempans; //maxを初期化 for(int i=length;i>=1;i--){ max+=digit[i]; } for(int i=length;i>=2;i--){ tempans=solve_sum(i); if(max<tempans){ max=tempans; } } return max; }
何をしているのか具体例で説明する。N=9876
と仮定する。length=4
である。
まず、max=9+8+7+6=30
で初期化。
そのあと、「最高桁>i桁」まではdigit[]
の値をそのままsum
に加算。
i桁目ではdigit[i]-1
を加算。ここでdigit[i]-1
が負の値を取る場合は計算しない。
「i-1桁>=1桁」までは9を加算。
こうして計算されたsum
を、iを減らしつつ全て試して最大値を出力する。
i=4 sum=8+9+9+9 i=3 sum=9+7+9+9 i=2 sum=9+8+6+9 i=1 sum=9+8+7+6
こんな感じでNを超えないように全探索してみた。
まだまだ計算量削れるかもしれない。43分かけてAC。
これ以降
わからん
まとめ
A問題早解きコンテストでしたが、実装に時間取られて死にました。
と思いきや
うおお!緑入ってた!死んでなかった! pic.twitter.com/u6laWCUCit
— Arc@競プロ (@arcslab123) 2018年2月24日
緑レート達成したぜ。やったね。