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色々とあったがこれで終わり！ 制限時間のない日に解きたかった
