AtCoder最強学生戦

第一回日本最強プログラマー学生選手権‐予選‐のネタバレを含みます．

https://atcoder.jp/contests/jsc2019-qual/tasks

A-Takahashi Calendar

今日は珍しい積の日（8＝2＊4）らしく，それに関する問題でした．この問題では，与えられた月と日から高橋暦を作り，そのときの積の日の回数を数えよ，という問題でした． コードは以下の通り．

M, D = map(int,input().split())
ans = 0
if D < 10:
  print(ans)
  exit()
for i in range(1,M+1):
  for j in range(10,D+1):
    if i == (j % 10) * ((j//10) % 10) and (j % 10) != 1 and ((j//10) % 10) != 1:
      ans += 1
print(ans)

まず，Dが1桁なら，2桁の数が０になるため積の日はなく，０を出力して終了します． で，それ以外ならfor文二重に回して，mod10で位の数を取り出していきます．

B-Kleene Inversion 与えられた整数列AをK回繰り返した整数列をBとして，Bの転倒数10⁹＋7で割った余りを出力しろとのこと．ここでいう転倒数とは，整数の順序対（i,j）(0<=i<j<K*N-1)であってBi>Bjを満たすもの，らしいです． コードは以下の通り．

N, K =map(int,input().split())
A = list(map(int,input().split()))
A2 = A*2
ans = 0
tento = 0
ibitsu = 0
for i in range(len(A)):
  for j in range(i,len(A)):
    if A[i] > A[j]:
      ans += 1
for i in range(len(A2)):
  for j in range(i,len(A2)):
    if A2[i] > A2[j]:
      ibitsu += 1
#print(ibitsu,ans)
ibitsu -= ans*2
#print(ibitsu)
ibitsu = ibitsu * K*(K-1)//2
#print(ibitsu)
ans *= K
ans += ibitsu
print(ans % (10**9+7))

最初の二重ループでは左から右の転倒数を数えて，ansに入れています．

2つ目の二重ループは意味わからないと思いますが，Aを二回繰り返したものをA2とし，そこでカウントした転倒数にibitsuと名付け（だって図描いてるとき歪やってんもん），そこからans*2を引いています．ほんまネーミングセンス0やな自分．

そして，ibitsuのほうは1からK-1までの総和をかけて（内部だからね），ansのほうには繰り返し数K（辺だからね）をかけて両方の和が答えとなります．

PyPy3で書くと300msほどかかったので，Nimだとどれくらいかなと思い，Nimで書き直すと思ったよりオーバーフローに困りました．Pythonだとオーバーフローを考える必要がないので． まあしかしNimだと8msくらいだったので，やっぱり速いなと思いました．

パフォーマンスは914でした．

感想

自分的には初の緑パフォーマンスで，上々の出来でした．なかなかにCの意味・解き方がわからなかったので，これより上は少し遠いのかな，と思いました．

また，本番になるとPythonに頼ってしまう（というか過去問解きのときからそう）ので，AtCoderにおけるPython を一時封印して，Nimで書くことにしようと思います．