AtCoderわからん日記_3 ABC149C,D

はじめに

　ABC149も参加してきました。Unratedになっちゃったけど。
　愚かなのでA問題で問題文を読み違えてミスしちゃったりしました。あと、B問題で結果を得るのではなく文字通りの操作をやろうとして、計算量のことを思い出して慌てて方向性の調整をしたりして、前回前々回やったことが少しだけ生きている……気がします。
　Qiita、この日記をテンプレート化したいんだけどどうしたらいいんだろう。それこそプログラミングでなにがしかのコードを組めばいいのか。わざわざエディタ開いてなんかするよりメモ帳に貼ってコピペしたほうが早いんじゃないかな。こうやって楽しようとしてよりめんどくさいことをする人、プログラマに多い気がする。偏見です。

C - Next Prime

X以上の素数のうち、最小のものを求めよ。

考えたこと

①素数の間隔がどのぐらいあるのか（平均で10ちょっとらしい）
②もう地道に割っていくしかないんじゃないか
③TLEこわい
この問題文シンプルでいいですね。
ルジャンドル予想とか使えないかなと思ったけど別にいらなかった。

1回目

1回目というか通ったので1回しかない

import math
n=int(input())
#ループを奇数から始める
if n % 2 == 0 and n != 2:
        n += 1
#余裕を持って20回試行
while n <= n + 20:
    i=3
    #平方根より小さい奇数のiで割り続ける
    while i <= math.sqrt(n):
        #割れたら次のn
        if n % i == 0:
            break
        #割れなかったら次のi
        else:
            i += 2
    #全部割れなかったらそれが答えなので終わる
    if i >= math.sqrt(n):
        print(n)
        break
    else:
        n+=2

通りました。う～ん。もっといいやり方があるとは思うけれども……。

if i >= math.sqrt(n):

しかし、やりかたというか、これすごくダサい気がする。ループをbreakせずにやり遂げた時の判定をどうしたらいいのかと思ってこうしたんだけれど、同じことをやるにしてもなんかもっといい方法がある気がする……。
それと、素数について、10⁵レベルならだいたい20もあれば十分だろう、という仮定で20回のループにしたけど、こういうのっていいのかなあ……。

強人（つよびと）の解答

• 平方根、math入れなくても**0.5でいい
• 地道に1ずつ増やしながら割っていくだけ

　意外と普通の総当たり作業だった。
　そもそもそんなに多くない回数で終わることがわかっているのでwhile文によるiの大きさの定義っていらないし、for文のほうを使うべきだったな。同様にwhile二回も使わなくてよかったな。
　前回前々回でTLEになりまくったこともあり、負荷をかけないように奇数だけで割るとか工夫したけれど、意外となくてもいけるんだなと思いました。このへんの計算量のおおよそな予想ができると加減がわかるんだろうな。しかし、それのおかげかわからないけれど実行時間は速かったです。また、割る範囲を平方根にしている人があまりいなかったな。しかし、競技プログラミングはいかに速くコードを書くかのところが強いから、そこまで計算量が多くなければなくてもいいのだけれど。でもだいぶ減るんじゃないかな、どうかな。

　みんなの提出を見ているといいコードってなんなのかなあと考えます。もちろんわかりやすくて早くて短いのがいいんだろうけれど、それらのバランスが難しいですね。一行で終わってるコード書いても可読性は低いし、早くてもこんな冗長なコードはよくないし。

忘れないうちにDも書こう。

D - Prediction and Restriction

高橋君は、ゲームセンターで「じゃんけんバトル」というゲームをプレイすることにしました。このゲームのルールは以下の通りです。

• プレイヤーは筐体とN回じゃんけんを行う (あいこの場合も1回のジャンケンと数える)。
• プレイヤーがじゃんけんで勝った場合、プレイヤーは出した手に応じて以下のスコアを得る (あいこや負けは0点)。
  • グーで勝った場合、R点
  • チョキで勝った場合、S点
  • パーで勝った場合、P点

ただし、ちょうどK回前のじゃんけんで出した手と同じ手を出すことはできない。(K回目までのじゃんけんでは好きな手を出せる。)
筐体は、各回のジャンケンで出す手をゲーム開始前に決定します。能力者である高橋君は、ゲーム開始前にこれをすべて読み取りました。
高橋君が読み取った情報は文字列Tとして与えられます。Tの i(1≤i≤N)文字目がrのときはi回目のじゃんけんで筐体がグーを出すことを、sのときはチョキを出すことを、pのときはパーを出すことを表します。
高橋君がN回のじゃんけんで出す手を最適に選んだとき、ゲーム終了までに最大で合計何点を得られるでしょうか。

考えたこと

①k回後に被るときはあいこか負けなのでカウントしない
②カウントしない文字を置換して、最後に有効なじゃんけんの数を数える
AtCorderには能力者が多いね。全員集めてバトルさせたいな。

1回目

n,k = map(int,input().split())
r,s,p = map(int,input().split())
st = input()
for i in range(len(st)-k):
    if st[i] == st[i + k]:
        st = st[:i + k]+ 'no' + st[i + k + 1:]
win = r*st.count('s') + s*st.count('p') + p*st.count('r')
print(win)

通りました。文字列って置換できないからスライスで切ってつないだんだけど、う～む。つかlen(st)て。nあるじゃん。

強人（つよびと）の解答

• 普通にリストで受け取って置換すればよい

ほかはだいたい同じでした。文字列にしたせいか実行時間がむっちゃ長い。試しにリストでやったら598msが47msになりました。愚かなり。
良くないところもあるけどD意外とできたな。時間内には出来てないけど。これからも頑張っていきたいです。