韓国の競技プログラミングの大学勢力によって調べてみよう！

こんにちは。リユナと申します。今日は韓国の競技プログラミングの世界で主に登場してる大学たちに紹介します！

0.概要

基本的にICPCは大学対抗戦であり、韓国のICPCの順位表とか見るときにどの大学がどんな特徴を持っているか、どんな感じかを知っていればもっと楽しいと思うので、今回はICPCによく出ている韓国の大学たちにポストします！あと、おまけで、今年の大学チームの名前の元ネタとかもちょっと説明してみます！

*大学の序列化などについては私も警戒していますので、客観的な事実と在学/卒業した何人かの有名な学生に対する感想と紹介だけを含めて、大学に対する主観的な判断はできる限り排除するように努力しますが、もしこの点で問題が生じたら申し訳ありません。紹介の順番は順位表の上からです。

下記のスコアボードはここで全て見られます！

2023ソウル大会の順位表です！

1. KAIST

まずは今年の優勝学校のKAISTですね。正式名称は韓国科学技術院である国立大学です。前にも言及したんですが、私の在学してる学校でもあります。

韓国ではほとんどソウルの中にある大学を高く評価する雰囲気が強いですが、その例外の一つである学校です。KAISTは大田(島根県じゃないですよ。「デジョン」って読みます。)に位置しています。大田は、韓国で色々な科学や工学研究所が密集している「大德研究開発特区」が位置している都市で、KAISTはその中にあります。

ICPCの伝統の強者で、毎年韓国大会でも1、2位を争います。 WFでも2017年銅メダルを獲得するなど、活躍しています。

だが、最近の成績はライバルでもあるソウル大学にはちょっと劣勢でしたが、この数年間IOIの韓国国家代表の学生たちがたくさん入ってきて国内大会1位を8年ぶりに獲得しました！(そのせいで私はセミファイナル出戦ができなくなったんですが😭)

出身の有名な競争プログラミング選手としてはBOJで何年間一位だった、今はMITにいるkoosagaさんがいますね。いま在学中の強者は2020年のICPCでほぼ満点を獲得して、今回の大会の優勝チームのエースであるgs18115さんとか、IOI金1銀1で、私たちのチームのエースでもあったSongCさんとかいます。

2. ソウル大学校/Seoul National University

(韓国では大学を普通大学校って呼びます。それで表記が混用されてるのでこの点、ご注意ください。)

韓国で一番有名な大学じゃないかって思います。まあもう説明することがあるでしょうかね。日本で言えば東大のポジションだと思います。名前通りソウルにある総合国立大学ですね。

数年間ICPCの優勝を独店していました。最近は(2022-2022)度合IOI3金1銀で三年連続で優勝チームになったFSMチームがやばかったんです。WFでも2021年、2022年二年連続で金メダルを獲得しました。怖いですね。

韓国のIOI国家代表の学生たちはほぼこの二つの学校に進学します。ちなみに、韓国のIOI国家代表はほとんどが京畿科学高校出身ですが、高校については別に説明する機会があれば追加で言及します。

3. 崇実(スンシル)大学校/Soongsil University

先ほどご紹介した二つの学校とは違い、聞いたことのない方々が多いと思います。 ソウルにある私立大学です。みんな大好きな北朝鮮の話をしようとすれば、歴史的にはこの学校、平壌にありました。韓国戦争以来韓国に南下して今はソウルにあります。ところで元々この学校があった位置には今は何があるのでしょうか？正解は、金日成総合大学です！

一昨年までWFに進出した事例はほとんどありませんでしたが、最近、いろいろな強者が入学し、特に競技プログラミングの実力者が入学できる入学特技者選考が充実しているため、韓国ICPCの浮上する強者といえる大学です。

今の代表的な有名な強者とすればBOJ四位でもあるJusticeHuiさんがいますね。今年の大会でももちろんあちらの「PS akgwi」チームのメンバーでした。その以外も錚々たる実力者がたくさんいる学校です。

チーム名である「PS akgwi」の元ネタについては後で説明いたします！

4. UNIST/Ulsan National Institute of Science and Technology

正式名称は蔚山科学技術院です。なんか英語でも漢字でもKAISTと似てますね。実は韓国には科学技術院が何個ありますが、その中の一つです。名前通り蔚山という都市にあります。釜山はしてる方が多いとは思いますが、あそこは釜山の真上です。工業都市です。個人的には日本にすると神戸のようなポジションかなと思います。

こちらも、2020年のWF出場を初めに最近浮上し始めた学校です。 何人かの情熱的な競技プログラマーが活発に活動したおかげで、内部サークルのようなコミュニティが多く活性化され、実力がますます上昇しています。

5. POSTECH/Pohang University of Science and Technology

過去の名称である浦項工科大学校でよく知られていますね。浦項は韓国の工業都市で、特に製鉄所が有名でその製鉄所の付設の大学です。浦項製鉄所は日韓(韓日)交渉当時の賠償と技術支援として建てられたことでも有名ですが、ある意味日本とも縁が多少ある学校だと言えますね。韓国の理工系大学ではソウル大学、KAISTと共にトップ3に挙げられていましたが、不思議なことに最近までは競技プログラミングがそれほど強くはありませんでした。最近だんだん競技プログラミングでも強くなっている学校です。

有名な競プロerなら日本のみんなにもよく知られていると思うhyperbolicさんがここの出身です。今回のチーム名にも元ネタがありますが、後で説明します。

6. 漢陽(ハニャン)大学校/Hanyang University

ソウルの私立大学です。漢陽はソウルの昔の名前です。まあ名付けセンスが武蔵野大学みたいですね。韓国内でも全体的に有名なところですが、特に工学部が有名です。まあこちらも最近数年間実力がどんどん増えて、受賞権を超えてWFも眺められる学校になりました。 実際、ここ数年のこの学校の順位を見ると、着実に少しずつ上がっているのが見られます！
ちなみに今回のOReOチームの場合、予選の時は5位以内に入る気炎を吐くこともあり、多くの注目を集めました。

7. 高麗(コリョ)大学校/Korea University

ソウルの私立大学で、韓国ではSKY(ソウル、高麗、延世)大学の一つで有名です。伝統的にICPCの強者として君臨した学校の一つです。2015年にはWFで銅メダルを獲得しました。

何で英語でKorea大学か疑問になるかもしれませんが、高麗は千年前に韓国にあった国家であり、Koreaという英語国名はそのKoryoから由来した名前だからです。

8. 西江(ソガン)大学校/Sogang University

こちらもソウルの私立大学です。競技プログラミングでは伝統の強者で、特記すべき点としては、BOJの開発者であるbaekjoonさんと、それと連動したサイトであるsolved.ac を開発したshiftpshさんの出身校です。 ある意味、韓国の競技プログラミング界に最も大きな影響を及ぼす学校とも言えますね。ちなみに今回のRedshiftチームのチーム名を見るとお気づきかもしれませんが、shiftpshさんが入っているチームです。

9.その他

Pusan National University(釜山大学校)、Kangwon National University(江原大学校)、Kyungpook National University(慶北大学校)は名前通り各々釜山、江原特別自治道, そして大邱にある国立大学です。特に、慶北大学は2020年のWFにも進出した隠れた強者大学です。

伝統的な強者大学の一人で延世(ヨンセ)大学校もありますね。ソウルの私立大学です。上の順位表にはないですが、2020年のWFにも進出したし、様々な有名ブロガーがいて、韓国では多くの人が競技プログラミングを準備する時、この学校の学生たちの記事を読んだりします。

10. 終えて

どうでしたか。いろんな大学の多くの学生が今でもICPCでもっと高い成績を収めるために一生懸命競技プログラミングをしていますが、この熱気が少しでも伝わってほしいです。

実はですね、数年前までは、ICPCの順位表はほぼソウル大一色に、KAISTがあと少し、そして下に下がると延世大と高麗大が少し見えるのが全部でした。いくつかの有名な学校の生徒だけのお祭りだったわけです。しかし、今は多くの学校で強者が続々と出てきており、競技プログラミングが最近になって大きく活性化され、色々な学校で多様なコミュニティができて上位圏に名前を上げる学校が多様化し、より熾烈な勝負が繰り広げられるようになりました。いくつかの学校が上位圏を独占しなくなった今を気に入らなかったり変な視線で見る場合もたまにあるようですが、私個人的には今のこのような版図がはるかに望ましいと思います。

読んでくださってありがとうございます！質問とかがあったら気軽にコメントで聞いてみてください！

11. おまけ！チーム名の元ネタを調べよう。

私の所属チームでもあるMunSongSongです。実は、韓国では「파송송 계란탁」(パソンソンゲランタク)って言う言葉があります。意味は「ネギざくざく卵ぱたぱた」で、インスタントラーメンに追加したらもっとおいしくなることを言う意味です。MunSongSongの発音が파송송を連想したため、チーム名がそうなったんです。Eggdropが「卵ぱたぱた」の部分でもあり、韓国にあるサンドイッチ店の名前でもあります。

PSは韓国で競技プログラミングを称する言葉です。「Problem Solving」のイニシャルですね。akgwiは韓国語で、漢字にしたら悪鬼ですね。その意味通りです。PS悪鬼というと、競技プログラミングにすべてが縛られて人生を失ってしまったり、卒業などが遅れたり、などの状況になった浪人を意味する言葉です。 実はWFのために卒業を先延ばしにすることを考えている私もPS悪鬼に含まれます

これはリーグオブレジェンドのプロリーグに関するネタです。Fakerで有名なSKT T1チームが2019年、国大戦史上最短の15分57秒で負けてしまったのでできたネタです。33-4の韓国版、またはLOL版ですね。

SKT T1も、阪神タイガースも今年優勝したのでめでたしめでたしかなと思ってます。

韓国で一番大きい法律事務所の名前です。私たちのように苗字で決められた名前でもあります。

shiftpshさんが所属しているチームで、英語そのままでは赤方偏移ですが、Redはレドコーダーの意味も含んでるし、まあ音ゲーの曲の名前の意味まで狙ったことでしっています。

残念ですね。

江原大学校のある江原道は韓国で一番山里というイメージで、ジャガイモ農業が有名です。Gamza Batって韓国語で「ジャガイモ畑」という意味です。

人を不快にさせるちょっと違ってるフィボナチの数列を狙ったチーム名です。

「틀딱」(トゥルタク)は韓国語で老人を卑下するスラングの一つであり、あえて老人でなくても年長者を表現することもあります。TLEは元々Time Limit Exceedの意味ですが、多分それはその表現を狙ったチーム名ですね。

韓国人はみんなニンニク好きですよね。実は韓国人、建国説話を見ると、熊が洞窟でニンニクだけを食べて人になった話が出てきます。 だから韓国人はニンニクを長い間食べないと熊に帰るのでニンニクをたくさん食べます。ww

Mad for Garlicという名前の料理店があります。fourじゃなくて三人だから3だそうです。

かつて高麗大学数学教育科だった作家が描いたウェブトゥーンには「I hate math」というTシャツを着た本人のオーナーキャラクターが出てきます。 それが原因で少し流行した言葉で、かなり長い間高麗大学には「I hate PS」というチームがありましたが、その後身のようです。

崇実大学校のとある有名な競プロerの名前がwookjeで、彼のブログのURLです。

SQL Injection。失敗したそうですね。

認めません。

済州大学校(Jeju National University)のある済州島はみかんで有名ですが、多分それの意味です。

韓国語で読めば「ヨンチャヨンチャ」ですが、「よいしょ！よいしょ！」の意味です。

パスワード、こう作っちゃだめですよ。

他にもいろんなネタがあったのですが、私が気づかなかったかもしれませんし、過去にも面白いチーム名がたくさんありましたが、全部紹介するには紙面が足りませんね。 ここまで読んでくださったら本当にありがとうございます！ もし日本のICPCの面白いチーム名があったら紹介してください！😊

それでは、また会いましょう！

北朝鮮の競プロとは？2016年ICPC平壌Regionalの問題を紹介します。

こんにちは。リユナと申します。今日は北朝鮮の競プロについて書きますね。

こんな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\le T\le 5$)である。

各々はまず一行で一つの整数N$(1\le N\le 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でなっている。$\left(1\le n\le 100,1\le N\le 100\right)$

次には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\le a,b\le 100,n\le 300000)$

a,bは上で説明した通りで、nは創作の回数である。

次のn個の行は三つの数"type L R"を含まれている。($1\le type\le 2$,LとRは実数)

出力は全ての創作1について結果を出さなきゃならない。小数点下の5桁から四捨五入して出力しなさい。

問題5. 易い幾何問題

時間制限:1秒
メモリ制限:32MB

ABCDは四面体で、DAの長さはa, DB=b, DC=c, あと$\angle$BDCはα, ∠ADC=β, ∠ADB=γだ。あなたはABCDの内接球の半径を計算すること。

数オリじゃない？

入力の一行はT($1\le T\le 100000)で、テストケースの数だ。$

毎テストケースは6個の数$a,b,c,\alpha ,\beta ,\gamma$ $(1\le a,b,c\le 100,0<\alpha ,\beta ,\gamma <360)を含まれている。$

$出力は小数点下の6桁から四捨五入した内線球の半径を出力しなさい。$

問題6. 最良の経路探し

時間制限:4秒
メモリ制限:256MB

ビト市はバイトランドの首都である。ビト市には現代的な高速道路があってその体系って頻繁に更新され，高速道路が体系に追加される。 その体系は交差点を結ぶ高速道路で構成されている。

運輸会社の社長であるあなたは、ある交差点から別の場所にコンピューターを輸送しようとしている。 ところが、バイトランドでガソリン価格が高すぎて、あなたは1台の貨物自動車だけで運ぼうとしている。 あなたはできるだけ多くのコンピューターを運ぼうとするが、すべての高速道路はW台以上のコンピューターは運べないという制限を持っている。

あなたは運べるコンピュータの最大値を計算しなければならない。 初期の高速道路システム上で任意の2つの交差点の間に移動することができる。 即ち、元のシステムはつながっている。

入力の一行ははテストケースの数T$(1\le T\le 3)でなっている。$

毎テストケースは交差点と道路の数を意味するNとMで始まる$(3\le N\le 70000,N-1\le M\le 150000)$

その次は、M個の行はaとbの間に道路があって、その道路の制限はcであることを意味する三つの整数a,b,cを含まれている。($1\le a,b\le N,1\le c\le 10000$)

その次には、質問の数を意味する整数Q$(1\le Q\le 105000)を含まれてある。全ての質問は二つの種類があって、$

1. a b c:　aとbの間に道路を連結してその制限はcである。

2. a b: aからbまで運べるコンピューターの数の最大値を計算せよ。$(1\le a,b\le N,1\le c\le 10000)$

ただし、二つの交差点を繋ぐ二つ、もしくはその以上の道路がある可能性もある。

この時、毎質問についてのコンピューターの最大数を出力せよ。

問題7. 良い日々

時間制限:1秒
メモリ制限:64MB

あなたは二つの日y/m/dとyy/mm/ddを入力させて、一つは初めての良い日であと一つは最後の良い日である。その間の全ての日々はよい日々で、その他はそうではない。あなたはよい日々の日数を計算するべきだ。

入力の一行はテストケースの数T$(1\le T\le 10000)でなってある。$

毎テストケースは6個の整数y, m, d, yy, mm, ddでなっている。$(1\le y,yy\le 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\le K\le 1000000000)だ。結果の文字列について、それに追加される文字数と結果になる文字列を空白で分かって出力せよ。$

問題9. 国際網奉仕

時間制限:1秒
メモリ制限:256MB

地球上には多数の網奉仕機*3たちがある。全ての数iについてi番目の網奉仕機は「半径」って呼ばれるR_iを持ってるので、網奉仕機は自分から離れた距離がR_i以下の全ての点まで奉仕できる。

一部の点は多い数の奉仕機から奉仕される。お前の課題は最大の網奉仕機から奉仕される点を探すのだ。

地球は6370の半径をもった球であり、その点たちの距離はエウクレイデス距離ではなくで表面上の距離である。

問題を易くするために網奉仕機たちの半径は2012から2016までに決まっている。

入力の一行ははテストケースの数T($(1\le T\le 6$)でなっている。毎入力の一行は奉仕機の数N$(1\le N\le 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\le N\le 100000)を含まれてますが、これは宝箱の数である。$

そしてN個の行がある。

p番目の行は三つの変数i a bを含まれている。これは宝石(p, t, a, b)を意味する。$(1\le t\le 1000000000,1\le a,b\le 1000000)ただし、どの二つの宝石も一緒に到着はしない。$

出力は、N個の整数を出力せよ。p番目の数はp番目の蓋に書く数字だ。

問題11. K番目のグラフ切断*4

時間制限:3秒
メモリ制限:256MB

ジソンはグラフ理論の勉強が好き。初めて彼は最小全域木を勉強した。そして彼は最短経路について学んだ。そして今はグラフの切断について勉強している。

重さのある有向のグラフ(つながれなかった可能性がある。)と源泉と目的地が与えられる。 言うまでもないが、源泉と目的地はグラフの一つの頂点だ。

あなたはグラフで源泉と目的地の間に何の経路もなくなるようにグラフから枝を消す。その時除去された枝の重さの和を「切断」って呼ぶ。

ジソンはもう一般的なグラフで最小切断が最大流量と同じであることを知っている。彼は今K番目の小さい最小切断について知りたい。彼はK番目の最小全域木とK番目の最短経路は計算できますが、K番目の最小切断はできない。彼を助けよう。

入力の一行は5個の整数N M K S Tを含まれている。

$N(1\le N\le 100)ーグラフの頂点の数$$M(1\le M\le 1000)$ーグラフの枝の数$K(1\le K\le 100)$$S(0\le S<N)$ー源泉の頂点番号問題の答えを出力せよ。もしなければ、-1を出力せよ。

問題12. 長い整数の因数分解

時間制限:1秒

メモリ制限:256MB

俺は整数がめっちゃ好きだが特に因数分解が好き。長い整数の因数分解って楽しけれどこれは難しい問題。俺の先生は俺に新しい因数分解の問題を与えた。

「整数Nがある場合、N^4+64を因数分解せよ。」

その初めで、俺はこれを二つの整数a, bの積で表せたい。もちろんaとbは一よりは多くて、N^4+64よりは小さい。俺はできるが忙しい。俺を助けるか？

入力の一行はテストケースの数T$(1\le T\le 10000)が含まれてる。$毎テストケースは一つの整数N$(1\le N\le 10000)を含んでる。$N^4+64=a*bを満たす整数a, bを出力せよ。色んなことができたら、その中で一つを出力せよ。

 

2. 翻訳後記・感想

問題ごとに話し方や形式が本当にまちまちで、きちんと定義されていない問題もあるのが少し気に入りませんでした。 これを日本語でもある程度反映しながら書こうとしましたが、うまくいったか分かりません。例えば、最後の問題だけ1人称が「俺」なんですが、この問題、言い方が以前までとは全く違って、命令調のタメ口だったんです。あと、網奉仕機もサーバーで翻訳しなくてそのまま書いてました。韓国では日本のようにサーバーって呼びます。何卒、北朝鮮語で書かれてある問題よ読んでいる韓国人が感じるえぐさ、みんなにもちょっとだけでも伝えたらいいなって思います。

採点できるところはないので、面白半分で読んでみてください。 以前は採点が可能なサイトがあったようですが、そこは今アクセスできず、他のところを探してみたのですが、ほとんど見つかりません。 おそらくBOJでもこれらの問題を載せることはないでしょうから、私は心の中であきらめました。

感想は···やっぱり数学の問題の比重がおかしいくらい高いという点が目にかかりますね。 もしソウルRegionalがあんな風に出ていたら、私は数学問題が得意だから、どうやら私たちのチームが優勝できたと思います。

 

あと最後に、数式のイメージファイルの使用を許可してくださったshiftpsh様に心より感謝申し上げます。読んでくださってありがとうございます！質問とかがあったら気軽にコメントで聞いてみてください！

*1:元の問題では「入力資料個数」で書かれてある。

*2:仲間という意味。北朝鮮でめっちゃ使われてるので、韓国人がその言葉を聴くと‘あれ？北朝鮮の人？’って思います。以下にもずっと出てるので、これだけはそのままで書きます。

*3:北朝鮮語でサーバー

*4:この問題の用語は原文を最大限生かしました。北朝鮮のえぐさをみんなで感じましょう。

韓国最大のオンラインジャッジサイトBOJとは？あと、solved.acとは？

こんにちは。リユナと申します。

今日は韓国の一番大きい競技プログラミング関連サイトであるBOJ(Baekjoon Online Judge)とそれに関しているsolved.acについて説明するポストを書いてみます。

このポストは有料広告が含まれたいです。 無料で書くものであり、ステマではありません。

2023 ICPC Seoul Regionalの参加後記

こんにちは。リユナと申します。

始める前に、私は韓国人の大学生で、今はKAIST（韓国科学技術院）で数学と電算学を専攻しています。翻訳機を使ってるのではありませんが、まだ日本語が完璧と言えるくらいではないので、ちょっとおかしい言葉とか文法的なミスが多いかもしれませんのでご了承ください.

0. ICPC Seoul Regionalとは？

全世界の大学生たちがそれぞれの競技プログラミング実力を誇る大会がICPCです。 World Finalという世界大会の予選格で、世界各地の地域別にregional contestがあり、例えば日本には横浜regional contestがあります。

もちろん韓国にもこのregional contestがあり、韓国のSeoul Regional Contestは当然韓国の首都であるソウルで開かれる大会…ではありません！実はソウルで行われません！ 高陽という、日本で言うと千葉くらいのポジションのソウルの衛星都市でおこなわれています。まあそれまでは理解できますが、その位置がなんと、

ソウルより北朝鮮にもっと近いのがやばいです🤣

まあそれで接近性も悪いし、チームのみんなが提出以後「これACできなかったら俺/私今から出て北行くよ！」とかジョークしたんですが、全員何かが間違ってしまって北朝鮮人になりました。

雑説はやめて、もう少し大会の説明をしますと、進め方はICPCスタイルで同じ大学の三人が一つのチームを組んでそれぞれのチームたちに与えられたパソコン一つで、与えられた問題に対する解決策を決められた時間内にできる限り多くプログラミングすることが目的の大会です。 これは韓国だけでなく日本の横浜regionalでもほぼ同じルールだと思います。 大会はオンラインで行われる予選と、（国境都市あたりに上がらなければならない）本選に分かれています。

1.チーム作り

私のチーム'MunSongSong Eggdrop'は去年から続いていたチームです。2022年にKAISTに競技プログラミングの上手い一年生が二人入って、休学を長くしてチームがなかった私は、彼らと一緒にチームを作ることにしました。チームメンバーの紹介をすると、

 mhy908: MunSongSongのMunです。私たちのチーム名は名字が各々Mun, Song, Songだったので作られたチーム名です。高校生の時APIOで銀賞をもらい、KOI(韓国情報オリンピック)で銀賞2個をもらいました。複雑な問題の観察とか幾何学の問題に特に強いです。

 SongC: MunSongSongのSongの一人です。韓国内で指折り数えられる競争プログラミング強者だと思います。 IOIで金賞1個、銀賞1個を受賞した華麗な経歴を持っています。全てに強いですが、特に変なデータ構造や誰もよく知らないアルゴリズムとかを全部しっています。

Eunha: MunSongSongのあと一人のSongです。私です。最年長者で紅一点でした。競プロの始まりは遅かったのでKOIで銅賞1個をもらったのが高校時代の全部ですが、大学大会への経験は比較的豊富です。本業は数学科なので数学的な問題に強いです。頭脳回転も悪くないので、解構築とか誠実の把握が必要な問題にも強いです。だが、全判的な競プロ能力は他の2人に比べては弱いです。

うまく組み合わせてチームワークが合えば、お互いの短所を補完できる良い組み合わせだと思ったし、実際に長い間同じチームで活動しながらだんだんチームワークが良くなりました。

2. 練習

普通に一週に一回を目指して練習しよう！とは言ったんですが、みんな忙しくてよくはできませんでした。主にBOJ(韓国のオンラインジャッジサイトです。)やcodeforcesで昔のICPCスタイルの大会の問題を時間を決めて本番の大会のように練習しました。

私たちのチームにはそれぞれの弱いところがたくさんあったので、改善のために次のように努力しました。

-皆が解はすぐに出てくるが、問題を組んでできない時にずっと掴んでいる場合が多い。

私も数学科であり、他の二人も高校時代まではOIをしてきたので、チーム大会への経験よりは自らが粘り強く問題を掘り下げていくスタイルにもっと慣れていました。ICPCでは、これがむしろチームメンバーのうち、他の人がキーボードを捕まえられないようにする毒になったため、誰かが長い間コンピュータをつかんでさまよっているなら、誰でもすぐにそれを中止させるルールを作りました。

あと、韓国語は普通に年上の人には親密度には関係なく敬語を使うのが普通ですが、水平的なコミュニケーションのために、皆がお互いにタメ口だけを使うことにしました。

-1問目でメンタルが壊れた始めると、すぐにスノーボールが転がっていく。

誰かがそんな悪循環に陥るとすぐコードをプリントして、キーボードから手を離せるようにしました。あと、私たちだけの規則を作ったんですが、プログラミングを始める前に、「何分かかるよ！」って宣言してその時間が過ぎたらすぐアウト！のようなチームの中の色々なルールを作って、かなり効果的でした。

こんなにチーム練習をしながら競プロ以外でも協力やチームワークなどについて色々と学ぶようになった気分でした。 これくらいなら後で履歴書に一行書いてもいいんじゃないかと思うくらいです(⁇)

3.予選

予選のスコアボードはこうです。私たちは４位をしました。序盤は凄まじく疾走しながら1位を続けていましたが、終盤で少しこじれて4位になりましたが、それでも満足的な成績で本選進出には何の問題もありませんでした。

4.本選

私たちの学校のある大田(デジョン)から高陽まで行くのが辛かったです。まずはソウルまでバスに乗って、まだここで電車に乗って、乗り換えて、そこでまだバスに乗ってまあ四時間くらいかかりました。KTXの駅も高陽には一つだけですが、実はその駅も大会場からはめっちゃ遠いし、ソウルを越えてそこまで上がるKTXの本数も1あまりなく、間に合いませんでした。

大会前日の問題セッティングのための例としては、去年の問題のうち簡単なものが3つ出てくるのが普通ですが、今回は珍しく去年1チームしか解けなかったCastle Designが出てきました。

当日の本選大会のタイムラインは大体こんな感じでした。

(0分)mhyが前の問題を、SongCが中の問題を、そして私が後ろを読みました。すぐ解けるのはまだ見えてきませんでしたが、Ｉはたぶん易い問題だし、Ｊは易くはないが私が専門と言えるスタイルの数学の問題のように見えました。

(7分)Iのファーストソルブが出ちゃいました。Iがかなり易いという結果がだし、SongCがIのプログラミングを始めました。

(23分)mhyはDの答えを出し、SongCがIを出して次々と正解になりました。あと、私はJを解いた！と思ってプログラミングしましたが、間違ってしまいました。

(37分)Jの初ソルブを奪われましたTT

mhyはあの時Cを出したが間違ってしまって、それから続いてく七転び八起きの始まりでした。

(45分)SongCがGを解きました。

(68分)SongCがHを解きました。

(その間)この時私のJ、mhyのCがそれぞれをいじめていました。 Jは一桁の場合、例外ケースをおかしくしたことに気づいて直しましたが、それでも間違って悔しかったです。 Cは考えれば考えるほど返礼ばかりたくさん出てくる不思議な問題でした。

(147分)SongCがFを解きました。あの時までは正にSongCのワンマンショーでしたね。

(その後)Bが考えよりは解けたので私とmhyがちょっと仕事を止めてBの問題の読み始めました。Bの問題はめっちゃやばいですが、Python-like pseudocodeだったのでPythonが母国語である私が解いて、具現にはセグ木が必要だったのでその部分だけはmhyに任せました。あと、キーボードが空いている間にJの検証コードを作りましたが、101、102のような中間に0が入った数字で問題が生じることを確認し、すぐにどこを直すか見つけました。 Jを直してBのコーディングを始めることにしました。

(176分)私がJを解きました。

(190分)私とmhyが一緒にBを解きました。この頃、スコアボードが閉じました。

(210分)SongCがKを提出して一度に当たりました。 おそらくファーストソルブだったと思います。 SongCは大会当時、パフォーマがすごかったです。

(240分頃)SongCはEはエイホ–コラシック法にすればいいと言い、これを始めました。 一方、mhyがコードをすべてやり直して新しく始めました。 私はLの解釈を出しましたが、プログラミングするにはもう遅い状態でした。

(280分頃)Eがエイホ–コラシック法に解けず、ハッシュをうまくやらなければならないことに気づき、時間不足に絶望しました。 mhyは完全にやり直したコードを提出しましたが、ついにCが正解でした！ ペナルティはたくさん貯まりましたが、それでも幸せでした。

(300分)大会が終了しました。

5.本選の後

大会が終わって他のチームに聞いてみたら、どうやらみんな何かこじれたようです。 上位チームにはJやCのような問題が足を引っ張るセットではないかと思います。 主催陣が「Cのような幾何問題でたくさん迷ったのですが、これから幾何をもっと出してはどうか」という衝撃的な発言をしてしまいました。

予想順位は昨年のように約7位でしたが、このように私たちの上に上がると思ったチームが予想とは裏腹に滑るところが多くて結局予選と同じ全体4位、校内2位で仕上げて銀賞を受賞しました！(あと賞金100万ウォンも！)

スコアボードはそんな感じです！

銀賞受賞は本当に嬉しいですし、キャリアハイというに値しますが、大会外では実は残念な部分もかなり多かったです。 全体優勝が同じ学校のチームであるPenguinsだったので、今回から適用されるルールによりますとRegional1位が出た学校は1位がWF直行、その他は校内1、2、3位がセミファイナルに行くというふうになったそうですよ。 それでPenguinsが1位になったので、私たちは学校2位にもかかわらずセミファイナルにさえ出る機会をもらえませんでした。 19年、22年に当時のルールだったらセミファイナル進出ができたので、なおさら残念でしたね。

いっそ希望がなかったらともかく、世界大会のチケットを目の前で逃した気分で、スコアボードの公開で台湾大学のstd_absチームがついにEを間違えて2位にとどまった瞬間、チームメンバー3人が絶叫しました。 世界大会進出のためには同じ学校の友達がいるチームが優勝できないことだけを祈らなければならないこの状況が本当にアイロニーでした。 どうか素晴らしいパフォーマンスで全体優勝を果たしたPenguinsチーム、心よりおめでとうございます！

とにかく一方では残念だったし、私とmhyの無冠行進を終わらせる絶好の機会は逃しましたが、それでも満足できる高い成果を得て嬉しいです！ 大会に参加した、そして運営に参加したすべての方々、本当にお疲れ様でした！

6.後は？

昨年のように「よっしゃー！このチームそのままだ！ 来年もよろしく！」という状況ではありません。 当初、私とすべてのチームメンバーは、私がこの大会を最後に引退すると思っていたので、それでMunSongSongで私の空いてる席に誰を入れるかをすでに決めておいた状態でした。 今になっては私が未練が残りすぎて卒業を延ばしてでももう一度参加しようかと悩んでいるところですが、一応既存チームを維持するのはかなり難しくなった状態です。

昨年は「来年成功できなくてもあまり落胆しないようにしています！」と書いたのですが、これが人の心が思い通りになればどんなに良いでしょうかww 実際にこんな状況になるととても未練が残ります。 むしろ最後をただ希望なしに終えたら未練もあまり残らないのに、目の前でチケットが飛んでいったような気分であまりにも残念で、このままでは競プロ悪鬼(主に韓国の競プロの人たちが、未練が残って束縛されてる浪人をこう呼びます。)になるのではないかと心配です。 何かに熱心に挑戦してだんだん成績が上がって成果が出て世界大会まで出るそんなロマンがあるじゃないですか？ 今引退してももう十分高いところまで来ましたが、残念な気持ちが残りそうです。 そういう意味で、もしかしたら自分の心の中で競プロが単なる問題解決以上に定着したのではないかと思います。 しかし、一方ではこのように結局メンタルだけが破裂して苦しんでいる場合もまた、こちらで多く目撃してきたので、私にとって最も良い選択が何なのかは依然として悩んでいる状態です。

とにかく、私が計算してみたら、驚くべきことに来年のICPCまでは出場可能なので、選択肢は次のように4つくらいあると思います。(韓国には普通男性の兵役があって、それではなくても大学生たちの休学が比較的に一般的なので、それのせいで他の国よりは二年の時間がもっと与えられる特例があります。)

1. きれいに未練を捨てて引退。
2. 色々な理由で解体する他のチームがあるので、校内のチーム員をよく集めて少なくともセミファイナルくらいは行ける戦力のチーム作り。
3. 大事にして育てた競プロ後輩たち2人が来年除隊して復学するので、彼ら2人を連れて行く。
4. 残りのチームメンバーに土下座して、無理矢理MunSongSongでもう一度出掛ける（？）

どんな選択をするかはたくさん悩みますし、私の人生で後悔のない良い選択をしたいので、どうしても簡単に終わる悩みではないと思います。が、どんな選択をしても、その選択で後悔のない結果を出せるように最善を尽くします！

最後に、この場を借りて2年間一緒に呼吸を合わせながら走ってきたSongC, mhy908に深く感謝したいと思います。 この素敵な二人の後輩たちのおかげで足りなかった私がたくさん学びながら大きく成長することができました。 競プロ以外でも2年余り同じチームを組んで目標に向かって一緒に走っていった経験は、これからの人生で本当に大切な経験になると思います。

私は心から、私の人生で最高の競プロチーム、いや、すべての分野をひっくるめて最高のチームがどこだったのかと聞くと、躊躇なくMunSongSong Eggdropだったと言えます。 来年、もし同じチームを成すことができなくても、尊敬する2人の後輩たちが必ずRegional優勝という夢を叶え、特にmhyが無冠脱出できることを心の奥底から願っています。 ありがとうございます。

7.問題たちの解き方

全ての問題は韓国のオンラインジャッジサイトであるBOJで解いてみます。AOJや他のジャッジサイトにはあるかどうかはよくわかりません。

A. Apricot Seeds

変なクエリ問題。特定された区間でバブルソートをするクエリが入って、その結果を出す問題です。大会場ではどのチームも解けなかったんです。解き方はちらりと通りすがりながら聞いたが、私の実力が足りないのかよく思い出せない。

B. Black Box

ICPCに出ても良いのかを悩んで見せる変な問題。まずはPython-like pseudocodeが来て、これの逆関数のように作動する関数を作れば良い。 大まかに言うと、シュードコードの作動方式は、まずリストが与えられた時、特定の規則に合わせてリストから元素を取り出してスタックに満たし、そのスタックから最初の項目と再び特定の規則から出てきた項目をswapすれば良い。

swapする規則はリストの最後の元素にかかっており、最後の元素はswapに変わらないことが保障され、一旦その規則に従って再び元素を2つ変えれば良い。 その後、元のリストで必ず最初の元素がスタックでも最初に入るという点から始め、規則を満たしながら入るためにはどの位置に何が入っていなければならないのかを逆追跡して探せば良い。 この時、「n個のマスの中で空いているマスの中で何番目の席」を探さなければならないため、セグメントツリーを通じて位置にどんな元素が入ってきたのかをアップデートしながら具現しなければならないのが最も具現難易度を上げる部分だ。

しかし、具現難易度よりは解釈難易度がはるかに高い。 マンゴーキウイアップルパパイヤバナナメロンココナッツライム··· コードを読んでいると気が遠くなる。

大体こんな感じです。

 C. Farm

幾何問題であり、私たちのチームは本当に苦労した問題だった。 座標圧縮をよくして、ずっと点をスイープしながら拡張できるところまで最大に拡張する方式ですれば、特に問題はないと言ったが、珍しい問題条件のために変な形の切れた多角形が発生する可能性があり、その場合、x軸の上に感染地が発生すると横一直線形のrectangular areaという珍しい事態が発生する可能性があり、この場合、例外処理を非常によくしなければならなかった。 しかも、このため大会中に質疑応答までしたが、yesと答えが返ってきて、かなり呆れた記憶がある。 私たちはy=-1のところから多角形が始まると仮定して解く方式にした。

D. Fraction

たぶん一番易い問題。かっこの文字列がvalidかどうか確認して、規則によって式を作って計算すればよい。私たちは規則に合わない場合に-1を出すのを忘れて一回間違った。

E. K-Lottery

手軌道にトライ木を作って、エイホ–コラシック法、、、ではなくロリハらしい。fail functionの管理について、ちょっとテクニックが必要な感じでムズイだったそう。文字列は私も弱いので、解き方を聞いたけどよく覚えてない😥

F. Lucky Draws

前から点を描くとしたら動的計画法でできそう。だが、naiveにしたらO(kN^2)という時間なので、関数のmonge誠実を探して最適化すればO(NklogN)で解けるらしい。

G. Magic Cards

実は数字が５０万までだから、1から５０万まですべての数字に対して記録したらいいです。

H. M.S.I.S.

最適に構築していれば、すべての列に対して上か下かは使用されることが分かる。 二つのうち一つ使うものを選んで位置に合わせて入れればいいという。 ここで重要な部分は、両方とも使われるものをどのようにうまく選ぶかですが、上の列に対して整列してD[i][j]=i番目まで選択、下の列から最後に選んだものはj。 という風にして点火式をうまく構築すればn^2に解けて、n=10000なのでギリギリ回るという。

I. Product Delivery

貪欲法。特に説明することもない。以上。

J. Special Numbers

digit DPっていうスタイルの問題。今までのICPCのKorea Regionalではメージャーではなかったんですが、今回に出た。

私の解き方は、f(n,k,zero)を「０からｎまでの数字の中でK-specialなことの数。zeroがTrueならばleading zeroを考える。」って定義した。あと、n の最初の桁をあらかじめ抜いておき、それが 0 のときから n の最初の桁になるまでfor文を回しながら再帰を回すようにした。 例えば、4940までの数字の中で12-specialであるのがいくつあるかを見るには、まず0から999までのうち12-specialなものの個数を数え、次に1000から1999の中で12-specialの個数を数えるが、このときはf(999, 12, True)で入れる。 これは0を0ではなく000と見て、1も1ではなく001と見て··· 同じ感じで、0をかけるといつもすべての数の倍数になるという点をうまく処理するためだ。 その次には2000から2999までの中で「6special」の数を数えなければならないが、千の位に2が入るという仮定の下で残りを数えることだからだ。 このようにメモイゼーションを伴う再帰を回せば、思ったより回る数字は大体限定的なので、時間内にとても余裕を持って帰った。

K. Tandem Copy

SongCが「うへへへ」しながら(本人によると)解いた。文字列のdpだが、変なケースがたくさんあるらしい。

L. Walk Swapping

解説は導き出したが、時間がなくて具現もできなかった問題。 これは解かないといけなかったのに···という物足りなさが残ることの一つだった。

結局、左に行って右に行く<<をすれば以前と変わることが一つもないので、ずっと左に行く/ずっと右に行くという2つの場合しか存在しない。 すると、数字一つを掴んでその子をずっと一マスずつ移動させる感じで、一周すると数列を一マスずつ左/右にシフトさせたのだ。

一旦可能かどうかを見るには、数列文字列を適当にロリハし、すべてのnに対してn番目の数を回してあれが出るかどうかを判断する方式で見て、可能であれば可能な場合に対して左まっすぐ/右まっすぐで施行回数のうちどれがもっと小さいのか、それをずっと見る方式で解けば良い。 という結論が出たが解けなかった。 実はそれで検証もできなかった。

 

この記事は前に韓国語に書いた 2023 ICPC Seoul Regional 본선 후기を適当に変形して翻訳したことです。もし韓国語ができたらあっちも見てくださったら嬉しいと思います。😉