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問題くらいの難易度であればスラスラ解けるようになりたいですね。現実的に解けない可能性もありますが…
ABC172を振り返る(B問題まで)
見事にレートを溶かし、茶色生活が終わりを迎えました。
これは反省しないといけない…
B - Minor Change
「終わった…」って思いましたねこれは…
1文字ずつ見ていって違ったら+1するだけだと思うじゃないですか。私もそう思ったんですが10^5回ループしないといけないんですよね。まず間違いなくTLEになります。
read s
read t
c=0
for i in `seq 0 $((${#s}-1))`
do
if [ ${s:i:1} != ${t:i:1} ]
then
c=$((c+1))
fi
done
echo $c当時の自分はTLEすると感づいていたにもかかわらず提出して案の定TLEになってますね。これはいけない…
ここで20分近く詰まります。diffを使って上手いことできないか？ と考えますがどうもうまくいかない。
そんな中で閃いたのが、nlを使うという考えです。
例えばcupofcoffeeという入力が変数sに入っているとき、
echo $s | fold -1
とすると
c u p o f c o f f e e
という出力が得られます。1文字ごとに改行している、という感じですね。
これにnlを使うと行番号が加わり、
1 c
2 u
3 p
4 o
5 f
6 c
7 o
8 f
9 f
10 e
11 eとなります。これを一旦ファイルf1に入れておきます。
あとは2つ目の入力(ここではcupofhottea)にも同じ処理を行い、出力をファイルf2へ。
ここまでをまとめると、
read s read t echo $s | fold -1 | nl > f1 echo $t | fold -1 | nl > f2
となっています。
そして出来上がったファイル2つをcatで出力し、sortで並び替えると以下のようになります。
1 c
1 c
2 u
2 u
3 p
3 p
4 o
4 o
5 f
5 f
6 c
6 h
7 o
7 o
8 f
8 t
9 f
9 t
10 e
10 e
11 a
11 eなんかうまくいきそう！ あとは「共通行を消す」という処理をすると、i文字目が同じ場合は1行消えますが違う場合は消えません。この処理を行った後の行数ともともとの文字数の差を出力すればOKですね。
共通行を消す処理はuniqを使うのですが、既にsortを書いているのでsort -uと処理しても同じです。行数カウントはwc -l、変数sの長さは${#s}であることを踏まえると、
read s
read t
echo $s | fold -1 | nl > f1
echo $t | fold -1 | nl > f2
echo $((`cat f1 f2 | sort -u | wc -l`-${#s}))でACでした。当時の自分はなぜか空白記号を消す処理を挟んでいましたが、そんなのしなくても問題ありません。
実行時間は約600ms。十分です。
C - Tsundoku
これは無理そう…？
累積和(a[0]からa[i]までの和を配列s[i]に入れる)みたいな処理を前準備として行いたいのですが、その前準備でTLEがほぼ確定しています。
これを書いている時点ではAC解が存在していません。
まとめ
B問題の解法にもっと早く気づいていればこんなにレート落とすこともなかったんじゃないかなと思っています。
というかTLEするの分かっていて提出するのはよくない。精進します。
