LoginSignup
0
1

More than 3 years have passed since last update.

いろはちゃんコンテスト Day1 解説 (Iまで)

Last updated at Posted at 2019-05-01

カイルダイアリー(テキトー)

いろはちゃんコンテスト Day1の解説&反省です。
使用言語はpython。

A - 一問目

それはそう

print(input()[0])

B - ローリング・老人と海

削除系はエラー出やすいのでひやひや、popのがいいかも。

s=list(input())
t=int(input())
for i in range(t):
    s+=s[0]
    del s[0]
print("".join(s))

C - Halcyon

はい。

n=int(input())
for i in range(n-7,n+1):
    print(i)

D - 肉と肉のぶつかり合い

貪欲に、デバッグ用コードコメントアウト忘れてワンペナ。

n,x,y,*a=map(int,open(0).read().split())
for i in range(n):
    x+=max(a)
    a.remove(max(a))
    if len(a)==0:
        break
    y+=max(a)
    a.remove(max(a))
    if len(a)==0:
        break
if x>y:
    print("Takahashi")
elif y>x:
    print("Aoki")
else:
    print("Draw")

E - 放課後

これはちょっとひねってあって実力で二ペナ、最初にforで愚直にシミュレーションしたがNが10^18でMLE。
記念日と記念日の間の日々を出して、最初と最後の記念日は0日とn+1日で対応、あとはa日以上普通の日を過ごしてはいけないのだから(普通の日々)//a*(a-1)+(普通の日々)%a


n,a,b,*d=map(int,open(0).read().split())
d=[0]+sorted(d)+[n+1]
print(sum((d[i+1]-d[i]-1)//a*(a-1) + (d[i+1]-d[i]-1)%a for i in range(b+1)))

F - Head of The Dragon

どうやらこれはAから通して11分で全参加者中12番目に提出したらしい、素因数分解してkより短かったら-1、そうじゃなかったら後ろからかけていくだけ。

a,k=map(int,input().split())
def factorize(n):   #二から回せ
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b += 1
    if n > 1:
        fct.append(n)
    if len(fct)==0:
        fct.append(1)
    return fct

x=factorize(a)
if len(x)<k:
    print(-1)
else:
    while len(x)>k:
        x[-2]=x[-1]*x[-2]
        del x[-1]
    print(*x)

G - 友達以上恋人以下

本番では解けずに写経AC、前回のkの範囲でリストを参照するの天才すぎる。右方向に更新されるのは(k-1)*m回であるから、もし足りなければ最後の方は更新されずに-1のままとなる。天才。
iroha G.png

n,m,k,*a=map(int,open(0).read().split())
dp=[[-1]*(n+1)for i in range(m+1)]
dp[0][0]=0
for i in range(1,m+1):
    for j in range(1,n+1):
        preMAX=max(dp[i-1][max(0,j-k):j])
        if preMAX>=0:
            dp[i][j]=preMAX+a[j-1]
print(max(dp[-1][-k:]))

H - ちらし寿司

これはほかの人のコードに比べてもんじゃっぽいのであんまり参考にしない方がいいかも(
まず、実験して「桁和%9の文字+桁和//9*(文字の9)」が最小っぽいことが判明、ところがこれで半分くらいのコーナーケースに引っかかる。これで5ペナ、よ~くみたらX!=Nって書いてありました(ブチギレ)。なので入力=出力だったら、9999→18999にしてやればよしこれも場合分けでまあまあめんどくさい、追加で3ペナ。何言ってるかわかんね~って人はwikipediaの桁和を見るといいかも。

from collections import*
d=defaultdict(int)

for i in range(30):
    for j in range(1,10):
        x=str(j)+i*"9"
        d[sum(map(int,x))]=x
s=input()
t=d[sum(map(int,s))]
if t==s:
    if len(s)==1:
        print("1"+str(int(s[-1])-1))
    else:
        b=int(s[0])+1
        if b==10:
            b="1"
            print(b+str(int(s[1])-1)+"9"+s[2:])
        else:
            b=str(b)
            print(b+str(int(s[1])-1)+s[2:])
else:
    print(t)

I - リスのお仕事

いわゆる拡張ダイクストラというやつで、そこまでの状態を保持している改造されたダイクストラ法。
ダイクストラ法自体が変わっているわけじゃないので、呼び方に派閥争いがあるとかないとか。私は改造ダイクストラと呼びます。

from collections import*
from heapq import*

def CUSTOMIZED_DIJKSTRA(point,d):
    cost=[-1 for i in range(n)]
    visted=[0 for i in range(n)]
    Q=[]
    cost[point]=0
    visted[point]=1
    for aft,c in d[point]:
        heappush(Q,(0,aft,c)) #カウント、次の点、隙間
    while Q:
        count,aft,c=heappop(Q)
        if not visted[aft]:
            visted[aft]=1
            cost[aft]=count
            for aftaft,c2 in d[aft]:
                if not visted[aftaft]:
                    if c!=c2:
                        heappush(Q,(count+1,aftaft,c2))
                    else:
                        heappush(Q,(count,aftaft,c2))
    return cost
n,m,k=map(int,input().split())
d=defaultdict(list)

for i in range(m):
    a,b,c=map(int,input().split())
    d[a-1].append([b-1,c])
    d[b-1].append([a-1,c])
x=CUSTOMED_DIJKSTRA(0,d)
if x[n-1]==-1:
    print(-1)
else:
    print((x[n-1]+1)*k)

J~ 解けない(ごめんね!)

カイルの力量不足です!お近くの青コーダー以上にお聞きください!では!

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1