ABC173を振り返る(B問題まで)
前回の記事から1文字しか変わっていないんだが？
A - Payment
1000-1000で割った余りを出力、ただしこれが1000になるなら0を出力。やるだけですね。
read v echo $(((1000-v%1000)%1000))
B - Judge Status Summary
これは何とかなりました。やっぱりBashはB問題あたり(あるいは簡単なC問題)が一番楽しいと感じます。
方針としてはuniq -cでそれぞれ数え上げるのが鉄板でしょう。というわけで一旦、
read n
a=(`dd`)
echo ${a[@]} | tr ' ' '\n' | sort | uniq -cと処理することを考えます。a=(`dd`)は残りの標準入力を全部配列に突っ込んでいるとでも捉えてください。
ここで、echo ${a[@]}と出力した場合はスペース区切りとなること、uniqを使うためにはあらかじめソートされている必要があることを忘れてはいけません。
例えばAC x 3、WA x 1、TLE x 2、RE x 0の入力は次のように出力されます。
3 AC
2 TLE
1 WAこれを配列に入れてしまえば簡単に出力できそうなのですが、REの個数が0なのが厄介ですね。
どれが消えているのか判断するのはぶっちゃけ面倒です。スマートな解き方はあるんでしょうけどコンテスト中には考えたくない。
というわけで先ほどの処理を少し変えて、
read n
a=(`dd`)
a+=(AC WA TLE RE)
echo ${a[@]} | tr ' ' '\n' | sort | uniq -c4要素を1つずつ配列にpushします。これですべて1回は確実に現れますね。ちなみにこの出力は
4 AC
1 RE
3 TLE
2 WAとなっています。
あとはそれぞれ-1したものを正しい順番で出力すればおしまいです。というわけで、
read n
a=(`dd`)
a+=(AC WA TLE RE)
a=(`echo ${a[@]} | tr ' ' '\n' | sort | uniq -c`)
echo "${a[1]} x $((a[0]-1))"
echo "${a[7]} x $((a[6]-1))"
echo "${a[5]} x $((a[4]-1))"
echo "${a[3]} x $((a[2]-1))"これがコンテスト当時の解答です。配列aを使いまわしているのでちょっとややこしくなっていますかね。
あと表示は${a[1]}ではなく素直にACとか書いた方がいいし、配列に入れるときにtr -dc '0-9\n'して文字を消去しておいた方がよっぽど分かりやすい気がします。
というわけで修正版が以下の通りです。
read n
a=(`dd`)
a+=(AC WA TLE RE)
c=(`echo ${a[@]} | tr ' ' '\n' | sort | uniq -c | tr -dc '0-9\n'`)
echo "AC x $((c[0]-1))"
echo "WA x $((c[3]-1))"
echo "TLE x $((c[2]-1))"
echo "RE x $((c[1]-1))"時間的にもOK。今回はちゃんと解ける問題で良かったです。
(他にスマートな解き方があるか調べたところ、一旦ファイルに突っ込んでからgrepを使うやり方がありましたね。uniq -cに引っ張られすぎた感じがします。)
C - H and V
せいぜい6x6だから全部見てやればいいと思っていたのですが無理でした。
よくよく考えなくともループ回数が2^6*2^6(どの行と列を取るかの全パターン)*6*6(各要素のチェック)=約150000、普通にBashがループできる許容範囲を超えていましたね。
公式の解説に近い実装はできていたのですが無念…
まとめ
前回よりB問題をスムーズに片付けられたので悪くはなかったかと思います。
少しずつ使えるコマンドやアルゴリズムを増やし、今回のC問題くらいの難易度であればスラスラ解けるようになりたいですね。現実的に解けない可能性もありますが…
