結果
| 問題 | No.204 ゴールデン・ウィーク(2) |
| ユーザー |
 tails
|
| 提出日時 | 2015-05-22 19:17:08 |
| 言語 | Perl (5.38.2) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 1,000 ms |
| コード長 | 5,042 bytes |
| コンパイル時間 | 97 ms |
| コンパイル使用メモリ | 5,268 KB |
| 実行使用メモリ | 4,812 KB |
| 最終ジャッジ日時 | 2023-08-25 23:43:00 |
| 合計ジャッジ時間 | 1,677 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
4,512 KB |
| testcase_01 | AC | 3 ms
4,536 KB |
| testcase_02 | AC | 2 ms
4,784 KB |
| testcase_03 | AC | 3 ms
4,636 KB |
| testcase_04 | AC | 2 ms
4,764 KB |
| testcase_05 | AC | 3 ms
4,628 KB |
| testcase_06 | AC | 2 ms
4,684 KB |
| testcase_07 | AC | 3 ms
4,596 KB |
| testcase_08 | AC | 3 ms
4,576 KB |
| testcase_09 | AC | 3 ms
4,712 KB |
| testcase_10 | AC | 3 ms
4,508 KB |
| testcase_11 | AC | 3 ms
4,536 KB |
| testcase_12 | AC | 2 ms
4,516 KB |
| testcase_13 | AC | 3 ms
4,752 KB |
| testcase_14 | AC | 3 ms
4,512 KB |
| testcase_15 | AC | 3 ms
4,632 KB |
| testcase_16 | AC | 3 ms
4,616 KB |
| testcase_17 | AC | 3 ms
4,516 KB |
| testcase_18 | AC | 3 ms
4,580 KB |
| testcase_19 | AC | 3 ms
4,740 KB |
| testcase_20 | AC | 2 ms
4,632 KB |
| testcase_21 | AC | 4 ms
4,800 KB |
| testcase_22 | AC | 3 ms
4,688 KB |
| testcase_23 | AC | 2 ms
4,712 KB |
| testcase_24 | AC | 2 ms
4,764 KB |
| testcase_25 | AC | 3 ms
4,536 KB |
| testcase_26 | AC | 2 ms
4,776 KB |
| testcase_27 | AC | 3 ms
4,616 KB |
| testcase_28 | AC | 4 ms
4,656 KB |
| testcase_29 | AC | 2 ms
4,512 KB |
| testcase_30 | AC | 2 ms
4,488 KB |
| testcase_31 | AC | 2 ms
4,628 KB |
| testcase_32 | AC | 3 ms
4,512 KB |
| testcase_33 | AC | 5 ms
4,716 KB |
| testcase_34 | AC | 2 ms
4,656 KB |
| testcase_35 | AC | 3 ms
4,512 KB |
| testcase_36 | AC | 2 ms
4,612 KB |
| testcase_37 | AC | 2 ms
4,688 KB |
| testcase_38 | AC | 2 ms
4,612 KB |
| testcase_39 | AC | 3 ms
4,680 KB |
| testcase_40 | AC | 2 ms
4,536 KB |
| testcase_41 | AC | 3 ms
4,540 KB |
| testcase_42 | AC | 4 ms
4,768 KB |
| testcase_43 | AC | 2 ms
4,576 KB |
| testcase_44 | AC | 3 ms
4,540 KB |
| testcase_45 | AC | 2 ms
4,812 KB |
| testcase_46 | AC | 2 ms
4,796 KB |
| testcase_47 | AC | 3 ms
4,508 KB |
| testcase_48 | AC | 2 ms
4,632 KB |
コンパイルメッセージ
Unquoted string "x" may clash with future reserved word at Main.pl line 1. Unquoted string "x" may clash with future reserved word at Main.pl line 1. Main.pl syntax OK
ソースコード
$_=x x($==<>).<>.<>.x x$=;s/
//g;/(??{"o*x{0,$=}o*"})(??{$b+=$-=-$b+length$&})/;print$b
__END__
上記の87バイトのコードの説明です。
全体の構造は、セミコロンで区切られた、次の4つの文からできていて、
これらが順に実行されます。
(1) $_=x x($==<>).<>.<>.x x$=
(2) s/\n//g
(3) /(??{"o*x{0,$=}o*"})(??{$b+=$-=-$b+length$&})/
(4) print$b
--------
(1) $_=x x($==<>).<>.<>.x x$=
<> で入力を読み込みます。
生放送で誰かが「Perl の <> が謎だ」とおっしゃっていました。
実際かなり複雑で、区切り文字の設定とコンテキストによって
挙動が変わります。
このコードの場合は、区切り文字は特に変えていないので
デフォルトの改行文字です。つまり、行が単位（入力レコード）
になります。
コンテキストは、理由の説明は省略しますが、ここでは
スカラーコンテキストです。その場合、1つの <> が入力の1単位を
表します。
以上を合わせると、結局、1つの <> が入力の1行になります。
$==<> で、最初の入力行つまり有給日数を $= という変数に
代入しています。分解して書くと $= = <> です。
<> が返す値には区切り文字である改行文字も付いてきますが、
$= は整数値しか入れられない変数なので、
代入時に整数に変換されて改行文字が落ちます。
左側にある x x($==<>) と、右側に出てくる x x$= というのは、
どちらも文字列 "x" の $= 回の繰返しの文字列です。
x x という部分の左側の x は文字列 "x" の意味で、
右側の x は文字列の繰返しの二項演算子です。
. というのは文字列を連結する演算子です。
"x" の繰返しと、入力の2行目と、3行目と、"x" の繰返し
を連結して、結果を $_ に代入しています。
--------
(2) s/\n//g
先程作った $_ から改行を全て取り除いています。
Perl のいくつかの文や式では、処理の対象を明示しない場合に、
暗黙で $_ が処理の対象になります。
文字数を節約するために \n の部分に本物の改行を使っているので、
この文の途中で行が分断されています。
--------
(3) /(??{"o*x{0,$=}o*"})(??{$b+=$-=-$b+length$&})/
全体が1つの正規表現です。正規表現をコード中にいきなり書いた
場合には、自動的に $_ に対してマッチングが取られます。
正規表現の中身は、2つの (??{...}) という構造になっています。
これは ... の部分を Perl のコードとして評価し、評価結果を
正規表現として扱うという構文です。
左側の (??{"o*x{0,$=}o*"}) は、中身が単なる文字列なので、
o*x{0,$=}o* を変数展開したものがそのまま正規表現になります。
（余談）
それなら、左側は (??{...}) を使わずに、単に
/o*x{0,$=}o*(??{$b+=$-=-$b+length$&})/
と書いても良さそうです。実際、少し前までの Perl では
そう書くことができましたが、今はセキュリティの理由だか何だかで、
変数展開と (??{...}) を混在させるとエラーになります。
（余談おしまい）
$= には有給日数が代入されています。なので、例えば $= が 5 なら、
(??{"o*x{0,$=}o*"}) は o*x{0,5}o* に評価されます。
これは、 "o" が0個以上あって、 "x" が0～5個続いて、さらに
"o" が0個以上続く、という部分文字列にマッチします。
右側の (??{$b+=$-=-$b+length$&}) は、左側でマッチした部分の
長さの max を求めています。その時点までの最大値で $b が
更新されていきます。
$& というのは、正規表現にマッチした部分文字列を表す変数ですが、
今はまだマッチの途中なので、この場合には、
マッチの開始位置から現在の位置までの部分文字列を表します。
length$& で、その長さを求めます。
やりたいことは、要するに $b = max($b,length$&) ですが、
Perl には max を求める組み込み関数がありません。
仕方がないので、 $- という変数の、負の値を代入すると 0 になる
という性質を利用しています。
これで $b が更新されますが、その結果が正規表現として
扱われます。 $b は数値つまり数字の並びなので、
$_ のどの部分にもマッチしません。結局、マッチはここで失敗し、
左側に戻って、（ o*x{0,$=}o* のバックトラックを引き起こした後）
マッチ開始位置を1つ右に進めてマッチをやり直し、
これが繰り返されます。
どの位置から開始してもマッチが成功することはないので、
最終的に失敗するまでの間に、全ての開始位置を試すことになります。
--------
(4) print$b
結果を出力します。