ABC188を振り返る(C問題まで)
どうにかレートは上げることが出来た。
今回はB,Cともにループをどう回避するかが大切。
A - Three-Point Shot
要は2数の差の絶対値が3未満であるかどうかを判定できれば良い。いきなり少し面倒…
大きい順に並べる→改行をマイナスにする→末尾にマイナスがついてしまうので0を付けて帳尻を合わせる→計算する、で差の絶対値が得られる。あとはYesとNoを出すだけ。
v=$((`tr ' ' '\n' | sort -nr | tr '\n' '-'`0)) ((v<3)) && echo "Yes" || echo "No"
というか普通に差を計算してから先頭のマイナスを消せばいいじゃんね。${v#-}で先頭のマイナスを消せるのは覚えておきたい。
B - Orthogonality
内積を計算する。ただしforループを使うと爆死する未来しか見えないので対策を講ずる必要がある。
はじめに入力の縦横を入れ替えたい。もともとの入力の1行目を改行区切りにしてa.txtに、同じく2行目をb.txtに入れる。あとはpasteでこれらを横並びにする。この際の区切り文字をアスタリスクにすることで内積の形にかなり近づけられる。
例えば入力が
3 1 3 5 3 -6 3
だったとして、
read n read a read b echo $a | tr ' ' '\n' > a.txt echo $b | tr ' ' '\n' > b.txt paste -d '*' a.txt b.txt
を実行すると
1*3 3*-6 5*3
になる。あとはA問題でやったように改行をプラスに置換、最後に0を置くことで計算できる。
read n read a read b echo $a | tr ' ' '\n' > a.txt echo $b | tr ' ' '\n' > b.txt v=$((`paste -d '*' a.txt b.txt | tr '\n' '+'`0)) ((v==0)) && echo "Yes" || echo "No"
C - ABC Tournament
まーじでむずかしい。二重ループした暁には壊滅する。
とりあえず人数を半分に減らす(この戦いで勝った人だけ残す)方法から考える。bcコマンドを使ってどうにか一括で処理してみる。
ひとまず入力が
2 1 4 2 5
だとして進める。ペアとなる2つで1行になるようにしたいので、
read n read s echo $s | sed -r "s/([0-9]+) ([0-9]+)/\1 \2\n/g"
と置換してみる。たぶんもっといい方法はあるが、これで
1 4 2 5
となる。空白や改行などがぐちゃぐちゃしてるが目を瞑りたい。
次に各行の2数の最大値をbcで得られるようなsedの書き方を考えると、
read n read s echo $s | sed -r "s/([0-9]+) ([0-9]+)/if\(\1\>\2\) \1 else \2\n/g"
となる。これで入力を
if(1>4) 1 else 4 if(2>5) 2 else 5
に置換できた。あとはbcを突っ込み、改行をスペースに変えれば半分の勝者だけが残った文字列を生成できる。これをn-1回繰り返し、とりあえず決勝の2数だけが残るようにする。
read n
read s
while((n>1))
do
s=`echo $s | sed -r "s/([0-9]+) ([0-9]+)/if\(\1\>\2\) \1 else \2\n/g" | bc | tr '\n' ' '`
n=$((n-1))
doneあとは2数のうち小さい方を取得する。これは面倒なので配列を使ってよいだろう…
read n
read s
while((n>1))
do
s=`echo $s | sed -r "s/([0-9]+) ([0-9]+)/if\(\1\>\2\) \1 else \2\n/g" | bc | tr '\n' ' '`
n=$((n-1))
done
a=($s)
ans=$((a[0]<a[1]?a[0]:a[1]))ところが最後に1つ問題が。準優勝したのは何番目の選手か考えなければならない。
初期の入力を改行区切りにしたときに何行目で出てくるかをgrepで取得することで解決できる。何行目かを出すオプション-n、完全一致を判定する-xを付ける。
read n
read s
sraw=$s
while((n>1))
do
s=`echo $s | sed -r "s/([0-9]+) ([0-9]+)/if\(\1\>\2\) \1 else \2\n/g" | bc | tr '\n' ' '`
n=$((n-1))
done
a=($s)
ans=$((a[0]<a[1]?a[0]:a[1]))
echo $sraw | tr ' ' '\n' | grep -xn $ans | tr ':' '\n' | head -1色々とあったがこれで終わり！ 制限時間のない日に解きたかった
ABC179を解いてみる(B問題まで)
A - Plural Form
一旦入力をそのまま出力し、末尾がsであるかどうかを判断するのが初心者には楽。変数sの末尾1文字は${s: -1}で取り出せる。スペースは必須。
read s
echo -n $s
[ ${s: -1} = "s" ] && echo es || echo s
B - Go to Jail
この程度であればBashでもループで探索できはするが、せっかくなのでもう少し凝ったやり方を。
入力例1を使って試してみる。最初に先頭1行は使わないのでtailを使って消し、以降の入力のスペースを-(マイナス)に置換する。
tail -n +2 | tr ' ' '-'
1-2 6-6 4-4 3-3 3-2
次にbcを使って計算する。
tail -n +2 | tr ' ' '-' | bc
-1 0 0 0 1
あとは0が3連続しているかを確認すればよい。面倒なので改行を削除し、grepで000とマッチするか判断する。grepの結果を三項演算子もどきで処理してやれば終わり！
tail -n +2 | tr ' ' '-' | bc | tr -d '\n' | grep -q "000" && echo "Yes" || echo "No"
C問題以降についてはTLEする匂いしかしないので一旦ここまで。
ABC178を解いてみる(B問題まで)
色々あって3か月プログラミングできていなかった。だいぶ衰えている気もする。
ABCにもしばらく参加していないためリハビリも兼ねて解いてみる。
B - Product Max
正負で色々と条件分岐しないといけないか？ と思ったが、よくよく考えなくとも候補はせいぜい4通り。xは最小値か最大値のどちらかしか可能性が無く、yも同じである。あえて中途半端な値を取る理由もない。
というわけで4通り列挙してソートするのが楽。
read a b c d echo $((a*c)) $((a*d)) $((b*c)) $((b*d)) | tr ' ' '\n' | sort -nr | head -1
C - Ubiquity
解き方自体はそこまで難しくない。要は全パターンが10^n通り、うち0を1つも含まないのが9^n通り、9を1つも含まないのが同じく9^n通り。全パターンからこの2つを引くと0も9も含まない組合せを余分に引いてしまっているので、その分8^nをもう1回足して帳尻を合わせる。
ただ10^1000000とかTLEせずに解けるわけないだろ！ と半ば諦め。TLEコードは下の通り。bcでもダメ。
readonly m=1000000007
read n
a=1
b=1
c=1
for i in `seq $n`
do
a=$((a*10%m))
b=$((b*9%m))
c=$((c*8%m))
done
echo $((((a-2*b+c)%m+m)%m))というわけで放棄しかけたのだが、ここで「ループを何個かまとめて回せばいいのでは？」という発想に至る。その結果がこれ。
readonly m=1000000007
read n
a=1
b=1
c=1
for i in `seq $((n/5))`
do
a=$((a*100000%m))
b=$((b*59049%m))
c=$((c*32768%m))
done
for i in `seq $((n%5))`
do
a=$((a*10%m))
b=$((b*9%m))
c=$((c*8%m))
done
echo $((((a-2*b+c)%m+m)%m))5で割った回数だけ先にループし、端数は最後にカバーするといったもの。なんとこれでギリギリAC。やっぱ諦めるものじゃないな。
ただ最後の式はもっといい書き方があるんじゃないかと考えている。mが多すぎ。どれか減らせそうな気はするが…
a-2*b+cが-mより大きい確証がない以上、どうしても1回mで割った余りを求めて範囲を-(m-1)からm-1に絞り、mを足してもう1回余りを求めるしかないような気もする。たぶん根底から勘違いしているんだろうがどうなのだろう。
ABC177を振り返る(A,C問題)
レートこそ耐えたものの、不勉強が強く表れた回。
A - Don't be late
まあやるだけ。T*Sだけ進むことが出来るので、あとはその値がDに届くか届かないかで判定する。
read d t s ((t*s>=d)) && echo Yes || echo No
B - Substring
無理。最善は尽くした。
read s
read t
ls=${#s}
lt=${#t}
min=$lt
for i in `seq 0 $((ls-lt))`
do
ss=${s:i:lt}
c=0
for j in `seq 0 $((lt-1))`
do
if [ ${ss:j:1} != ${t:j:1} ]
then
c=$((c+1))
if((c>=min))
then
break
fi
fi
done
min=$((min<c?min:c))
done
echo $minすべての部分文字列についてループしていく方法でTLE。forループはやはり厳しいか。
過去のABCで似たような問題が出ていたが、あれは2つの文字列長が同じ状態であった。今回は部分文字列を列挙していかないといけないため前回同様にはいかず。これ解法あるのだろうか…
C - Sum of product of pairs
今回の戦犯。ちょっと思いつくのに時間がかかった。
正直( (a[0]+a[1]+a[2]+...+a[n-1])^2-(a[0]^2+a[1]^2+...+a[n-1]^2) ) / 2で解く気満々だったが、mod演算の関係で割れない。
この場合取れる戦略は2つで、「mod演算できる計算式を別に考える」か「この計算式を実現させる方法を考える」かのどちらかである。今回は(どういうわけか)後者を選択、bcコマンドによるゴリ押しで進んだ。本来であればオーバーフローしないようにmod演算をループごとに行うのが筋であろうが、オーバーフローしない状態で最後まで計算する方法があるなら越したことは無い(???)
m=1000000007 read n read a s1=`echo $a | tr ' ' '+'` s2=`echo $a | sed -r "s/([0-9]+)/\1\*\1/g" | tr ' ' '+'` echo "(($s1)*($s1)-($s2))/2%$m" | bc
入力をaとして受け取り、s1にΣa[i]を、s2にΣ(a[i]^2)の数式を入れた。あとはこれをbcコマンドに突っ込んで最後にmod演算する。
あまり美しいとは言えない解法だが、ギリギリACできたのでとりあえずヨシ！
余談
もう少し丁寧な解法を考える。
漸化式のように、i番目までの解=(i-1番目までの解)+(i番目の値)*(i-1番目までの値の和)でつないでいく形。
m=1000000007
read n
read a
s1=0
ans=0
for x in $a
do
ans=$(((ans+s1*x)%m))
s1=$(((s1+x)%m))
done
echo $ans普通にACできてしまった。これがコンテスト中に思いつかなかったのは勉強不足であったと言わざるを得ない。
解説を見ると累積和や区間和という言葉が出てきたが、正直真面目に実装した経験がないので理解できているか怪しい。本当は日頃からもっと学んでいければよいのだが…
ABC176を振り返る(C問題まで)
ついに茶色に復帰した。とはいえギリギリなのでまたすぐ落ちる気はする…
A - Takoyaki
これは焼く回数の計算に小数点の切り上げが必要。愚直に分岐してもよい。
read n x t
if((n%x==0))
then
echo $((n/x*t))
else
echo $(((n/x+1)*t))
fi1発で計算したい場合は次のようになる。
read n x t echo $(((n+x-1)/x*t))
B - Multiple of 9
各桁の総和が9の倍数であるかを判定したいが、本ブログで何回も触れてきたように2*10^5のループを足し算していくのはちょっと危険。別の方法を考える。
ここではuniqを使い、それぞれの数字が何回現れるかを計算する。
fold -1 | sort | uniq -c
これを入力例3で試すと、次の出力が得られる。
7 0
6 1
10 2
10 3
8 4
7 5
8 6
6 7
11 8
13 97個の0、6個の1…といった表記に出来る。
次にこの結果を配列に入れると、a=(7 0 6 1 ...)となる。あとはこれを使って各桁の総和を計算すればよい。
a=(`fold -1 | sort | uniq -c`)
l=${#a[@]}
s=0
i=0
while((i<l))
do
s=$((s+a[i]*a[i+1]))
i=$((i+2))
done
((s%9==0)) && echo Yes || echo Nolには配列の長さが入っている。これでACできる。
改善点
さらに考えると、0と9はどれだけあっても総和が9の倍数であるかの判定に影響しないため、最初に削除してしまう方法もある。そこまで大幅な時短にはならないが考え方としてはありかもしれない。
C - Step
今回の肝。B問題のようにループを省略する手段がなく、愚直にループを回していくしかない。ところが200000のループはBashにとってかなりの難敵である。
例えばこう書くとTLEになる。
read n
read -a a
s=0
min=${a[0]}
for x in ${a[@]}
do
((x<min)) && s=$((s+min-x)) || min=$x
done
echo $siについてのループを回してループ内でa[i]を参照するよりも、配列の中身を直接xに入れて処理した方が明らかに早くなる(配列を参照しないで済むため？)
ところがこれでも足りない。
そこで、そもそも配列を使わないという方法を考える。上のコードではread -a aのように配列とみなして入力を受け取っているが、この-aを消し、あくまでも1つの文字列として入力を受け取ろうと考える。
文字列であっても、空白区切りであれば1つずつループを回すことが可能である。つまり、配列時のfor x in ${a[@]}と文字列時のfor x in $aで同じループが実現できる。配列に入れて展開する時間を省けるという利点がある。
ただしこの問題では、最初の基準点としてa[0]を調べる必要が出てくる。そこで、cutコマンドを使って空白区切りで表されるデータの1つ目だけを切り取ることで取得する。
長々と書いたが、要は配列を使うことそのものが時間を食ってしまっているため、どうにか配列を使わないで考えるとギリギリ時間が足りたのである。
read n
read a
s=0
min=`echo $a | cut -d' ' -f1`
for x in $a
do
if((x<min))
then
s=$((s+min-x))
else
min=$x
fi
done
echo $sa[0]はcut -d' ' -f1で代用している。これは、空白区切りで表されたフィールドの1つ目を切り取るという意味である。時間は983ms。
余談
では他の200000回ループも似たように攻略できるかといったらそうではなく、アルゴリズム上どうしてもループ内で配列の参照という形を取りたい場合はこの方法が使えない。現時点での攻略法は適用できる問題がかなり限られてしまうため、別の方法も考えていきたいところ。
ちなみにB問題をこの方法で実装すると次のようになる。ここでは入力をfold -1で1文字ずつ区切り、そのままforループに突っ込んでいる。
s=0
for x in `fold -1`
do
s=$((s+x))
done
((s%9==0)) && echo Yes || echo No意外と500ms以内でACできてしまった。B問題については少し考えすぎだったかもしれないが、結果として0WAで通せたので良かったとする。
ABC175を振り返る(A,C問題)
ちょっと調子が良かったと言える回。Bash相性は良かったり良くなかったりした。
茶色復帰も少しずつ見えてきている。
A - Rainy Season
せいぜい入力が3であることを考慮すると、RRRがあるか→RRがあるか→Rがあるかを順番にif文で見ていってもよい。
これがコンテスト当時のAC解。
read s
if echo $s | grep -q RRR
then
echo 3
elif echo $s | grep -q RR
then
echo 2
elif echo $s | grep -q R
then
echo 1
else
echo 0
fi
grep -qは見つかったか見つかってないかだけを判定し、出力はさせたくないときに使える。
また、こう長ったらしく書かなくても、
grep -Eo "R+" | head -1 | tr -cd R | wc -c
でもいける。これは"R+"(Rの1回以上の繰り返し)が入力にあればそれを出力し、その1行目のRの文字数を出力している。これが4文字以上であればsortなどが必要になってくるが、3文字までなのでこれで良い。
多分文字数カウントなどに関してはもっと効率よい手段がある。
B - Making Triangle
公式の解説では「Nは200までなのですべての組を確認できる」とあるが、Bashでは確認できない。
read n
n=$((n-1))
a=(`tr ' ' '\n' | sort -n`)
c=0
for i in `seq 0 $n`
do
for j in `seq $((i+1)) $n`
do
for k in `seq $((j+1)) $n`
do
if((a[i]+a[j]>a[k]))
then
if((a[i]!=a[j]&&a[j]!=a[k]))
then
c=$((c+1))
fi
else
break
fi
done
done
done
echo $cこの3重ループはTLEする。他の方法が無いか考えておく。
C - Walking Takahashi
まず求める値が絶対値であることを踏まえ、xは絶対値を取って正の値になるようにする。
次に、kステップあれば原点を越える一歩手前まで到達できるかを計算し、到達できないのであればひたすら原点に向かい続けた際の距離が解となる。ここで、この条件分岐は移動回数による不等式で求める。距離による不等式if((k*d<x))ではオーバーフローしてしまうので気を付ける(1敗)。
到達できる場合、残りの移動回数を計算する。この回数が偶数なら一歩手前が解、奇数なら原点を1回だけ超えた場所が解となる。原点近くを行って帰って…と繰り返し移動することを考えると導出できる。
こう考えるとループが一切必要ないため、Bashにとってはかなりありがたい問題であった。
read x k d
x=$((x>0?x:-x))
c=$((x/d))
if((k<c))
then
echo $((x-d*k))
else
echo $(((k-c)%2?d-(x-d*c):x-d*c))
fiこれでAC。変数cには原点を越える手前までの移動数が入る。
ABC174を振り返る(B問題まで)
ちょっと今回は相性が悪かった(毎回言ってる)。
B - Distance
またN=10^6のループかぁ…。難易度は低いんですが時間的な制約をどうにかしないといけません。
いつも通りforループを避ける戦略を取りたいところ。今回はbcを使って解きます。このコマンドは数式を受け取ってそれを出力してくれるという素晴らしい関数です。
今回は入力x,yに対してx*x+y*y<=d*dを満たすx,yの数を出力する必要があるため、とりあえずこの形を作ることから考えます。
read n d sed -r "s/^(.+) (.+)$/\1\*\1+\2\*\2<=$((d*d))/g"
これで入力例1が次のようになります。
0*0+5*5<=25 -2*-2+4*4<=25 3*3+4*4<=25 4*4+-4*-4<=25
あとはこれをbcコマンドに突っ込めば、
1 1 1 0
となります。不等式が成り立っている場合1、そうでない場合0を出力していますから、あとは1の数を数えるだけになります。
今回は0か1しかない中で1を選ぶので、シンプルにgrep 1 | wc -lで良いですね。
以上まとめて、
read n d sed -r "s/^(.+) (.+)$/\1\*\1+\2\*\2<=$((d*d))/g" | bc | grep 1 | wc -l
でACとなります。しかし1500msを超えていて危なかったです。もう少し簡単にできるといいんですが…
まとめ
C問題、D問題のアルゴリズムは分かるようになりたいところ。
