AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) B Three Coins
問題
全部裏を向いたコインがN枚並んでいます。コインにはそれぞれスコアaiが設定されています。
以下の操作を好きなだけ行うことが出来ます:
- 連続した3枚のコインについて、すべて表裏が一致していた場合に限りその3枚を裏返す
表になっているコインのスコア総和の最大値を求めてください。
制約
- 3 <= n <= 500
- -100 <= a[i] <= 100
SECON 2017 Online CTF Powerful Shell(Binary, 300pt)
powershellの実行ファイルが与えられます。
そのままだと実行権限無かったのでまずぐぐってPCの設定を変えます。
中身はこんな感じ。
$ECCON=""; $ECCON+=[char](3783/291); $ECCON+=[char](6690/669); $ECCON+=[char](776-740); $ECCON+=[char](381-312); $ECCON+=[char](403-289); $ECCON+=[char](-301+415); $ECCON+=[char](143-32); $ECCON+=[char](93594/821); (中略) $ECCON+=[char](803-793); $ECCON+=[char](10426/802); Write-Progress -Activity "Extracting Script" -status "20040" -percentComplete 99; $ECCON+=[char](520-510); Write-Progress -Completed -Activity "Extracting Script";.([ScriptBlock]::Create($ECCON))
難読化(?)したコードを生成しなおして実行しているっぽい。
というわけで$ECCONを別ファイルに出力すると、それ自体がpowershellスクリプトになるので実行します。
すごい。
This host is too freshだと文句を言われているので該当するスクリプト部を見ると
<# Host Check #> Write-Host -b 00 -f 15 Checking Host... Please wait... -n Try{ If ((Get-EventLog -LogName Security | Where EventID -Eq 4624).Length -Lt 1000) { Write-Host "This host is too fresh!" Exit } }Catch{ Write-Host "Failed: No admin rights!" Exit } Write-Host "Check passed"
一瞬イベントログについて真面目に調べかけましたが、30分くらいしてこのコードをまるっと消せばいいことに気づきます。
すごい。(2回目)
実際にキーを押すと音が鳴ります。すごい。
でまあ何音か鳴らすとプログラムが終わってしまうので該当するコードを読みます。
$keytone=@{'a'=261.63} $pk='a' ForEach($k in ('w','s','e','d','f','t','g','y','h','u','j','k')){ $keytone+=@{$k=$keytone[$pk]*[math]::pow(2,1/12)};$pk=$k } Write-Host -b 00 -f 15 "Play the secret melody." (ここに鍵盤を描画するprint文がひたすら入るので略) Write-Host $stage1=@();$f=""; While($stage1.length -lt 14){ $key=(Get-Host).ui.RawUI.ReadKey("NoEcho,IncludeKeyDown") $k=[String]$key.Character $f+=$k; If($keytone.Contains($k)){ $stage1+=[math]::floor($keytone[$k]) [console]::beep($keytone[$k],500) } } $secret=@(440,440,493,440,440,493,440,493,523,493,440,493,440,349) If($secret.length -eq $stage1.length){ For ($i=1; $i -le $secret.length; $i++) { If($secret[$i] -ne $stage1[$i]){ Exit } } x "Correct. Move to the next stage." }
冒頭の
ForEach($k in ('w','s','e','d','f','t','g','y','h','u','j','k')){ $keytone+=@{$k=$keytone[$pk]*[math]::pow(2,1/12)};$pk=$k }
でキーごとに音のトーンを表す数字を割り当てており、
それをsecretに書かれた順番通りに押せばクリアです。
なおこの鍵盤の入力が次のステップでも使われるため、これらのコードをまるっと消してしまうと今度は先に進めなくなります。
このステージを突破すると、今度は「Enter the password.」と言われます。
なんのこっちゃなので対応するコードを見ます。
$text=@"(3000文字位あるので略)"@ $plain=@() $byteString = [System.Convert]::FromBase64String($text) $xordData = $(for ($i = 0; $i -lt $byteString.length; ) { for ($j = 0; $j -lt $f.length; $j++) { $plain+=$byteString[$i] -bxor $f[$j] $i++ if ($i -ge $byteString.Length) { $j = $f.length } } }) iex([System.Text.Encoding]::ASCII.GetString($plain))
ということで最初と同じくまた難読化したコードを組み立てて実行しているので、
実行直前に$plainを吐き出してみます。
${;}=+$();${=}=${;};${+}=++${;};${@}=++${;};${.}=++${;};${[}=++${;}; ${]}=++${;};${(}=++${;};${)}=++${;};${&}=++${;};${|}=++${;}; ${"}="["+"$(@{})"[${)}]+"$(@{})"["${+}${|}"]+"$(@{})"["${@}${=}"]+"$?"[${+}]+"]"; ${;}="".("$(@{})"["${+}${[}"]+"$(@{})"["${+}${(}"]+"$(@{})"[${=}]+"$(@{})"[${[}]+"$?"[${+}]+"$(@{})"[${.}]); ${;}="$(@{})"["${+}${[}"]+"$(@{})"[${[}]+"${;}"["${@}${)}"];"${"}${.}${(}+${"}${(}${|}+${"}${(}${)}+${"}${(}${)}+${"}${)}${|}+${"}${)}${&}+${"}${(}${+}+${"}${&}${@}+${"}${+}${=}${+}+${"}${|}${)}+${"}${+}${=}${=}+${"}${[}${]}+${"}${)}${@}+${"}${+}${+}${+}+${"}${+}${+}${]}+${"}${+}${+}${(}+${"}${.}${@}+${"}${[}${]}+${"}${&}${=}+${"}${+}${+}${[}+${"}${+}${+}${+}+${"}${+}${=}${|}+${"}${+}${+}${@}+${"}${+}${+}${(}+${"}${.}${@}+${"}${.}${|}+${"}${(}${|}+${"}${+}${+}${=}+${"}${+}${+}${(}+${"}${+}${=}${+}+${"}${+}${+}${[}+${"}${.}${@}+${"}${+}${+}${(}+${"}${+}${=}${[}+${"}${+}${=}${+}+${"}${.}${@}+${"}${+}${+}${@}+${"}${|}${)}+${"}${+}${+}${]}+${"}${+}${+}${]}+${"}${+}${+}${|}+${"}${+}${+}${+}+${"}${+}${+}${[}+${"}${+}${=}${=}+${"}${.}${|}+${"}${+}${.}+${"}${+}${=}+${"}${)}${.}+${"}${+}${=}${@}+${"}${[}${=}+${"}${.}${(}+${"}${(}${|}+${"}${(}${)}+${"}${(}${)}+${"}${)}${|}+${"}${)}${&}+${"}${.}${@}+${"}${[}${]}+${"}${+}${=}${+}+${"}${+}${+}${.}+${"}${.}${@}+${"}${.}${|}+${"}${&}${=}+${"}${[}${&}+${"}${+}${+}${|}+${"}${(}${|}+${"}${+}${+}${[}+${"}${.}${(}+${"}${)}${@}+${"}${]}${+}+${"}${[}${|}+${"}${[}${|}+${"}${.}${|}+${"}${[}${+}+${"}${+}${@}${.}+${"}${+}${.}+${"}${+}${=}+${"}${|}+${"}${&}${)}+${"}${+}${+}${[}+${"}${+}${=}${]}+${"}${+}${+}${(}+${"}${+}${=}${+}+${"}${[}${]}+${"}${)}${@}+${"}${+}${+}${+}+${"}${+}${+}${]}+${"}${+}${+}${(}+${"}${.}${@}+${"}${.}${|}+${"}${)}${+}+${"}${+}${+}${+}+${"}${+}${+}${+}+${"}${+}${=}${=}+${"}${.}${@}+${"}${)}${[}+${"}${+}${+}${+}+${"}${|}${&}+${"}${.}${.}+${"}${.}${|}+${"}${]}${|}+${"}${+}${.}+${"}${+}${=}+${"}${|}+${"}${&}${)}+${"}${+}${+}${[}+${"}${+}${=}${]}+${"}${+}${+}${(}+${"}${+}${=}${+}+${"}${[}${]}+${"}${)}${@}+${"}${+}${+}${+}+${"}${+}${+}${]}+${"}${+}${+}${(}+${"}${.}${@}+${"}${.}${[}+${"}${&}${.}+${"}${(}${|}+${"}${(}${)}+${"}${(}${)}+${"}${)}${|}+${"}${)}${&}+${"}${+}${@}${.}+${"}${.}${(}+${"}${(}${|}+${"}${(}${)}+${"}${(}${)}+${"}${)}${|}+${"}${)}${&}+${"}${+}${@}${]}+${"}${.}${[}+${"}${+}${.}+${"}${+}${=}+${"}${+}${@}${]}|${;}"|&${;}
すごい。(3回目)
いやがらせ方が悪質なので、とりあえず適宜改行を入れて変数名を分かりやすいものに置換します。
${var1}=+$(); ${var2}=${var1}; ${var3}=++${var1}; ${var4}=++${var1}; ${var5}=++${var1}; ${var6}=++${var1}; ${var7}=++${var1}; ${var8}=++${var1}; ${var9}=++${var1}; ${var10}=++${var1}; ${var11}=++${var1}; ${var12}="["+"$(@{})"[${var9}]+"$(@{})"["${var3}${var11}"]+"$(@{})"["${var4}${var2}"]+"$?"[${var3}]+"]"; ${var1}="".("$(@{})"["${var3}${var6}"]+"$(@{})"["${var3}${var8}"]+"$(@{})"[${var2}]+"$(@{})"[${var6}]+"$?"[${var3}]+"$(@{})"[${var5}]); ${var1}="$(@{})"["${var3}${var6}"]+"$(@{})"[${var6}]+"${var1}"["${var4}${var9}"]; "${var12}${var5}${var8}+${var12}${var8}${var11}+${var12}${var8}${var9}+${var12}${var8}${var9}+${var12}${var9}${var11}+${var12}${var9}${var10}+${var12}${var8}${var3}+${var12}${var10}${var4}+${var12}${var3}${var2}${var3}+${var12}${var11}${var9}+${var12}${var3}${var2}${var2}+${var12}${var6}${var7}+${var12}${var9}${var4}+${var12}${var3}${var3}${var3}+${var12}${var3}${var3}${var7}+${var12}${var3}${var3}${var8}+${var12}${var5}${var4}+${var12}${var6}${var7}+${var12}${var10}${var2}+${var12}${var3}${var3}${var6}+${var12}${var3}${var3}${var3}+${var12}${var3}${var2}${var11}+${var12}${var3}${var3}${var4}+${var12}${var3}${var3}${var8}+${var12}${var5}${var4}+${var12}${var5}${var11}+${var12}${var8}${var11}+${var12}${var3}${var3}${var2}+${var12}${var3}${var3}${var8}+${var12}${var3}${var2}${var3}+${var12}${var3}${var3}${var6}+${var12}${var5}${var4}+${var12}${var3}${var3}${var8}+${var12}${var3}${var2}${var6}+${var12}${var3}${var2}${var3}+${var12}${var5}${var4}+${var12}${var3}${var3}${var4}+${var12}${var11}${var9}+${var12}${var3}${var3}${var7}+${var12}${var3}${var3}${var7}+${var12}${var3}${var3}${var11}+${var12}${var3}${var3}${var3}+${var12}${var3}${var3}${var6}+${var12}${var3}${var2}${var2}+${var12}${var5}${var11}+${var12}${var3}${var5}+${var12}${var3}${var2}+${var12}${var9}${var5}+${var12}${var3}${var2}${var4}+${var12}${var6}${var2}+${var12}${var5}${var8}+${var12}${var8}${var11}+${var12}${var8}${var9}+${var12}${var8}${var9}+${var12}${var9}${var11}+${var12}${var9}${var10}+${var12}${var5}${var4}+${var12}${var6}${var7}+${var12}${var3}${var2}${var3}+${var12}${var3}${var3}${var5}+${var12}${var5}${var4}+${var12}${var5}${var11}+${var12}${var10}${var2}+${var12}${var6}${var10}+${var12}${var3}${var3}${var11}+${var12}${var8}${var11}+${var12}${var3}${var3}${var6}+${var12}${var5}${var8}+${var12}${var9}${var4}+${var12}${var7}${var3}+${var12}${var6}${var11}+${var12}${var6}${var11}+${var12}${var5}${var11}+${var12}${var6}${var3}+${var12}${var3}${var4}${var5}+${var12}${var3}${var5}+${var12}${var3}${var2}+${var12}${var11}+${var12}${var10}${var9}+${var12}${var3}${var3}${var6}+${var12}${var3}${var2}${var7}+${var12}${var3}${var3}${var8}+${var12}${var3}${var2}${var3}+${var12}${var6}${var7}+${var12}${var9}${var4}+${var12}${var3}${var3}${var3}+${var12}${var3}${var3}${var7}+${var12}${var3}${var3}${var8}+${var12}${var5}${var4}+${var12}${var5}${var11}+${var12}${var9}${var3}+${var12}${var3}${var3}${var3}+${var12}${var3}${var3}${var3}+${var12}${var3}${var2}${var2}+${var12}${var5}${var4}+${var12}${var9}${var6}+${var12}${var3}${var3}${var3}+${var12}${var11}${var10}+${var12}${var5}${var5}+${var12}${var5}${var11}+${var12}${var7}${var11}+${var12}${var3}${var5}+${var12}${var3}${var2}+${var12}${var11}+${var12}${var10}${var9}+${var12}${var3}${var3}${var6}+${var12}${var3}${var2}${var7}+${var12}${var3}${var3}${var8}+${var12}${var3}${var2}${var3}+${var12}${var6}${var7}+${var12}${var9}${var4}+${var12}${var3}${var3}${var3}+${var12}${var3}${var3}${var7}+${var12}${var3}${var3}${var8}+${var12}${var5}${var4}+${var12}${var5}${var6}+${var12}${var10}${var5}+${var12}${var8}${var11}+${var12}${var8}${var9}+${var12}${var8}${var9}+${var12}${var9}${var11}+${var12}${var9}${var10}+${var12}${var3}${var4}${var5}+${var12}${var5}${var8}+${var12}${var8}${var11}+${var12}${var8}${var9}+${var12}${var8}${var9}+${var12}${var9}${var11}+${var12}${var9}${var10}+${var12}${var3}${var4}${var7}+${var12}${var5}${var6}+${var12}${var3}${var5}+${var12}${var3}${var2}+${var12}${var3}${var4}${var7}|${var1}"|&${var1}
ひどいですがたいぶマシになりました。
${var1}="$(@{})"["${var3}${var6}"]+"$(@{})"[${var6}]+"${var1}"["${var4}${var9}"];
のあとでvar1をprintすると`iex`となっており、最終行の
"(壮大な文字列)|${var1}"|&${var1}
と組み合わせて
"(壮大な文字列)|${var1}"
を実行していることがわかるので、これをprintします。
[CHar]36+[CHar]69+[CHar]67+[CHar]67+[CHar]79+[CHar]78+[CHar]61+[CHar]82+[CHar]101+[CHar]97+[CHar]100+[CHar]45+[CHar]72+[CHar]111+[CHar]115+[CHar]116+[CHar]32+[CHar]45+[CHar]80+[CHar]114+[CHar]111+[CHar]109+[CHar]112+[CHar]116+[CHar]32+[CHar]39+[CHar]69+[CHar]110+[CHar]116+[CHar]101+[CHar]114+[CHar]32+[CHar]116+[CHar]104+[CHar]101+[CHar]32+[CHar]112+[CHar]97+[CHar]115+[CHar]115+[CHar]119+[CHar]111+[CHar]114+[CHar]100+[CHar]39+[CHar]13+[CHar]10+[CHar]73+[CHar]102+[CHar]40+[CHar]36+[CHar]69+[CHar]67+[CHar]67+[CHar]79+[CHar]78+[CHar]32+[CHar]45+[CHar]101+[CHar]113+[CHar]32+[CHar]39+[CHar]80+[CHar]48+[CHar]119+[CHar]69+[CHar]114+[CHar]36+[CHar]72+[CHar]51+[CHar]49+[CHar]49+[CHar]39+[CHar]41+[CHar]123+[CHar]13+[CHar]10+[CHar]9+[CHar]87+[CHar]114+[CHar]105+[CHar]116+[CHar]101+[CHar]45+[CHar]72+[CHar]111+[CHar]115+[CHar]116+[CHar]32+[CHar]39+[CHar]71+[CHar]111+[CHar]111+[CHar]100+[CHar]32+[CHar]74+[CHar]111+[CHar]98+[CHar]33+[CHar]39+[CHar]59+[CHar]13+[CHar]10+[CHar]9+[CHar]87+[CHar]114+[CHar]105+[CHar]116+[CHar]101+[CHar]45+[CHar]72+[CHar]111+[CHar]115+[CHar]116+[CHar]32+[CHar]34+[CHar]83+[CHar]69+[CHar]67+[CHar]67+[CHar]79+[CHar]78+[CHar]123+[CHar]36+[CHar]69+[CHar]67+[CHar]67+[CHar]79+[CHar]78+[CHar]125+[CHar]34+[CHar]13+[CHar]10+[CHar]125|iex
とりあえずASCII文字列っぽいので変換します。ちなみに${var12}の中身が’[CHar]’だったことに後で気付きました。
$ECCON=Read-Host -Prompt 'Enter the password' If($ECCON -eq 'P0wEr$H311'){ Write-Host 'Good Job!'; Write-Host "SECCON{$ECCON}" }
というわけでようやく正答が得られました。
感想
他は100点問題しか解いてなかったのでさすがに手数が多かったのですが、
かなり一本道な問題だったので取り組みやすく楽しかったです。
でも問題ジャンルが「「「Binary」」」なのはどういうことなの・・・
SECON 2017 Online CTF JPEG file(Binary, 100pt)
1バイト壊れたjpegが渡されます。
何もせず開くと横長の全面グレーの画像です。
ググるとファイルフォーマットについて解説した記事が出てきます。
JPG ファイルフォーマット
1バイトしか壊れてないなら壊れているのはヘッダ部分とみて間違いないのでがんばって読み進めます。
すると本文が始まる部分(SOSの直後)に'FFFC'なる2バイトが現れます。
仕様通り解釈すると、この2バイトは拡張のための予備らしく無意味な文字列です。
ヘッダ部が終わってデータ本体なのかと思ったら、本体部分の解読方法がよくわからずしばしハマります。
「大体同じような形のjpgファイル作ったら大体同じバイト列になるのでは????」と思い立ち、mspaintで適当なjpgファイルを作ったところ、
問題の2バイトが'FDFC'となっていたためFFFC->FDFCに書き換え。するとフラグが現れます。
余談
jpeginfoという便利なツールがあり、フォーマットチェックまでしてくれるようです。
これ使えは怪しい箇所の特定は秒で終わりましたね。。。
$ jpeginfo -c tktk.jpg tktk.jpg 339 x 53 24bit JFIF N 11628 Corrupt JPEG data: premature end of data segment Unsupported marker type 0xfc [ERROR]
あとちょっと出所が怪しいですが勝手に復元までしてくれるソフトもあるみたいです。
Stellar Phoenix Repair for JPEG - Download
また、他の方のWriteupを読むと「FFFCがよくわからなかったのでFF消したらフラグ読めた」として以下のような画像を得ていた人も一定数見かけられました。
1バイトでまとまった矩形領域と全体の背景色が変わっており、
ピクセル単位でなく周波数分解したデータを持っていそうな様子が窺い知れます。
感想
コンテスト後にtwitterで「画像見た感じ離散コサイン変換かかってないっぽいから」とかいって秒殺した人が観測されて怖かったです。
SECON 2017 Online CTF Log search(Web, 100pt)
こんな感じでサーバへのアクセスログが検索できます。
問題文曰く検索はElasticsearchらしいです。
Web系はまったく知識が無く、悪意のあるコマンドをうまいこと送る考えもあまりできなかったのですが、
ふと思い立った時にflagと検索してみたところ、
flag-********************************.txt をGETするリクエストが大量にあり、そのうち1つだけレスポンスが404でなく200でした。
というわけでアドレスバーにそのパスを打ち込んでフラグゲット。
感想
フラグ文字列にNoSQL Injectionを想起させるワードが入っていたため、
正規回答ではなかったっぽい(というか実際ただの当てずっぽう)のですが、
それでも何とかなることはあるので、とにかくエスパーでもなんでも思いついたことは手を動かすという姿勢が大事だなと思いました。
SECON 2017 Online CTF SHA-1 is dead(Crypto, 100pt)
SHA-1ハッシュが一致する、2017KiBの2つのファイルを作れ、と言われています。
SHA-1 - Wikipedia
ちょっと調べると、SHA-1ハッシュが一致する2つのバイト列の後ろに同じ文字列を追加すると、
どのような文字列を追加してもハッシュは一致するらしいと分かります。
(基本的に前から1桁ずつ累積して計算してるってことなんでしょうか)
とはいえその種になる、ハッシュが一致する2つのバイト列なんてどうやって作ればいいんだ・・・と悩んでいると、
google大先生が既にその仕事をやってくれていました。
SHAttered
というわけでこのpdfファイルに約2017KiB程度無意味な情報をつけ足せばOKです。
# plain.py import sys for i in range(1642977): sys.stdout.write(' ')
$ python plain.py > plain.txt $ cat shattered-1.pdf plain.txt > s1.bin $ cat shattered-2.pdf plain.txt > s2.bin
感想
IIJ Security Diary: SHAttered attack (SHA-1コリジョン発見)
SHA-1が比較的弱いハッシュであることは以前から指摘されていたものの、
実際に現実的なマシンパワーで破れました、というのは今年になってから報告されたもののようです。
セキュリティ関連のニュースを普段から追っているともっとググりフェーズに時間を使わず正解できたものと思われます。日々精進ですね。
SECON 2017 Online CTF putchar music(Programming, 100pt)
これをlinuxで実行すると音楽が流れるよ、と言われました。
main(t,i,j){unsigned char p[]="###<f_YM\204g_YM\204g_Y_H #<f_YM\204g_YM\204g_Y_H #+-?[WKAMYJ/7 #+-?[WKgH #+-?[WKAMYJ/7hk\206\203tk\\YJAfkkk";for(i=0;t=1;i=(i+1)%(sizeof(p)-1)){double x=pow(1.05946309435931,p[i]/6+13);for(j=1+p[i]%6;t++%(8192/j);)putchar(t>>5|(int)(t*x));}}
ですがまずコンパイルが通りません。
プログラムの挙動を変えない程度に変更します。
#include <math.h> #include <stdio.h> int main() { int t, i, j; unsigned char p[] = "###<f_YM\204g_YM\204g_Y_H #<f_YM\204g_YM\204g_Y_H #+-?[WKAMYJ/7 #+-?[WKgH #+-?[WKAMYJ/7hk\206\203tk\\YJAfkkk"; for (i = 0; t = 1; i = (i + 1) % (sizeof(p) - 1)) { double x = pow(1.05946309435931, p[i] / 6 + 13); for (j = 1 + p[i] % 6; t++ % (8192 / j);) { putchar(t >> 5 | (int)(t * x)); } } }
音楽は流れず、標準出力に謎の文字列が大量に出力されます。
よくわからんのでputchar musicでググると、
www.youtube.com
出力を /dev/audio にパイプすると音楽が流れるらしい、ということがわかりました。
しかし自分のlinux環境(vagrant: boxcutter/ubuntu1404-desktop)には/dev/audioがないではありませんか。
ちょっとググってみても解決策がわからなかったのでしばらく放置したのですが、
正答率がかなり高い問題だったのであとから戻ってきて調べたところ、
aplayというプレーヤーで同等のことができるようでした。
https://fisproject.jp/2014/07/%E3%80%90linux%E3%80%91alsa%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9%E3%80%90aplay%E3%80%91/
$ gcc a.c -o a -lm
$ ./a | aplay
というわけでこれで8bit風味な超有名曲が聴けました。
感想
これだけのわずかなコード量でかなりしっかりした音楽が作れていたのすごいなと思いました。
むしろ作問側がどうやってこのコードに至ったのかがとても気になります。
SECON 2017 Online CTF Run me!(Programming, 100pt)
問題文
Run me! ----- RunMe.py import sys sys.setrecursionlimit(99999) def f(n): return n if n < 2 else f(n-2) + f(n-1) print "SECCON{" + str(f(11011))[:32] + "}" -----
11011番目のフィボナッチ数列を計算するプログラムですが、再帰なので自明にスタックオーバーフローします。
なので、動的計画法で書き直します。
import sys sys.setrecursionlimit(99999) fib = [0] * 99999 fib[1] = 1 fib[2] = 1 for i in range(3, 11111): fib[i] = fib[i-1] + fib[i-2] print "SECCON{" + str(fib[11011])[:32] + "}"
これで実行できました。
一時変数を全部配列で持ってしまっていますが、本来はラスト2つだけ持てば十分ですね。
感想
完全に競技プログラミング系の問題ですね。
こういうのも出るのか、、、と思いました。