まだ緑(ABC142)
ABC142のネタバレ含みます!
問題はこちら. atcoder.jp
A 入力以下の数の中の奇数の割合。何故か奇数の際につまづいて微妙に時間をロスってしまう。しかも解説で場合分けはいらんやでと言われ往復ビンタ.
N = int(input()) if N % 2 == 0: print(0.5) else: print(0.5+(1/N)/2)
B めっちゃ素直なfor文。Aより速い説とか思って提出時間を見直すとほんまにAよりまあまあ速い。
N,K = map(int,input().split()) H = list(map(int,input().split())) ans = 0 for i in H: if i >= K: ans += 1 print(ans)
C 辞書かなあと思ったがよく考えるとソートの必要がありそうなので大丈夫か?と思ったがそこでソートできるのがPythonの良いところ。考え直すとリストで良い気が。Twitterで見たんですけどAtCoderでは空白刻みで出力は改行で提出しても良いらしい.実際に開業出力でオッケーだったのでたぶん大丈夫.
N = int(input()) A = list(map(int,input().split())) dict = {} for i in range(N): dict[A[i]] = i+1 sA = sorted(dict.items()) ans = [] for i in range(N): ans.append(sA[i][1]) print(*ans)
D 公約数の中で互いに素なやつをいっぱい選べとのこと。例を見ると最大公約数が大きくても答えは結構小さそう。ということで最大公約数の素因数分解をして個数を見る方法を思いつく。1を追加すべきなのと、22とかでも2を取り出すしかないため、使っている種類のみを見ることに。そこから一悶着あるのがこの問題だと思うのですが、以下のサイトで高速素因数分解の結果を返してくれる自作関数を発見。
返してくる形式に合わせようと思っていたが、種類のみでオーケーなのでlen()でいった。コードテスト中にAとBが互いに素だと上手くいかないことに気づいたが、何も考えつかなかったので例外処理して終了。時間が気になったが結構大丈夫だった。PyPyだと標準解TLEがあんまりないのか?(文字列操作とかはPython苦手らしいのでダメかもしれない.あとループぶん回すのとかも遅いとのこと)
import fractions A,B = map(int,input().split()) k = fractions.gcd(A,B) if k == 1: print(1) quit() def factorization(n): arr = [] temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr.append([i, cnt]) if temp!=1: arr.append([temp, 1]) if arr==[]: arr.append([n, 1]) return arr print(len(factorization(k))+1)
E なんかよくわからんのでとばしたが、Fをやっているうちに動的計画法と気づいてEにしとけば良かったかと後悔.
F 全くわからん有向グラフ。しかし問題文を見たところグラフに詳しくなくても解けそうな感じがしたので着手。隣接グラフを書けるようになって少し嬉しかった。
総評 パフォーマンスは1157。やっぱり緑。5分ほど速くすれば水色パフォーマンスになったようだがそれよりEかFを解きにいったほうが良いと思った。速解きで頑張るのは勉強を終えてからにしたい。運が良ければあと2回ほどで緑になるかも。この2週間蟻本開いていないので精進します.
Nimメモはここに移動しましたー> qiita.com
Twitterアカウントはこれー> twitter.com
茶色になった!(ABC141)
ABC141のネタバレあります!
富士通杯(将棋の全国大会)で主将やりながらAtCoderやってた三十三間党です.
問題はこちら→atcoder.jp
A.Weather Prediction
この町では晴れ,曇り,雨と天気が周期的に変化するらしい.雨多くて辛いね.if文使って書いた.3分くらい.
S = input() if S == "Sunny": print("Cloudy") elif S == "Cloudy": print("Rainy") else: print("Sunny")
B.Tap Dance
踊りやすさとは.for文を使って,偶数文字目にR,奇数文字目にLがあれば奇数があればbreakしてNo言ってexit,なかったらYesと言うように書きました.4分くらい.
S = input() for i in range(len(S)): if S[i] == "U" or S[i] == "D": continue if i % 2 == 0: if S[i] != "R": print("No") exit() else: if S[i] != "L": print("No") exit() print("Yes")
C.Attack Survival
一回正解すると他の皆の点が減っていくスタイル.つらいね.allとか使うわけにはいかないので,文面通りには書けないけど,他の人減点って正解者加点と一緒だよね.というわけで最初のKポイントから正解数Qを引いたリストを作ってから,for文で正解者にポイントを与えるように書きました.10分くらい.
N,K,Q = map(int,input().split()) A = [int(input()) for i in range(Q)] Li = [K-Q] * N for i in A: Li[i-1] += 1 for i in range(N): if Li[i] <= 0: print("No") else: print("Yes")
D.Powerful Discount Tickets
重ね掛け出来るタイプの半額券強すぎい.M<=105なので,O(NlogN)まで許されますね.ここで優先度付きキューの取り出しがO(logN)なのを思い出したので,for文の中で優先度付きキュー使えばO(NlogN)で済むなあと思いました.優先度付きキューで最大を取り出すために使ったマイナス×と,切り捨ての相性が悪くて思いついてから書くまで手こずりました.17分くらい.
import heapq,math N,M = map(int,input().split()) A = list(map(int,input().split())) H = [] w = 0 for i in A: heapq.heappush(H,-1*i) for i in range(M): w = (heapq.heappop(H))*-1 w //= 2 heapq.heappush(H,w*-1) print(-1*sum(H))
E.Who Says a Pun?
何も思いつかないので,Nimで愚直解一応書いておいたら意外とギリギリ通らないぐらい.Z-Algorithmというもので解けるらしい.このサイトによると以下のように書ける.
これをN回繰り返してO(N2)で解ける.と思いきや同じ文字を2回使っても良いように書いてるので題意に合わせて書き換えないといけませんでした.
F.Xor Sum 3
Xorわからんごー.階段の電気のスイッチの話聞いて便利だなーと思った.
qiita.com とりあえずこれで勉強してみた.
総評
パフォーマンスは1094でした!自己最高パフォーマンス更新しましたね.あと1問出来れば水色パフォいけそうなので頑張ります.新レートは472で,茶色になりました!初めてレート上昇で色が変わったので嬉しいですね!AtCoder過去問というよりは,蟻本を進めていこうと思います.
Nimメモはここに移動しましたー> qiita.com
Twitterアカウントはこれー> twitter.com
(ABC140)
ABC140のネタバレあります! 三十三間党です.
問題はこちら. atcoder.jp
A.Password
高橋くんが3桁パスワードを作る問題.ありがちな話ですが,(文字の種類)^(桁数)ですね.今回だとN3.しかし急ぎすぎてなぜかN2を出力する凡ミス.
import strutils,math var N = stdin.readline.parseint echo (N^3)
B.Buffet
料理をリストAの順番A[i]で食べ,満足度リストB[A[i]]番目の満足度を得,もしA[i]+1がA[i+1]なら,C[i]の満足度も得れる,という問題です.リストが実装出来ますか?という問題だと思います.
import strutils,sequtils,math var N = stdin.readline.parseint A = stdin.readline.split.map(parseint) B = stdin.readline.split.map(parseint) C = stdin.readline.split.map(parseint) ans = 0 ans += sum(B) for i in 0..<N-1: if A[i] + 1 == A[i+1]: ans += C[A[i]-1] echo ans
C.Maximal Value
問題文の意味を読み取るのに時間がかかりました.解き方はやっぱり例から入りました.どれだけ大きい数がBに入っていたとしても,連続しないと意味がないようなので,min(B[i],B[i+1])が思いつきました.それに+でBの最初と最後を足して完成です.
import sequtils,strutils,math,algorithm var N = stdin.readline.parseint B = stdin.readline.split.map(parseint) ans = 0 ans += B[0] ans += B[N-2] for i in 0..<N-2: ans += min(B[i],B[i+1]) echo ans
D.Face Produces Unhappiness
これもまた問題文で一瞬??となりました.てか解説文読んでもよくわからん.
総評
パフォーマンスは541.冴えねー.茶色レートにもならんし.やっぱりね,過去問でD解いてないやつがD解けるようになるわけないっすわ.というわけで過去問のDもやっていきたいと思います.あと蟻本のC++->Nim翻訳も進めていきたい.
Nimメモはここに移動しましたー> qiita.com
Twitterアカウントはこれー> twitter.com
悲しみのD(ABC139)
ABC139のネタバレ含みます!
学生選手権の当日イベントに参加できるかどうかのギリギリの順位らしく、ドキドキの三十三間党です。可能な限り、コンテストがあったその日の内に記事を更新したいと思います。
前からベッドがぶっ壊れてまして、その話をすると、本日実家から両親が来てくれてベッドの組み立てをやってくれました。僕も手伝ってはいたんですが、コンテストあると言ったら、組み立てとくからコンテストやり、とのことで。ありがとう両親。
問題URL
https://atcoder.jp/contests/abc139/tasks
A Tenki
文字列から天気予報が当たった回数を求めよっていう問題でしたね。for文とif文使って予報と実際が当たっているかを判定しました。なんかAにしては難しいようなイメージ。
var S = stdin.readline T = stdin.readline ans = 0 for i in 0..<len(S): if S[i] == T[i]: ans += 1 echo ans
B Power Socket
電源タップの問題。一人暮らししているので身近ですね。1個ならそのまま、2個以上ならB口ずつ増やしていきたいんですが、そのとき口を1個消費します。
import strutils,sequtils var a,b :int;(a,b) = stdin.readline.split.map(parseint) var count = 0 kuchi = 1 for i in 0..<b: if kuchi >= b: echo count quit() else: kuchi = kuchi - 1 + a count += 1
C Lower
右隣が非増加なら移れるよーという問題でした。前に1番長い単調非減少の数列は何個続く?という問題を解いたことがあったので一緒だなと思って解きました。
前から順番に見ていって、非増加ならカウンタを増やし、非増加でないなら、そこでansと比べて大きい方を取り、カウンタはリセット、という方法を取ったのですが、これだと最後の数列が評価されませんので、for文抜けてからもう一回評価しました。もっと良い書き方がありそうですね。
import strutils,sequtils var N = stdin.readline.parseint H = stdin.readline.split.map(parseint) ans = 0 count = 0 for i in 0..<N-1: if H[i] >= H[i+1]: count += 1 else: if count > ans: ans = count count = 0 if count > ans: ans = count count = 0 echo ans
D ModSum
1〜Nまでの数列を並べかえた数列でmodを取る問題。くそ悩みました。僕は例題を手を動かしながら考える派なのですが、いかんせん今回はNの並べかえということでNの階乗通りありますので、N=3もしくはN=4でギブなわけです。 制約を見てみますと1<=N<=109となっていますのでO(1)、入力Nの大きさによらない答えを出すしかありません。 なんか見た目数列の問題なんよなーとか思いつつ、2,1,4,3,6,5みたいな数列を考えたり偶奇で場合分けかなーとか考えていました。詰まったので順位でも確認するかと思ったら、なんとほとんどの人は解いています‼ぐえっ。 思っているより簡単な問題だと認識を改め、落ち着いて例を見直します.あれっ、N=13のとき78って、くそでかくね???急に気づきました。慌てて1〜13の和を計算すると、13(13+1)/2=91。78との差は…13やんけ!よく考えたらiのときi+1取ってi = NのときにN諦めたらええやん!ということでN(N+1)/2-N(=N*(N-1)/2)でええんか?入力例は…全部OK。じゃあもう提出や! ・・・
AC
なおこの時点で76分。本当にありがとうございました。
import strutils var N = stdin.readline.parseint echo (((N*(N+1)) div 2) - N)
終わってみればあっけない。
E League
無理そう。あざした。
F Engines
あー…ベクトルだわこれ。なんかしかも解けそう。とかABCFとかいうくそ順番でやったためDが76分提出とかなるんですよ。しかも解けてない。だめだめ。
パフォーマンスは680。ABCでは最高パフォーマンスだが、緑にしたい。次がその次ぐらいでRatingが茶色になるんじゃなかろうか。
あと今回は全Nimでしたが、Python(もしくはC++?)も混ぜて、書きやすいやつで書こうかなとは思っています。
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桁の数が0になるため積の日はなく,0を出力して終了します. で,それ以外ならfor文二重に回して,mod10で位の数を取り出していきます.
B-Kleene Inversion 与えられた整数列AをK回繰り返した整数列をBとして,Bの転倒数109+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で書くことにしようと思います.
はじめてのNim(Nim初心者によるAtcoder精選過去問10問)
どーも三十三間党です。皆さんNimという言語をご存知でしょうか。
Nimは爆速で動くPythonです。嘘です。
なないろ言語で競プロまとめ(https://qiita.com/drken/items/6edb1c0542d4c3b7179c)を見ながら、C++ばりの速さが出て、Pythonみたいな書き方できる言語ないかなーと探していたら、2つほど候補が見つかりました。CrystalとNimです。しかしコードを見ていると、やはりCrystalはRubyをリスペクトされて書かれた言語なので、Rubyを学んだことのない僕には少し読みづらかったです。
そこでNimのコードを見るとあらびっくり、これPythonじゃね?と思うほど個人的にはコードが似ていたので,勉強しようと思いました。
今回はそのNimを使って、「AtCoderに登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~」
(https://qiita.com/drken/items/fd4e5e3630d0f5859067)
を解きました。一応Pythonで一回解いたことはあります。
なお、ACしているので、動くコードとは思いますが、Nim初心者(というかAtCoderも初心者)なので冗長だったり、間違った文章を書いたりしている等あると思います。ご了承願います。
今回からはMarkdown方式で書いているので、コードの見づらさは多少改善されているかと思います。
Nimならこういう書き方良いよ!っていうのがあれば教えてください!
1.Welcome to AtCoder
import sequtils, strutils var a = parseInt(readline(stdin)) bc = map(split(readline(stdin)),parseInt) s = readline(stdin) echo (a+bc[0]+bc[1]," ",s
標準入力の()多いかな〜と思いましたが、まあpythonでもこんなもんですよね。空白区切りの標準入力はimport要るんですね。stdinはstandard inputの略か。変数宣言に型は必須ではありませんが、変数の場合varは必須そう。
リストで受け取ってしまいましたが、
var a, b, c: int (a, b, c) = stdin.readLine.split.map(parseInt) という分割代入の方法もあるそうな。
2.Product
import sequtils,strutils var ab = map(split(readline(stdin)),parseInt)<200b> if (ab[0] * ab[1]) mod 2 == 0: echo "Even" else: echo "Odd"
%ではなくてmod。ifの書き方Pythonと一緒ですね。
3.Placing Marble
var S = stdin.readLine var c = 0 for s in S: if s == '1': c += 1 echo c
for s in S(文字列)という書き方もできちゃう。ちなみに文字列はmutableだそうで。
4.Shift Only
import strutils import sequtils var N = stdin.readline.parseint A = stdin.readline.split.map(parseint) ans = 0 block myblock: while true: for i in 0..N-1: if A[i] mod 2 != 0: break myblock A[i] = int(A[i]/2) ans += 1 echo ans
なんか急に標準入力受け取る書き方変えてしまいました(やってることはおそらく同じですが)。なんか()の部分を.で書き換えられる?らしい。
block文が個人的には新しい。最初に自分でblockを作っておくと、breakでどのblockから抜けるか選べます。多重ループ 抜け方 でググることもなくなりますね。
while文も書き方同じですが、Trueではなくてtrueですね。ちなみにNimは大文字小文字を区別しないようですが、最初の一文字目だけ区別するようです。
for文の中の、0..N-1という書き方で、Pythonのrange(N)と同じみたい。
/は何があろうとfloat型返すらしく、int型に変換しないと元の変数に代入することができません。そんなもんか。
2進法に書き換えて云々で解きたかったのですが2進数への書き換えが意外と面倒くさい?のかも
5.Coins
import strutils var A = stdin.readline.parseint B = stdin.readline.parseint C = stdin.readline.parseint X = stdin.readline.parseint ans = 0 for a in 0..A: for b in 0..B: for c in 0..C: if 500*a + 100*b + 50*c == X: inc(ans) echo ans
ans += 1はinc(ans)でもおっけー。今まで全部実行時間1msですね。
6.Some Sums
import sequtils, strutils, math var N,A,B:int ans = 0 (N,A,B) = stdin.readline.split.map(parseint) for i in 1..N: var c = 0 x = i while x > 0: c += x mod 10 x = int(x/10) if A <= c and c <= B: ans += i echo ans
気づいてませんでしたが、
import ho import ge
を
import ho, ge
という書き方もできるようです。
Pythonで書いていたときは文字列リストに変換してから整数に変換し、その和を取るという解き方をしていたので、その書き方をしようとしたら思った以上に面倒くさかったのでやめました。型を変えずに処理できるときはそうしたほうが良さそうかも。
7.Card Game for Two
import strutils import sequtils import algorithm proc getInt() : int = parseInt(readLine(stdin)) proc getInts() : seq[int] = readLine(stdin).split().map(parseInt) var n = getInt() a = getInts() ans = 0 a.sort(cmp,Descending) for i in 0..<n: if i mod 2 == 0: ans += a[i] else: ans -= a[i] echo ans
標準入力長いなーと思っていたら(普通の長さかもしれませんが)、関数にしてまとめている方がいらっしゃったので真似させていただきました。
sortのDescendingで降順に並べ替えて(引数cmpはよくわかりませんでした)解きました。
8.Kagami Mochi
import strutils import sequtils import sets proc getInt() : int = parseInt(readLine(stdin)) var n = getInt() d = initset[int](8) for i in 1..n: d.incl(getInt()) echo d.card
集合の要素数を数えます。initsetintで2の冪乗サイズの整数型が入る集合になるようです。
9.Otoshidama
import strutils import sequtils var ny = stdin.readline.split.map(parseint) n = ny[0] y = ny[1] block myblock: for i in 0..n: for j in 0..n-i: if i * 10000 + j * 5000 + (n-i-j) * 1000 == y : echo (i," ",j," ",n-i-j) break myblock echo("-1 -1 -1") 実行時間が3msになりました。
個人的には3重ループ間に合わねーぜ!っていう問題だと思っていたのですが、
import strutils import sequtils var ny = stdin.readline.split.map(parseint) n = ny[0] y = ny[1] block myblock: for i in 0..n: for j in 0..n-i: for k in 0..n-i-j: if i * 10000 + j * 5000 + k * 1000 == y and i+j+k == n: echo (i," ",j," ",k) break myblock echo("-1 -1 -1") 3重ループ間に合っちゃった……(実行時間905ms)速さは正義。
10.白昼夢/Daydream
import strutils,unicode var s = readline(stdin) words = ["eraser","dreamer","erase","dream"] while true: for word in words: removesuffix(s,word) if s == "": echo "YES" break else: if not endswith(s,words[0]) and not endswith(s,words[1]) and not endswith(s,words[2]) and not endswith(s,words[3]): echo "NO" break
速え(当社比、実行時間3ms)。文字列操作強力ですね!
11.Traveling
import strutils,sequtils var N = stdin.readline.parseint for i in 1..N: var t,x,y:int (t,x,y) = stdin.readline.split.map(parseInt) if x + y > t or (((x+y) mod 2) != (t mod 2)): echo "No" quit() echo "Yes"
実行時間59msと最長の結果になったのですが、他の人の提出結果も見たところ、こんなもんかと思われますが,Nimの最速は11msでした。
感想 速い、Pythonっぽい、好き(小並感)
ABC138
ABC138のネタバレ含みます!
昨日のAGCでぼこぼこのぼこにやられた三十三間党です.ABC138の振り返りをしていきます.
A問題
入力の数値によってprintを変えるifが使えるか問題ですが焦りすぎて””を忘れてRE(PythonのためCEがないです)を出してしまう凡ミス.
B問題
逆数の和の逆数を出す問題.真面目にfor文を回して終了.
C問題
見た瞬間「結構すぐ解けそう!」と思い最初の5分ペナルティが痛いことが予想されました.入力例を見て,小さい順に合成すれば良くね?と思いましたが,確信が持てなかったので数直線に並べて考えました.まあやっぱり小さい順に並べて合成するんですが.
D問題
木やグラフの構造について全然知らなかったので,問題文・入力例の把握に時間がかかりました.蟻本を見ながら付け焼刃で理解しました.しかし肝心の実装のところでグラフ構造を実装できなかったうえ,方針も間違っていました(部分木のリストを作ろうとしてたが,親ノードのリストを作らないといけなかった).やはり勉強不足感を感じ,夏休み中に蟻本を進めていこうと思いました.
また,解答例の注釈に,『このあたりの問題から,言語によっては「正しい」解法でも実行時間制限がきわどいかもしれません』と書かれていて,やはりコンパイラ型言語で書くべきかなと思いました.前に書いたAPG4bも全部終わったので,C++かなにかで書こうかと思います(なないろ言語で精選過去問10選を解くというサイト(https://qiita.com/drken/items/6edb1c0542d4c3b7179c)を見て,Crystalの文法に感動したので個人的には,勉強したうえでCrystalで書きたい).
E問題
個人的に解けるかどうかという問題が来たときにその後の問題も一応全部確認することにしています.D問題を見たときにE問題も見たのですが,「グラフもあんまり知らんしE問題のほうが簡単か?」と思ったのですが,やっぱり実装しようとするとなかなかに難しく,断念しました.
F問題
問題文読んで諦めました.XORに対する知識なさすぎい.
総括
・C問題初めてコンテスト中に解けて嬉しかった.
・Cが簡単なときはDも解きたい.
・グラフよく知らんし勉強しよう.
・C++の長いコードが苦手なのでPythonっぽく書けるコンパイラ型言語を勉強して(Crystal?)それで書きたい.
(追記)
なないろ見直したけどCrystalも良いがNimも魅力的.書いてみたい.