この記事は, Muroran Institute of Technology Advent Calendar 2019 1日目 の記事です．
- はじめに
- ABC086A - Product
- ABC081A - Placing Marbles
- ABC081B - Shift only
- ABC087B - Coins
- ABC083B - Some Sums
- ABC088B - Card Game for Two
- ABC085B - Kagami Mochi
- ABC085C - Otoshidama
- ABC049C - 白昼夢 / Daydream
- ABC086C - Traveling
- おわりに
はじめに
「AtCoderに登録したら解くべき精選過去問10問を〇〇で解いてみた」シリーズです．このシリーズは色々な言語で挑戦するのが主流のようですが，今回は少し趣向を変えてワンライナーで全ての問題を解いていこうと思います．
言語はPython2を使います．理由は以下の通りです．
- 内包記法で遊びたかった
- 比較的無茶な書き方，処理をしても問題なく通る
- Python3で標準から消えたreduceを標準で使える
ワンライナーではimportが出来ないので，Python3ではreduceを使うことが出来ません．ほとんどの問題がreduceなしでは解けなかったので，今回は渋々Python2での挑戦となります．
ABC086A - Product
atcoder.jp
二つの正整数a,bの積が偶数か奇数か判定する問題．
2数の積の偶奇は2数それぞれの偶奇に依存するため，a,bそれぞれの偶奇を求めて積の偶奇を判定する．
print("Even" if reduce(lambda a, b: False if a&1 and b&1 else True, map(int, raw_input().split(" "))) else "Odd")
# 改行有 print("Even" if reduce( lambda a, b: False if a&1 and b&1 else True, map(int, raw_input().split(" ")) ) else "Odd" )
ABC081A - Placing Marbles
atcoder.jp
文字列中に含まれる'1'の数を数える問題．
countを使って文字列中の'1'の数を数える．
print(raw_input().count('1'))
ABC081B - Shift only
atcoder.jp
与えられた数字の中で2で割ることが出来る回数の最小値を求める問題．
logやfor文を使えないため，内包記法により2で割り続けた数のリストを生成し，条件を満たす値を数えることで2で割れる回数を求める．
入力の個数を表す値は使用しないが入力としては受け取らなけばならないため，val = (input | val) & val と変更することで強引に組み込んだ．
print(min( map(lambda x: reduce(lambda a,b: a + (0 if (b&1 or b==0 or x%b>0) else 1), [0]+[x>>t for t in range(35)]), map(int, [(input()|1<<35)&1<<35]+raw_input().split(" ")))))
# 改行有 print(min( map(lambda x: reduce(lambda a,b: a + (0 if (b&1 or b==0 or x%b>0) else 1), [0]+[x>>t for t in range(35)] ), map(int, [(input()|1<<35)&1<<35]+raw_input().split(" ")) ) ))
ABC087B - Coins
atcoder.jp
以下の式を満たすの組の数を求める問題．
全探索で十分だが，入力を変数に格納できない上に式評価の関係で内包記法による解候補の全列挙もできない．それぞれの入力に対してリストを生成し，reduceによって積を導出することで全列挙を実現する．
リストの先頭に(x，解の個数)を追加し，((x，解の個数)，現在の評価解)をセットとしてreduceで走査する．入力順序の関係で先頭にxを追加することはできないため，後ろに挿入してreverseした．
print(reduce(lambda x, y: [x[0], x[1] + (1 if 500*y[0]+100*y[1]+50*y[2] == x[0] else 0)], list(reversed(reduce(lambda x, y: [i+[j] for i in x for j in y], [[[i] for i in range(input()+1)], [i for i in range(input()+1)], [i for i in range(input()+1)]])+ [[input(), 0]])))[1])
# 改行有 print(reduce(lambda x, y: [ x[0], x[1] + (1 if 500*y[0]+100*y[1]+50*y[2] == x[0] else 0) ], list(reversed(reduce(lambda x, y: [i+[j] for i in x for j in y], [[[i] for i in range(input()+1)], [i for i in range(input()+1)], [i for i in range(input()+1)]] )+ [[input(), 0]])) )[1])
ABC083B - Some Sums
atcoder.jp
各桁の和がA以上B以下であるものの総和を求める問題．
全探索で十分間に合うが，入力が1行でまとめられていることに注意が必要．1行ずつ読み込むpythonでは，変数を使わない場合1行の入力をリストとして使わざるを得ない．変数を個別に扱うため，enumerateにより各変数にラベルを付与してreduceで強引に場合分け出来るようにした．
print(sum(reduce(lambda x, y: filter(lambda t: (t%10)+ ((t/10)%10)+ ((t/100)%10)+ ((t/1000)%10)+ ((t/10000)%10) >= y[1], [i for i in range(x[1]+1)]) if x[0] == -2 else filter(lambda t: (t%10)+ ((t/10)%10)+ ((t/100)%10)+ ((t/1000)%10)+ ((t/10000)%10) <= y[1], x), list(map(lambda x: [x[0]-2, x[1]], enumerate(map(int, raw_input().split(" "))))))))
# 改行有 print(sum( reduce(lambda x,y: filter(lambda t: (t%10)+ ((t/10)%10)+ ((t/100)%10)+ ((t/1000)%10)+ ((t/10000)%10) >= y[1], [i for i in range(x[1]+1)] ) if x[0] == -2 else filter(lambda t: (t%10)+ ((t/10)%10)+ ((t/100)%10)+ ((t/1000)%10)+ ((t/10000)%10) <= y[1], x), list( map( lambda x: [x[0]-2, x[1]], enumerate(map(int, raw_input().split(" ")))) ) ) ))
ABC088B - Card Game for Two
atcoder.jp
数を取り合って各々のプレイヤーの合計値を最大化する問題．
数はどの順番で取っても良いため，各プレイヤーはその時点で残っている最大の数を取るのが最適な行動となる．これは，降順にソートされた数列を順番に取ることと等しい．
求める解は合計値の差分のため，先行が取る数(偶数番)を正，後攻が取る値(奇数番)を負として足していくことで解を得ることが出来る．
配列の番地番号をenumerateによって付与して走査した．配列数を表す値は不要だが読み取らなけらば先に進めないため，初期値とand演算を行うことで評価と値の無視を両立した．
print(reduce(lambda x, y: x + (-y[1] if y[0]&1 else y[1]), [input()&0]+list(enumerate(sorted(map(int, raw_input().split(" ")), reverse=True)))))
# 改行有 print( reduce(lambda x, y: x + (-y[1] if y[0]&1 else y[1]), [input()&0]+list(enumerate( sorted(map(int, raw_input().split(" ")), reverse=True) )) ) )
ABC085B - Kagami Mochi
atcoder.jp
与えられた数の集合から作成できる狭義単調増加列の長さの最大値を求める問題．
数をどの順番で使っても良いことから適切に並び替えすれば重複する数以外は全て使うことが出来ると分かる．そのため，組み込み関数のsetを使って重複した数を切り取り，残った列の数を出力するだけで良い．
print(len(set([input() for _ in range(input())])))
ABC085C - Otoshidama
atcoder.jp
以下の方程式を解く問題．
の値が定まると
は一意に定まるため，
を全探索するO(
)解法で解ける．
入力を変数に格納できないため，探索リストの先頭に入力用の要素を追加してreduceで使いまわす．
print(reduce(lambda x, y: str(x)+" "+str(y), reduce(lambda x, y: x if x[0] == True or y[3] < 0 or y[4] < 0 or x[1]-y[3]-y[4] < 0 or 10000*y[3]+5000*y[4]+1000*(x[1]-y[3]-y[4]) != x[2] else [True]+x[1:3]+y[3:]+[(x[1]-y[3]-y[4])], [[False]+map(int, raw_input().split(" "))+[-1,-1,-1]] + [[False,-1,-1, i, j] for i in range(0, 2001) for j in range(0, 2001)])[3:]))
これで通ると思ったが，ワンライナーによって無駄な処理が増えたためこのままではTLEやMLEに陥ってしまう．ここで，2式の差分を取ると以下の式が生成される．
生成された式から，の値は
に依存しないことが分かるので，
の値を全探索するだけで解を求めることが出来る(O(
))．(O(
)解法もあるが，今回は不要なので割愛)
print(reduce(lambda x, y: str(x)+" "+str(y), reduce(lambda x, y: x if x[0] == True or y[3] < 0 or int((x[2]-1000*x[1]-9000*y[3])/4000) < 0 or x[1]-y[3]-int((x[2]-1000*x[1]-9000*y[3])/4000) < 0 or 10000*y[3]+ 5000*int((x[2]-1000*x[1]-9000*y[3])/4000)+ 1000*(x[1]-y[3]-int((x[2]-1000*x[1]-9000*y[3])/4000)) != x[2] else [True]+x[1:3]+ [y[3]]+ [int((x[2]-1000*x[1]-9000*y[3])/4000)]+ [(x[1]-y[3]-int((x[2]-1000*x[1]-9000*y[3])/4000))], [[False]+map(int, raw_input().split(" "))+[-1,-1,-1]] + [[False,-1,-1, i] for i in range(0, 2001)])[3:]))
# 改行有 print( reduce(lambda x, y: str(x)+" "+str(y), reduce(lambda x, y: x if x[0] == True or y[3] < 0 or int((x[2]-1000*x[1]-9000*y[3])/4000) < 0 or x[1]-y[3]-int((x[2]-1000*x[1]-9000*y[3])/4000) < 0 or 10000*y[3]+ 5000*int((x[2]-1000*x[1]-9000*y[3])/4000)+ 1000*(x[1]-y[3]-int((x[2]-1000*x[1]-9000*y[3])/4000)) != x[2] else [True]+x[1:3]+ [y[3]]+ [int((x[2]-1000*x[1]-9000*y[3])/4000)]+ [(x[1]-y[3]-int((x[2]-1000*x[1]-9000*y[3])/4000))], [[False]+map(int, raw_input().split(" "))+[-1, -1, -1]] + [[False,-1,-1, i] for i in range(0, 2001)] )[3:] ) )
ABC049C - 白昼夢 / Daydream
atcoder.jp
指定された文字列を末尾追加していくことで文字列Sを構成できるか判定する問題．
文字列を逆にして考えるとシンプルな文字列比較を続けるだけで良いことが分かる．文字列は最初の3文字だけ一致判定できれば良い．そのため，3文字の一致判定後は残り文字数分だけ1文字ずつ一致判定を行う．4つの情報(現在の文字，現在の文字列(|s|<4)，現在使用中の文字列の残り，現在まで構成可能かどうか)をreduceに乗せて1文字ずつ進めて判定する．
提出後に気付いたが，結局文字列全てに対して判定を行うことになるため，わざわざ3文字一致して文字列を限定する必要はなかった．
print("YES" if reduce(lambda x, y: True if x == -1 and y == "" or x == True and y == "" or x == True and y == True else False, reduce(lambda a, b: [-1] + ([0, "", False] if a[3] == False else ["", a[2][1:] if a[2][0] == b[0] else "", True if a[2][0] == b[0] else False] if len(a[2]) > 0 else ["" if reduce(lambda x, y: ["", y[1]] if (a[1]+b[1]) == y[0] else ["", x[1]], [["_", ""], ['mae', 'rd'], ['rem', 'aerd'], ['esa', 're'], ['res', 'are']]) == "" else a[1]+b[1], reduce(lambda x, y: ["", y[1]] if (a[1]+b[1]) == y[0] else ["", x[1]], [["_", ""], ['mae', 'rd'], ['rem', 'aerd'], ['esa', 're'], ['res', 'are']])[1], a[3] & True]), [[c, c, "", True] for c in list(reversed(raw_input()))])) else "NO")
# 改行有 print( "YES" if reduce(lambda x, y: True if x == -1 and y == "" or x == True and y == "" or x == True and y == True else False, reduce(lambda a, b: [ -1 ] + ( [0, "", False] if a[3] == False else ["", a[2][1:] if a[2][0] == b[0] else "", True if a[2][0] == b[0] else False] if len(a[2]) > 0 else [ "" if reduce(lambda x, y: ["", y[1]] if (a[1]+b[1]) == y[0] else ["", x[1]], [["_", ""], ['mae', 'rd'], ['rem', 'aerd'], ['esa', 're'], ['res', 'are']] ) == "" else a[1]+b[1], reduce(lambda x, y: ["", y[1]] if (a[1]+b[1]) == y[0] else ["", x[1]], [["_", ""], ['mae', 'rd'], ['rem', 'aerd'], ['esa', 're'], ['res', 'are']] )[1], a[3] & True ] ), [[c, c, "", True] for c in list(reversed(raw_input()))] ) ) else "NO" )
ABC086C - Traveling
atcoder.jp
2次元平面上の旅行プランが与えられ，その旅行プランが実現可能かを判定する問題．
時刻から時刻
の移動はそれぞれ独立して考えることができるため，reduceで隣接する時刻についての判定をそれぞれ行う．実行不可能な移動が一つでもある場合は解がNoとなるため，時刻
における情報のリストにbool値を加え，and演算で旅行プラン全体の解を導出する．
print("Yes" if reduce(lambda a, b: [a[0] & False if b[1]-a[1] < abs(b[2]-a[2])+abs(b[3]-a[3]) or (b[1]-a[1] & 1) ^ (abs(b[2]-a[2])+abs(b[3]-a[3]) & 1) else True] + b[1:], [[True, 0, 0, 0]] + [[True] + map(int, raw_input().split()) for _ in range(int(input()))])[0] else "No")
# 改行有 print("Yes" if reduce( lambda a, b: [ a[0] & False if b[1]-a[1] < abs(b[2]-a[2])+abs(b[3]-a[3]) or (b[1]-a[1] & 1) ^ (abs(b[2]-a[2])+abs(b[3]-a[3]) & 1) else True ] + b[1:], [ [True, 0, 0, 0] ] + [ [True] + map(int, raw_input().split()) for _ in range(int(input())) ] )[0] else "No" )
おわりに
内包記法で遊ぼうと思ってたのに気づいたらreduceで殴るゲームになっていました．
見た目では問題の簡単さが相まって簡単に見えますが，やってみないと分からないような詰みポイントがいくつもあって楽しいです．ぜひ一度挑戦してみてください．
なお，__import__を使えばどこでもライブラリをimport出来るみたいなのでPython3系でもなんとかできそうです↓．
print("Even" if __import__("functools").reduce(lambda a, b: False if a&1 and b&1 else True, map(int, input().split(" "))) else "Odd")
