AtCoder Beginner Contest 179

参加記 atcoder

はい。
AtCoder Beginner Contest 179
ooox-- 826(-9) 茶色がかなり現実的に。

A - Not

PyPy3

s=input()
print(s+"es" if s[-1]=="s" else s+"s")

末尾を見て判定。

B - Go to Jail

PyPy3

n=int(input())
ans=chk=0
for i in range(n):
    a,b=map(int,input().split())
    if a==b: chk+=1
    else: chk=0
    ans=max(ans,chk)
 
print("Yes" if ans>2 else "No")

ゾロ目チェックして回数を数える。

C - Ubiquity

C++

#include<bits/stdc++.h>
using namespace std;
 
#define sl1(a)  scanf("%lld",&a)
 
int main(){
    long long n,ans=0ll;
    sl1(n);
    for (long long  i=1;i<=n;i++)  ans+=(n-1)/i;
    printf("%lld\n",ans);
    return 0;
}

解説見た後ならシンプルになるのですが、コンテスト中はA×Bを2重ループで見てました。制約が緩くて助かりました。
サンプル2で見てみると、i=1のときには(100-1)/1は99です。1×1+99...1×99+1まで成立するからです。i=2のときには(100-1)/2は49です。2×1+98...1×49+2まで成立するからです。
なので1からN-1までだけ調べれば解になります。

D - Leaping Tak

PyPy3

mod=998244353
w=[]
dp=[0]*200005
ds=[0]*200005
dp[1]=1
ds[1]=1
n,k=map(int,input().split())
for i in range(k):
    a,b=map(int,input().split())
    w.append((a,b))
 
for i in range(2,n+1):
    for j,k in w:
        li=i-k
        ri=i-j
        if ri<0: continue
        li=max(li,1)
        dp[i]+=ds[ri]-ds[li-1];
        dp[i]%=mod
    ds[i]=ds[i-1]+dp[i]
    ds[i]%=mod
 
print(dp[n])

コンテスト中はAC出来ませんでした。計算量無視で配るDPしたのでそれは仕方ないです。
サンプル4で考えてみます。
TLEした配るDPは移動全パターンをぐるぐる回すので1マス目から移動するのには、
[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1]
になります。1マス目から2マス目に移動できるパターン数は1マス目+2マス目になります。今見ているマスから移動可能なマスに加算するので配るDP。K個ある移動区間l,rをぐるぐるしていたらTLEでした。

解説の貰うDP+累積和はiマス目に移動できるパターン数はiマス目-rマス目からiマス目-lマス目の区間のパターンの累積和で求められる、という感じのようです。よく理解していないし、言語化も出来ません。

E - Sequence Sum

PyPy3

n,x,m=map(int,input().split())
 
f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
p=x
for i in range(m+1):
    if i!=0: p=p*p%m
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

コンテスト中はAC出来ませんでした。脳が数式を拒否しました。
問題の内容を X1%M, X2%M, X4%M... の総和を求める問題だと解釈してしまいました。
そこから考えた処理で pow(X, 2, M) などとしていて数が大きくなったときにTLEしていました。
X同士を掛け算し続ければ何番目の時にXの何乗かをpowを使って計算ということは必要ありませんでした。

が全てです。
Mで剰余を取っているので現れる数は0からM-1の範囲です。最悪でも100,000回くらいで同じ数が出ます。そこからは出現する数はループします。
なので先頭部分、ループ部分、端数部分をよしなに計算すると解になるはずです。