競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。お金の大切さや今後の生き方も併せて伝えられたらと思います。

競技プログラミング~ABC172前半~

おはようございます。しほみんです。

 

ABC172です。今回もC問題でやばいなーと思っていたのですがなんとか切り抜けられました。C,D問題はともに令和ABC400点の中でも結構高い難易度だったのかなと思います。今日はC,Dの振り返りはしないですが、最後にABCについて思うことを追加しておきます(あくまで個人の意見なので参考程度にしてください)

 

 

https://atcoder.jp/contests/abc172

 

 

 

自分の競技プログラミングへのスタンスです。

<自分のプログラミング力>

・レートは800程度になりました。緑を何とか維持。

・C#でクラスとかつかってアプリケーションは作れます。

<Atcoderでのスタンス>

・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。

・基本的に本番でやっている。現在50回以上参加、2年目。

・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色(1200以上)は欲しい。

 

今回はABCD、75分(4WA)でした。C問題でつまってしまいましたが、D問題があっさり気が付けたので、戻ってC問題を解いた形です。E問題もなんとなく組み合わせの数問題だろうなとは思いましたが詰め切れず...って感じです。

やはりE問題になるとかなり難易度が上がるので、ABCDを早く正確に解くことを重点に置いてまずはレート上げていこうかなあと思います。

きちんとC問題も解けたのでレーディングは1184で、レートは845→884に再び戻りました。

 

今回はD問題まで振り返ります。

長くなるので前半はB問題まで書きます。なのでちょっと今日の話は微妙かもですね。

前回に引き続き考察をメインに書きます。

コードは別に上げます。

 

 

A問題

aが与えられます(1<=a<=10)

a+aの2乗+aの3乗を求めてください。

 

 

普通にa+a*a+a*a*aを出力すれば答えが出ます。

ところで、二乗とか三乗とかの乗数なのですが、C#ではMath.Powがあります。

今回なら、a+Math.Pow(a,2)+Math.Pow(a,3)とか書くこともできます。

 

ただ、Pow関数はdouble型の読み込みをするのであんまり桁が大きくなるとうまく表現できなくなります。よって、整数としてあらわしきれなくなる恐れがあります。

よって整数の乗数を考えるときはPow関数は使わず、普通に同じ数を何回かかけるといった書き方がベターです(あと楽です)。

 

ちなみに、繰り返し二乗法を使った関数を自分で用意しておくと大きな乗数にも対応できます。

 

繰り返し二乗法

・・・aのn乗数が偶数ならn/2乗数の2乗、n乗数が奇数ならaのn-1乗×aと分解していく方法。再帰関数の基本形なのでぜひ押さえておきたい手法です。

 

B問題

文字列S,Tが与えられます(SとTの文字数は同じ)

SからTの文字列に変更するとき、以下の動作は最低何回必要ですか?

動作:Sのどれか1文字を選択して、別の文字に置き換える

 

動作の意味自体を理解できれば、やることは簡単です。

1回の動作では、高々Sの1文字をTの1文字にするだけです。

なので、最大でも(Sの文字数)は必要です。

ただ、最小なので、別に上の動作をしなくてもよいことがあります。

それは、SとTのi番目の文字が一致しているときです。この時は何にもしなくてもよいです。

 

まとめると、

SとTのi番目の文字を比較して、違う部分を数えればよいことになります。

for文でi=0からs.Lengthまで行い、s[i] != t[i]のとき、数を足せばよいです。

あとは普通に答えを出します。

 

A,B問題って確かに簡単ですが、要求を素直にきちんと実装できる能力がないとできないので、とても大事な問題だなあとやっぱ改めて思いますね。

 

最後に....

最後にABCの現状について思うことを言います。

少なくともABC程度のレベルだと競技としての要素は弱く、どちらかというと実務で役に立ちそうな、技術ばっかりです。

 

常に、D問題までを30-60分程度で解いて、レートが1200程度とれているレベルなら技術のアルゴリズムの側面では十分です。逆にこれだけあればどの企業でも困らないんじゃないかなと思っています。

 

なので、自分はここを目指すために、こうやっていろいろ思いながら振り返っています。

 

何かの参考になれば。

 

ではでは。