こんにちは。リユナと申します。今日は北朝鮮の競プロについて書きますね。
こんなICPCは嫌！
0.概要
始める前に、標記について言及しておきます。普通韓国では北朝鮮のことを「北韓」だと呼びます。韓国の北側っていう意味で、北側の政権を正式的に認定しない態度が入ってますね。このような呼び方は同じ漢字文化圏ではあと台湾などで使われているらしいです。私のももちろん「北韓」って呼ぶのが慣れてます。
しかし、日本では「北朝鮮」と呼ぶことがはるかに多いようでした。 日本政府側も北韓政権を認めていないと思いますが、理由がかなり気になりますね。 とにかく、この文を読む皆さんは「北朝鮮」という表記の方がずっと慣れていると思いますので、便宜上こう呼びます。
前のポストの北朝鮮ジョーク、みんな好きだったらしいで日本のみんなは北朝鮮が大好き？！って思いました。(笑)私たちにとっては、ある意味同じ国の一部であり、また唯一国境に面した国ですが、全く分からない未知の世界なのが北朝鮮です。まあミサイル発射と挑発と暴言が特技のようです。
そんな北朝鮮でも、なんと競技プログラミングをします！ さらに、その実力も決して低いレベルではないということですが、2019年のICPC World Finalでは北朝鮮の金策工科大学のチームが全体8位で、ソウル大学の真下の順位に入り、銀メダルを獲得しています。
当然北朝鮮の予選である平壌Regionalがありますが、問題たちはほとんど公開されてないので、しかも採点できる所はなさそうです。しかし、2016年の問題だけは何故か韓国のウェッブに広がってるので、今回にみんなにご紹介いたします！
参考で、北朝鮮語と韓国の標準語はほとんど違いがないのですが、政治的だったり軍事的な感じの単語がよく含まれていて、科学技術用語の場合は翻訳が違うことがかなりあり、韓国人にとってはこの部分が非常に面白く感じられるポイントなのですが、皆さんに翻訳させていただいて、これをうまく生かせず、あらかじめ残念で申し訳ないとお伝えします。
驚いたことに、当時の平壌大会の映像はユーチューブで見ることができます。 共有したいのですが、韓国人である私がこれを共有することで法律的な問題が生じる可能性があるかもしれませんので、お手数ですが、直接探していただければ幸いです。
まあ入場曲がコンギョだったり賞品がミサイルだったりはしませんが、大会が始まる前に、彼らの「敬愛する最高領導師」の銅像に皆が献花する姿は本当に気持ち悪かったです。ww
あと蛇足で、この大会以降WFがアメリカで行われましたので、北朝鮮政府側からは強制的に書類不備を起こし、当時優勝チームがWF失格になったという非常に北朝鮮らしい噂があります。
それでは、始めます！
1.問題
問題1. 配列転倒数
時間制限:1秒
メモリ制限:64MB
あなたたちは皆配列の転倒数について知っているだろう。ハンミン君は聡明で今新しい転倒数を思っている。
もしiとjの奇偶が一致して、i<j、そしてa_i>a_jならば彼は(i, j)を反転されたことで思う。その一方で、奇遇が違ってa_i<a_jだったらこれも反転されたことと思う。
あなたはハンミン君のずっともでこの新たな転倒数を計算することに関して頼まれた。あなたは解けるのでしょうか。
入力はまずテストケース*1の数T(1≤T≤5)である。
各々はまず一行で一つの整数N(1≤N≤5000)を含まれているが、あれは配列の長さだ。
次の行にはN個の実数が空白で分けれ入る。
出力：あなたは全てのテストケースについて一行で反転を打つ。
問題2. B＿N
時間制限:1秒
メモリ制限:128MB
聡明な学生リ・ギウンは物理が得意だが数学は下手だ。彼のドンム*2シン・ヨンジンは反対に数学が得意です物理が苦手だ。それでリドンムはシンドンムの物理の課題をやって、シンドンムはリドンムの数学課題をやってくれる。
今日はリドンムがとても難しい数学の問題を持って来てシンドンムに聞いた。だが、シンドンムはめちゃくちゃ忙しくて彼はあなたにこれを解くことを頼んだ。あなたはシンドンムのずっともで、必ずこれを解かなきゃだめだ。その問題はこれだ。
配列{A_1, A_2, ... , A_n}がある。新しい配列{B_1, ..., B_n}はこう定義されている。
uとvが違う場合i_u=i_vも可能だ。実際にB_3=A_1*A_1*A_1+A_1*A_2+A_2*A_1+A_3だ。あなたは必ずこのNについてB_Nを計算しなきゃだめだ。
あなたは彼らを助けてくれるのか？
おい自分の宿題は自分でやれこのバカドンムめ！
入力の一行はテストケースの数Tでなっている。
毎ケースの一行は二つの整数nとNでなっている。(1≤n≤100,1≤N≤100)
次にはn個の整数が空白で分かれて入る。
出力：問題の結果を出力せよ。
問題3. 行列検査
時間制限:1秒
メモリ制限:512MB
ジョン教授は第４１次国大大学生プログラムアジア平壌地域競演問題出題者である。彼は１００組の2016*1946行列の1946*2016行列の掛け算を終わったばかりです。もちろん結果は2016*2016の行列である。計算は10日かかった。結果は１００組で実はこの問題の入出力資料になったはずだ。
パソコン使ってよおいpolygonとか使ってよあんた教授でしょう？電気不足かい？
その後ジョン教授は眠りに落ちてしまい、彼の息子が結果に手を出した。彼はある一つの数字の一桁を消して「１」を書き出した。
明日ジョン教授は本当に怒った。しかし息子の子はたった二歳で何も覚えてない。
ジョン教授は息子の言葉を聞いて検査を始める。息子は組の一つの桁を変化させ、その数字が2,0,1,6のうちの一つであることを分かった。そして彼は息子が変化させた位置が行番号と列番号が７０以下であることを知った。行列の左上が(1,1)である。
彼は入出力を今日伝送するべきだ。だから、彼は結果を検査するとした。あなたは彼の優秀な学生であり、彼を助けなさい。
バックアップじゃんとしておいてよ北朝鮮これでいいのか？
入力は１００組の入出力資料でできている。毎組はこうなっている。
一行は5個の整数a_1, a_2, a_3, a_4, a_5である。あなたはこうして行列Aが製作できる。
次の行は5個の整数b_1, b_2, b_3, b_4, b_5である。あなたはこうして行列Bが製作できる。
その次は70*70の整数の行列がある。あなたが検査することはこれである。
あなたは二つの行列の掛け算をする時に必ず2016011010で割った余りをとる。
出力：あなたはどの組が息子によって変化したのかを出力する。入力の番号は1から100だとする。もしかして全ての入力組が変化してなかったら０を出力してよ。
われらは入力と出力の例えが多すぎて見せてくれない。あなたがその形式を担保しなければならない。
無責任すぎるじゃないか？おい！
(実はこの問題の意味、私もよくは理解してません。だって入出力も出てないし、どんな感じかよく分かりません。)
問題4. リンゴ配り
時間制限:8秒
メモリ制限:512MB
ヒョンイル君は道徳のある学生だ。彼はいつも彼の学級ドンムたちと友達を自分自身のようにしてくれる。ある日、彼は美味しくて大きいリンゴを持って来て彼の友達に配ろうとしている。興味深い所は、このリンゴが楕円形だということだ。
彼はいつも2つの操作を行う。
創作1はリンゴのLからR角度の間の残りの面積を計算することだ。
創作2はLからR角度の間のすべてのリンゴの粒を与えることだ。
ヒョンイル君はリンゴを
デカルト座表計(直交座標系)に置き、結果リンゴは楕円x2/a2+y2/b2=1に位置している。
ヒョンイル君の兄であるあなたは幼い弟の計算能力を試そうとするが、あなたはすべての質問に必ず答えなければならない。
できるかな？ できる。
ああ、 もう一つの条件があるが、prevは最後に出力された数であり、実際のLとRは次の公式によって計算される。
もしL>Rの場合あなたは二つの値を変えなければならない。あなたはL_real, R_realの二つで計算しなきゃならない。初めにprevは０だ。
入力の一行は三つの整数を含まれている。a, b, そしてnだ。(1≤a,b≤100,n≤300000)
a,bは上で説明した通りで、nは創作の回数である。
次のn個の行は三つの数"type L R"を含まれている。(1≤type≤2,LとRは実数)
出力は全ての創作1について結果を出さなきゃならない。小数点下の5桁から四捨五入して出力しなさい。
問題5. 易い幾何問題
時間制限:1秒
メモリ制限:32MB
ABCDは四面体で、DAの長さはa, DB=b, DC=c, あと∠BDCはα, ∠ADC=β, ∠ADB=γだ。あなたはABCDの内接球の半径を計算すること。
数オリじゃない？
入力の一行はT(1≤T≤100000)で、テストケースの数だ。
毎テストケースは6個の数a,b,c,α,β,γ (1≤a,b,c≤100,0<α,β,γ<360)を含まれている。
出力は小数点下の6桁から四捨五入した内線球の半径を出力しなさい。
問題6. 最良の経路探し
時間制限:4秒
メモリ制限:256MB
ビト市はバイトランドの首都である。ビト市には現代的な高速道路があってその体系って頻繁に更新され，高速道路が体系に追加される。 その体系は交差点を結ぶ高速道路で構成されている。
運輸会社の社長であるあなたは、ある交差点から別の場所にコンピューターを輸送しようとしている。 ところが、バイトランドでガソリン価格が高すぎて、あなたは1台の
貨物自動車だけで運ぼうとしている。 あなたはできるだけ多くのコンピューターを運ぼうとするが、すべての高速道路はW台以上のコンピューターは運べないという制限を持っている。
あなたは運べるコンピュータの最大値を計算しなければならない。 初期の高速道路システム上で任意の2つの交差点の間に移動することができる。 即ち、元のシステムはつながっている。
入力の一行ははテストケースの数T(1≤T≤3)でなっている。
毎テストケースは交差点と道路の数を意味するNとMで始まる(3≤N≤70000, N−1≤M≤150000)
その次は、M個の行はaとbの間に道路があって、その道路の制限はcであることを意味する三つの整数a,b,cを含まれている。(1≤a,b≤N,1≤c≤10000)
その次には、質問の数を意味する整数Q(1≤Q≤105000)を含まれてある。全ての質問は二つの種類があって、
1. a b c: aとbの間に道路を連結してその制限はcである。
2. a b: aからbまで運べるコンピューターの数の最大値を計算せよ。(1≤a,b≤N, 1≤c≤10000)
ただし、二つの交差点を繋ぐ二つ、もしくはその以上の道路がある可能性もある。
この時、毎質問についてのコンピューターの最大数を出力せよ。
問題7. 良い日々
時間制限:1秒
メモリ制限:64MB
あなたは二つの日y/m/dとyy/mm/ddを入力させて、一つは初めての良い日であと一つは最後の良い日である。その間の全ての日々はよい日々で、その他はそうではない。あなたはよい日々の日数を計算するべきだ。
入力の一行はテストケースの数T(1≤T≤10000)でなってある。
毎テストケースは6個の整数y, m, d, yy, mm, ddでなっている。(1≤y,yy≤5000)
その時、いい日の日数を出力せよ。
ちょっと待って。1から5000年までならユリウス暦からグレゴール暦に移るのはいつに反映すればいいの？ そんなこと一つも教えずに問題を解けと言われたらどうするの？
問題8. ヒョソンとクァンソン
時間制限:1秒
メモリ制限:256MB
ローマ字でなっている長い文字列Sがある。二人の少年。ヒョソンとクァンソンは面白い競技をやる。その規則はこうなっている。
初期に審判員のハ
クミョンが彼らに空いていないSの部分文字列を与える。(私たちはそれをPPで表示しよう。) 2人の競技者は交代で後ろに1つの文字を追加して新しくできた文字列がSの部分文字列になるようにする。 もし彼らが文字を追加できなければ、試合は終わる。
ヒョソン君は最後の文字列ができる限り短くしたいが、クァンソン君はできる限り長くしたい。ゲームはヒョソン君から始まる。もし彼らが最適でゲームをしたら私たちは毎文字列に追加される文字の数を推測できる。それをf(P)としよう。
部分文字列Aはもしf(A)<f(B)であるが、f(A)=f(B)でAがBより辞書順で前なら部分文字列Bより小さいって定義する。
与えられた整数Kについて、文字列SのK番目の小さい文字列を探しなさい。探せるか？
入力の一行は一つの文字列になってるがその長さは500000以下である。
二番目の行は一つの整数Ｋ(1≤K≤1000000000)だ。結果の文字列について、それに追加される文字数と結果になる文字列を空白で分かって出力せよ。
問題9. 国際網奉仕
時間制限:1秒
メモリ制限:256MB
地球上には多数の網奉仕機*3たちがある。全ての数iについてi番目の網奉仕機は「半径」って呼ばれるR_iを持ってるので、網奉仕機は自分から離れた距離がR_i以下の全ての点まで奉仕できる。
一部の点は多い数の奉仕機から奉仕される。お前の課題は最大の網奉仕機から奉仕される点を探すのだ。
地球は6370の半径をもった球であり、その点たちの距離はエウクレイデス距離ではなくで表面上の距離である。
問題を易くするために網奉仕機たちの半径は2012から2016までに決まっている。
入力の一行ははテストケースの数T((1≤T≤6)でなっている。毎入力の一行は奉仕機の数N(1≤N≤1000)を含まれている。
そして、次のN行は奉仕機の軽度、緯度、半径を表す三つの整数を含まれている。(0≤経度< 360、-90<緯度<90)
問題10. 宝箱
時間制限:3秒
メモリ制限:256MB
ソンヨンはどんな数学問題でもめっちゃ早く解ける。彼の兄のチェ・ガンは高い宝石を保管できるN個の宝箱を持っている。
ある日、チェが宝石店からN個の宝石を持ってきた。 買ってきたじゃなくて？！チェはすべての宝石を1箱に1個ずつ入れる。 言い換えれば，彼は1つの宝石を店頭に保管するだけだ。
すべての宝石は4つの数を持っているが、保管番号p、筒に到着する時間t、そして2つの値aとbを持つ。 (p,t,a,b)について説明をしよう。
宝石(p,t,a,b)が到着すれば、チェはすでに到着した宝石の中から最もよく結合される宝石を見つけなければならない。 最もよく結合される宝石(p1,t1,a1,b1)は、次の条件を満たさなければならない。
1. その宝石は必ず新しい宝石より早く塗着するべきだ。即ちt1<t.
2. あれの箱の番号はpより小さいはずだ。即ちp1<p.
3. 結合効果が最大になることを選ぶ。それはa1*a+b1*bで定義する。
そしてチェはあの箱の蓋に宝石たちの結合効果を書くとする。だから、チェはソンヨンに毎箱の蓋に数を計算して書くことを頼んだ。ソンヨンを助けようと。
入力の一行はは整数N(1≤N≤100000)を含まれてますが、これは宝箱の数である。
そしてN個の行がある。
p番目の行は三つの変数i a bを含まれている。これは宝石(p, t, a, b)を意味する。(1≤t≤1000000000,1≤a,b≤1000000)ただし、どの二つの宝石も一緒に到着はしない。
出力は、N個の整数を出力せよ。p番目の数はp番目の蓋に書く数字だ。
問題11. K番目のグラフ切断*4
時間制限:3秒
メモリ制限:256MB
ジソンは
グラフ理論の勉強が好き。初めて彼は
最小全域木を勉強した。そして彼は最短経路について学んだ。そして今はグラフの切断について勉強している。
重さのある有向のグラフ(つながれなかった可能性がある。)と源泉と目的地が与えられる。 言うまでもないが、源泉と目的地はグラフの一つの頂点だ。
あなたはグラフで源泉と目的地の間に何の経路もなくなるようにグラフから枝を消す。その時除去された枝の重さの和を「切断」って呼ぶ。
ジソンはもう一般的なグラフで最小切断が最大流量と同じであることを知っている。彼は今K番目の小さい最小切断について知りたい。彼はK番目の
最小全域木とK番目の最短経路は計算できますが、K番目の最小切断はできない。彼を助けよう。
入力の一行は5個の整数N M K S Tを含まれている。
N(1≤N≤100)ーグラフの頂点の数M(1≤M≤1000)ーグラフの枝の数
K(1≤K≤100)S(0≤S<N)ー源泉の頂点番号
T(0≤T<N S)ー目的地の頂点番号問題の答えを出力せよ。もしなければ、-1を出力せよ。
問題12. 長い整数の因数分解
時間制限:1秒
メモリ制限:256MB
俺は整数がめっちゃ好きだが特に
因数分解が好き。長い整数の
因数分解って楽しけれどこれは難しい問題。俺の先生は俺に新しい
因数分解の問題を与えた。
「整数Nがある場合、N^4+64を
因数分解せよ。」
その初めで、俺はこれを二つの整数a, bの積で表せたい。もちろんaとbは一よりは多くて、N^4+64よりは小さい。俺はできるが忙しい。俺を助けるか？
入力の一行はテストケースの数T(1≤T≤10000)が含まれてる。毎テストケースは一つの整数N(1≤N≤10000)を含んでる。N^4+64=a*bを満たす整数a, bを出力せよ。色んなことができたら、その中で一つを出力せよ。
2. 翻訳後記・感想
問題ごとに話し方や形式が本当にまちまちで、きちんと定義されていない問題もあるのが少し気に入りませんでした。 これを日本語でもある程度反映しながら書こうとしましたが、うまくいったか分かりません。例えば、最後の問題だけ1人称が「俺」なんですが、この問題、言い方が以前までとは全く違って、命令調のタメ口だったんです。あと、網奉仕機もサーバーで翻訳しなくてそのまま書いてました。韓国では日本のようにサーバーって呼びます。何卒、
北朝鮮語で書かれてある問題よ読んでいる韓国人が感じるえぐさ、みんなにもちょっとだけでも伝えたらいいなって思います。
採点できるところはないので、面白半分で読んでみてください。 以前は採点が可能なサイトがあったようですが、そこは今アクセスできず、他のところを探してみたのですが、ほとんど見つかりません。 おそらくBOJでもこれらの問題を載せることはないでしょうから、私は心の中であきらめました。
感想は···やっぱり数学の問題の比重がおかしいくらい高いという点が目にかかりますね。 もしソウルRegionalがあんな風に出ていたら、私は数学問題が得意だから、どうやら私たちのチームが優勝できたと思います。
あと最後に、数式のイメージファイルの使用を許可してくださったshiftpsh様に心より感謝申し上げます。読んでくださってありがとうございます！質問とかがあったら気軽にコメントで聞いてみてください！
