プログラミング初心者でもとりあえず練習で競技プログラミング(AtCoder)に参加してみようという記事を以前書きましたが、とはいえ競プロの敷居は依然として高く感じられると思います。
なので、これからは同じ初心者の私がAtCoderに参加してどんな風に問題を解いているかということを私自身のアウトプットのためにも書いていこうと思います。
そして何より、「こんなレベルでも大丈夫なのか」と皆さんにぜひ思っていただくのが目的なのでカッコつけずにダサい方法での回答をどんどん載せていこうと思います。
余談ですが外出自粛期間だからいいものの、休日夜に一人でパソコンに向かっていると悲しくなってきちゃいますね。
現状の私の状態
ちなみに現在の私はAtCoderを4月からとりあえず始めてみて、ABCのコンテストだけ出てアルゴリズムの勉強は特にしないという状態です。
言語はPythonを使っていますが特に理由はありません。強い人達が使っているC++がかけないからです笑
レートは茶色コーダー(下から２番目)です。レートに関してはchokudai山のブログに記載されている内容を引用させていただきました。
| 灰 | 参加すれば誰でもなれるので意欲以外の保証はなし |
| 茶 | 学生なら優秀だがエンジニアとしてはちょっと物足りない。派遣とかで来たエンジニアが茶色あれば一安心。 |
| 緑 | 緑あれば大抵の企業でアルゴリズム力は十分。他社評価サイトなら最高評価。 |
| 水色 | 基礎的なアルゴリズム処理能力については疑いのないレベル。 |
| 青 | 一部上場のIT企業でも、一人もいないことが結構あるレベルになる。 |
| 黄 | 化け物。競プロの問題を解く機械だと思っておけば良い。 |
| 橙 | あたまおかしい。 |
| 赤 | もうなんか世界大会とかに招待されたりする。 |
特に勉強をしているわけではないので緑に行ければラッキーくらいですかね。茶色はコンテストに参加してれば取れるので一つのマイルストーンしてみてもいいかもしれません。
ABC174の問題
今回は8/2(日)の21時から行われたABC174の問題について見ていきます。現状の実力だと毎回D問題を回答できるできないレベルなのでこちらでもひとまずD問題までの紹介とします。
A問題
Aは問題ないですね。入力される数値が30以上かどうかを判定するだけです。
コードは下のように書きました。print文を1行で書く方法もありますが、その手法はD問題で書きました。
X = int(input())
if 30<= X:
print('Yes')
else:
print('No')B問題
Bも大丈夫ですね。与えられる座標と原点の距離を求めてDと比較すればいいだけの問題です。距離の求め方も説明をつけてくれているので万が一忘れても回答可能です。
一つ工夫としては距離の比較の際にルート(sqrt)を使用したくなかったので距離の2乗どうしを比較しました。
N, D = map(int, input().split())
cnt = 0
for i in range(N):
X, Y = map(int, input().split())
d2 = X**2 + Y**2
if d2 <= D**2:
cnt += 1
print(cnt)C問題
Cになると難易度が上がりますね。とりあえず最初は頭悪く77…をひたすらKで割って割り切れるか確かめるという方法を試しましたが、すぐに割る数の桁が大きくなるので計算できなくなってしまいます。
ということで少し頭使いましょう。数列は初項が7で$a_n = 10a_{n-1} + 7$の数列とみなせるため、数列の各項をKで割った余り$q$も$q_n = 10q_{n-1} + 7$の数列となるはずです。余りは高々K-1なのでこちらは何回計算しても問題ないでしょう。
Kで割り切れるというのはKで割った余りが0ということなので、何番目に余りが0になるかを計算していきます。
ただし、Kが偶数と5の倍数の場合は絶対に割り切れないので除外しています。それ以外の数では必ず割り切れる場合があると言い切れるのはちょっとした証明が必要な気もしますが正解してしまったので省略ということにします。
K = int(input())
if K % 2 == 0 or K % 5 == 0:
print('-1')
exit()
A = 0
for i in range(K):
A = (10 * A + 7) % K
if A == 0:
print(i+1)
breakD問題
今回のD問題はいつになく回答が短く済む問題でした。これは難しく考えすぎないほうがいいですね、要は全ての操作が終わったら右側に白い石、左側に赤い石が配置されることになります。
ということは、赤い石があった場合その石より左側の白い石と交換すればいいことになります。つまり操作の回数は一番右側にある赤い石より左側にある白い石の個数分ということになりますね。
ただし、全て白、全て赤の場合は例外として処理が必要です。ということで下のように珍しくとてもシンプルに回答することができました。
N = int(input())
c = input()
numR = c.count('R')
print(0 if numR == 0 or numR == len(c) else c[:numR].count('W'))以上この程度のレベルですが、初心者の方にもなんとかなると思ってもらえたら幸いです。回答は全て私のgitHubに載せてありますので必要があればご覧ください。
コメント