ふーらくたるの雑の記

雑な事を記していくなど

ゆるふわ競技プログラミングオンサイト参加記

2019年2月9日にFORCIA, Inc.さんで開かれた「ゆるふわ競技プログラミングオンサイト」に参加してきました。
普段の企業コンとは違い、看板に偽り無しの(いい意味で)ゆるふわなオンサイトでした。
せっかくなので久しぶりの参加記を書いていこうと思います。

コンテスト前

開始時間が14:00からと、競プロerに優しい開始時間だったので無事起床することができました。
せっかくの「ゆるふわ」コンテストなので、とりあえず会場に向かうまでの間にお酒を買ってみました。
もちろんコンテスト中に解けなくて冷えた時に、お酒を飲んで体をあっためるためです。


普段の企業コンのオンサイトだと、コンテストの結果が就職に影響してきたり、そもそもみんなが真剣にやっているのでとてもお酒を飲めるムードではないという問題があり、なかなか難しいです。
こういったことが許されるのも、こういうオンサイトならではなのかなと思ったり*1。

当日雪が降ると言われていましたが、何事もなく会場に着くことができました。
どうでもいいのですが、僕はFORCIAさんの夏のインターンに申し込んで無事落とされているので、会場をみた瞬間精神的に冷え始めてもう酒開けてやろうかって思いましたがなんとか踏みとどまることができました。

コンテスト

さあコンテストだ！と、行きたいところなのですが、なぜか開始時間になってもコンテストページ(HackerRank)が開けません。
他の世間一般のイベントだったら運営の方も焦っていてもおかしくないと思うのですが、某ロシアのコンテストのせいか、コンテスタントも運営の方も「おいおいおいおいw」みたいになっていて面白かったです(ちゃんと対応はしてくださっていました)。
結局、新しくコンテストを作り直すことで無事コンテストが始まりました。

問題
www.hackerrank.com

1問目 B式A+B

bとBを使って表された2進数の数同士の和を計算して、答えをbとBを使った2進数の表記に直して出力せよ、という問題です。
コンテストで見たときは愚直に実装する方法しか思いつかなかったので、「ゆるふわとは…」という気持ちになっていました。
後で教えていただきましたが、bとBを1と0に直してからPythonのint(s, 2)を使えば一瞬で解けますね…

2問目 集合写真

1問目とは違って軽めの実装やるだけ問題。

3問目 線香

GCDするだけなのでGCDやりました。

4問目 最短経路は何本ありますか

題の通り、最短経路を数え上げる問題です。
個人的に最短経路の数え上げdpに思い入れがありまして、懐かしいなあと思いながらダイクストラを書いていました。

5問目 ガソリンスタンド

経路復元してくださいという問題です。
経路が一意に定まっているので、適当にBFSしました。

6問目

5問目を解き終わった時点で1ページ目にいて、結構ほかほかだったので、冷えた時に飲むはずだったお酒を飲むことにしました。
念願の飲酒オンサイトです。
さて6問目ですが、木が入力として与えられるので、各頂点について、他の頂点までの距離の和を求めてくださいという問題です。
とりあず全方位木DPっぽいのでうしさんのブログ記事を開きます。
あまり全方位木DPの経験がないので、うーんって言いながら頑張って紙に考察を整理していました。
さて、ここで一つ罠があったのですが、先ほど飲んだお酒が回ってきて何もわからなくなってきます。
慣れていない問題を解く前にお酒を飲むのはやめましょうね。冷えます。
考察を3回ぐらいやり直してようやくAC。

7問目

ミスったなあなんて思いながら開いてみたらセグ木貼るだけの問題が出てきてびっくりします。

8問目

ラスボス問です。
とりあえず中間点に相当する左下からどうにかするんだろうとは思って、点素パスを求める+制約が小さいというのを見て「フローっぽいなあ」なんて思います。
今思うと意味不明なのですが、「でも終点が2つあるからフローじゃ解けないや」って思って却下。
そのままぐるぐる迷走してたらコンテストが終わっていました。
あとなんかolpheが優勝していました。

コンテスト後、懇親会

僕がバチャコンに勝手に参加して、勝手に冷えている縁でJoeさんに話しかけていただいたり、ドワコンで隣の席だったこるとんさんと久しぶりに話したり、my3さんとhotpepsiさんのマラソンのお話しに耳を傾けたり、アイコンが大好きなhatooさんや、貪欲さんから社会人のお話を聞いたりしていました(受動的な行動ばっかりですね😇)。
後olpheと今夜の日経コン頑張って色変えようぜみたいな話をしていました(有言実行さすがすぎる)。
最後の方に運営のmatsu7874さんに、問題作りの大変さを聞いて、やっぱりコンテスタントとして参加したいなぁなんて思っていたら時間になっていました。
あと気づいたらピザがなくなっていました。誰か無限枚食べてないか。

感想

やっぱりオンサイトはいいですね。
特に普段なかなか会えない人とお話しできるというのは、このゆるふわ競技プログラミングオンサイトならではの魅力だと思います(DDCCとかだと人が多すぎて会えないし、通るのが難しいコンテストだと、それはそれで会える確率が少なくなるので)。
後、これが個人的にはとても嬉しかったのですが、順位を気にせず純粋に競技プログラミングの「問題を解く楽しさ」を味わうことができました。
次回も開催してくださったら嬉しいな。あ、でも懇親会のピザはもっと多い方が嬉しいです。

ところで僕は20卒で絶賛就職先募集中なので、FORCIAさんもしよかったら^^

*1:これ勝手に僕が許されたと思っているだけなので、許されてなかったらウケる

ICPCアジア地区予選つくば大会2017参加記

参加記 ICPCアジア地区予選つくば大会2017

12月17日(日)に開催されたICPCつくば大会にnishiyon NO DANPENのチームメンバーとして参加して9位をとってきました。
参加記を書くまでがオンサイトと聞いたので参加記を書きます。

チームメンバー

チームメンバーはfemto(@femto16)さん、conf(@confused_uec)、僕(@fooractal)で、コーチがtshitaさんです。
ICPCが開催された日のメンバーのAtCoderレートはfemtoさんが2216、confが2001、僕が1882です。僕だけ青なので肩身がせまいですね…

1日目(12月16日)

JAXA見学

エクスカーションとしてJAXAに見学に行くことになっていたので早起きしてつくばへ向かいます。つくばエクスプレスに乗ってつくばに行ったのですが、会場入りする前から競プロerっぽい方々を何度か見かけて徐々に気持ちが高まって来ます。

JAXAに着いてからは、僕は宇宙兄弟が好きなので、「あ、これ宇宙兄弟で見たやつだ!」みたいにずっとテンションが上がっていました。写真をいっぱい撮りたかったのですが、悪意のあるふぁぼ爆によりスマホの充電が切れてしまい、あまり写真を撮ることができませんでした。あとこのとき農工大のnokoTaroさんに軽く挨拶します。お土産には宇宙食とスペースクッキーを買いました。

リハーサル

写真を撮られたり、英字キーボードに慣れるために最小全域有向木のライブラリを写経したり、TLの人に挨拶しに行ったり、tuboさんとちょくちょく目があったりしていました。

懇親会

食べ物が美味しかった(小並感)。チーム紹介がありましたが、僕が世界一マイクを使うのが下手なのでチームリーダーのfemtoさんが話すことになりました。輪郭の断片 is unknown object。

懇親会が終わった後は宿に直行しました。お腹が空いたのでお土産の宇宙食を食べた後すぐに寝ました。

2日目(12月17日)

清々しい朝です。ホテルの朝食も美味しくて最高の気分で会場に向かいます。とりあえず6完することを目標にコンテスト開始の時を待ちます。

コンテスト

とうとうコンテスト開始です。femtoさんが色々セッティングしている間に僕とconfで問題文を読みます。AがDPで解けるとすぐ気づいたので「AでDP…?」って思いながら実装します。初のアジア地区予選で緊張していたのか、配列外参照をして無限にバグらせますがなんとかAC。

その後confがBの実装をしたり、femtoさんがCの考察をしているのを横に問題文を読んでいきます。EはなんかAtCoderで見たことありそうな問題感がすごかったのですが、わからなかったのでパス。Fが割と手をつけやすそうな雰囲気を出しているグラフ問題だったので、頑張ってFを考察します。

弧を反転させることで最短路の長さが短くなる場合はすぐ解けましたが、その他の場合にどうすればいいかわからずしばらく悩みます。ここらへんでconfがBを通します。その後femtoさんが最短経路木上で考えればいいとおっしゃったのをヒントに、橋を検出できれば勝てそうということを思いつきます。あいにく橋検出のライブラリを持っていなかったのですが、ダイクストラすれば橋を検出できそうだと気づいたのでとりあえず実装します。僕がバグらせてる間にfemtoさんがCをAC。手があいたfemtoさんと一緒にペアプロをします。一瞬でバグが見つかります。投げます。AC。

この時点ですでにGとIの考察が終わっていたらしく(ガチプロ)、後2問通そう!ってなります。femtoさんが残り1時間ぐらいでIを通します。残り30分ぐらいでconfがGを通します。6完目標達成です。やったぜ。あとはEとKの考察をしたり、凍結された順位表を眺めたりしていました。

解説・表彰式

ただでさえわからない競プロの解説を英語でやられて何もわからなくなっていました。
そして順位発表もとい表彰式です。存在だけは知っていた生yesnoおじさんと順位発表の盛り上がりにおおーってなってました。順位ですが、なんと9位!!ちゃんと調べていませんが、過去の電通大のアジア予選の順位の中では多分2位タイのはずです(1位と2位は電通大がWFに出た年です)。

表彰式後のご飯

おいしかった。農工大の方々やつたじろうさん、こうきさん、こうりんさん、らてあさんと話したりします。あと9位になったのでKLabさんからニンテンドークラシックミニ スーパーファミコンをいただきます。このときfemtoさんがめっちゃテンション上がっていました。そしてついに…

やりました。念願のサインです。

ほんとうに想像していた以上の嬉しいことがいっぱい起こって、最高のICPCとなりました。

3日目(12月18日)

Indeedに見学に行けることになっていましたが、集合時刻から1時間ぐらい遅刻して到着します。社内見学には間に合ったので色々見て回ります。色々設備も充実していて、将来こういうところに入れたらいいだろうなぁなんてぼんやり思っていました。

そのあとICPCのお金でお昼ご飯をいただきます。このとき前に座っていらっしゃったalpha_virginisさんやこうきさん、らてあさん、去年のJAG夏合宿で同部屋だったoyasさんとお話しします。oyasさんに「強くなりましたね」って言われたのが嬉しかったです。
そして午後から5限があったので、午後のLINEのオフィスツアーに行かずにお昼ご飯だけ食べて帰るやつをしました。

なお、帰ろうとしたところ京王線が止まっていたため結局5限遅刻しました。

総括

最高でした。femtoさんが引退されてしまうのでnishiyon NO DANPENは今年で解散です。話してくださった方々、ICPCを開催してくださった方々、そしてnishiyon NO DANPENの皆様、本当にありがとうございました。

CODE THANKS FESTIVAL2017参加記

参加記 CODE THANKS FESTIVAL2017

12月2日(土)に開催されたCODE THANKS FESTIVAL2017に参加してきました。頑張って思い出しながら書いていくのでよろしくお願いします。

前日

TIkeさん主催のボドゲ会参加者の皆さんと合流するため品川までいきました。品川の港南口でTIkeさん、つたじろうさん、こうきさん、竹雄さん、らてあさん、フェリンさんに挨拶したあと、お腹空きましたねということでロイヤルホストの方へ。席が空くまでの待ち時間では、らてあさんにゼロ距離ふぁぼ爆を食らったり、2人でTreeoneさんに並列ふぁぼ爆をしたり、ついでにこたつがめさんにふぁぼ爆をしたりして時間を潰していました(ごめんなさい><)。注文したのはオムライスでしたが、注文する際、僕の声が小さすぎて店員さんに何回か聞き返されてWAを食らってました(今思えばこれはフラグだったのかも…)。オムライスはすごい美味しかったです。

食べ終わった後は解散して家に帰りました。普段は生活リズム崩壊勢なのですが、前日ということで早めに就寝。

当日

参加するまでフェーズ

早く寝たかいあって無事起床することができました。

ここで一つ罠にはまってしまったのですが、早く起きすぎたために余裕かましてTwitterをやってたら時間ギリギリになったので焦って家を出ることになります。

道中同じくTLEしそうなShinya Katoさんの焦っている様子を見てニヤニヤしていました。

そしてここでもう一つ罠があって、Twitterをやりすぎてしまったが故にスマホの充電が切れてしまいました。それだけなら別に大したことはないのですが、さんくすの会場をメモしてなかったので(は?)、駅に着いたのに会場がどこだかわからないという事態に陥ります。会場名のSuffixが「MONO」ということは記憶していたので、駅員さんに「この近くになんとかMONOっていう施設ありませんか!?」って聞いたら「は?」って言われて終わりました。悲しいね。

うろちょろしててもしょうがないので、とりあえずオタクっぽい人の流れに着いて行こうとしたりしていましたが(最悪)、目がついていないので見失って失敗しました。途方に暮れてましたが、突然自分がPCを持って来ているということに気づきます。近くにWi-fiスポットがあったので、無事会場の情報を得ることができました。この時点ですでにギリギリ。急いで会場に向かったらまだ開会式は始まっていなかったらしく、なんとか間に合うことができました。やったぜ。

ちなみにKatoさんは遅刻してたみたいで笑いました。

会場入りフェーズ

無事到着したので、会場でTシャツを貰いました!去年のこどふぇすは当日風邪で休んでしまったため、1年ごしのゲットとなり非常に感慨深かったです。早速着ようとしましたが、セーターの上からだときつくて入らなかったのでそのまま放置してました(それはそう)。そのままお弁当と僕の大好物のカントリーマアムを回収してコンテストに備えます。


コンテストフェーズ

code-thanks-festival-2017.contest.atcoder.jp
12:00から3:00までの3時間コンテストでした。

A問題
問題文を読んでソートするだけだと気づいたので実装して提出しました。12:02AC。

B問題
制約が小さいことを確認して、C++で文字列扱うの面倒臭いなあって思いながら全探索して通しました。12:06AC。

C問題
見た瞬間優先度付きキューを用いた貪欲法で解けると思ったので頑張って実装しました。12:12AC。

D問題
問題文を読んでmin { kn mod m | k ∈ N}を求めればいいことに気づきます。5分ぐらい考えて全く解法を思いつかなかったので、「300点だし、適当にkn mod mの重複が出るまでkを探索してやれば解けるだろ!w」と甘い考えのもと実装して提出します。当然のごとくTLE。ここで問題文をもう一度じっと睨んで見ると急に頭の中にgcdという単語が浮かんで来ます。頭の中で証明もどきをして、サンプルもあうことを確認したので実装してみます。しかしgcdをしばらく書いていなかったので、2分ぐらいバグらせます。何が間違っているかわからなかったのでネットで"gcd 再帰"って検索しました(ひどい…)。提出して見たら無事通りました!12:38AC。ここら辺ではじめて順位表を見ますが、意外と自分が悪くない順位にいることに気づきます。

E問題(1回目)
10分ぐらい偶奇を用いた考察をしていましたが、全く解ける気配がないのでパス。400点むずかしい。

F問題
太字で書かれたいかにも怪しげな制約から、DPをしても状態数がそんなに多くならないと思います。ペナルティもなしだし、とりあえず出してみるかと、mapに状態を突っ込んで行く素直なdpを書いたら通ってしまって「えぇ…」ってなってました(コンテスト後にTLの方のツイートで気づきましたが、これ嘘解法ですね…)。12:51AC。

G問題
制約を見て半分全列挙ができそうということに気づきます。前半分と後ろ半分でvalidな集合かどうかを判定するのは、bitを使えばできそう。問題はマージするところだけど、これもあらかじめbit DPで前計算しておけばO(1)でマージすることができそう、と思い頑張って実装します。サンプルがあったので祈る気持ちで提出。AC。この時点でパーカー獲得が決定してガッツポーズします。ここで順位表を見たら2位に僕の名前があって、おいおいおいってなってました。13:26AC。

H問題(1回目)
問題文からUnion-findを使いそうだとぼんやり感じます。逆操作を考えて見たりしましたが、うまい方法が思いつかなかったのでとりあえず平方分割+Union-findのシミュレーションを実装して投げて見たらTLE。自分には手に負えなさそうということでE問題に再チャレンジします。

E問題(2回目)
問題文をじっと睨んでたら「50/10って5だなー」と頭に浮かんで来ます。5種類の袋から取り出すコインの枚数をバラバラに決めて、各コインの重さを未知数とする方程式を解けばなんかコインの種類を特定できそう?=>実装してみるか=>AC! ここら辺からもしかして賞金狙えるんでは?なんてことを思い始めます。14:27AC。

H問題(2回目)
永続Union-findがあれば二分探索で解けるなーと気づきます。頑張って永続Union-findを検索しますが、全然検索に引っかからなかったのでモニターに向かって中指を立ててました(隣に座っていた方、いきなり隣の奴が中指を立てたことで驚かせてしまったのなら申し訳ありません)。それでも諦めずに検索してるとD言語を用いて実装されていた方のブログ記事が出て来ます(URLは後で貼ります)。D言語の言語仕様をぐぐりながら少しだけ直します。=>AC ABCとyukicoderを除けば人生初の全完だったので、思いっきりガッツポーズしてました。この時点で残り3分程度。14:56

表彰式、懇親会フェーズ

コンテストが終わった後、TLの人々と話しました(記憶力が鶏並なので時系列がごちゃごちゃになってるかもしれません…すみません…)。 ボドゲ会の人々や、去年のJAG夏合宿で同部屋だったoyasさん、全然残り一問を解き終わらない自宅番兵さんとお話しすることができました。こうきさんにはクソみたいな解法の説明をしてしまい、反省しております…。

一通り皆さんと話した後、表彰式がありました。なんとコンテスト前は考えもできなかった5位に入賞することができました。5000円です。やったぜ。


ただ、どうやら僕のid(fooractal)は可読性が著しく低いらしく、司会の方に何度か読み方をSubmitされましたが、全部WAでした。で、表彰されるということは何かしらの感想をみなさんの前で言わなければなりません。僕はこの手の人前に出て何かを喋るということが世界一苦手なのですが、勇気を出して必死に考えた内容を話そうとしました。しかし、僕が話し始めた瞬間、僕の周囲が突如真空状態になり、発した声が皆様の元に届くことが物理的に不可能になってしまいました。聞けば感動間違いなしの名スピーチであったと確信しておりますが、皆様の元にお届けすることができなくて非常に残念でした。ちなみに僕が話し終わったあとは真空じゃなくなりました。

現場にいたKatoさんの声


そのあとはchokudaiさんの解説を聞いた後、コネクションハントをやったり、ご飯を食べたりしながらTLの皆さんと交流していました。この時去年からずっと会いたかったゼオスさんや、Treeoneさんともお話しすることができました。あとご飯は寿司とかピザとかでてきていっぱい食べました。美味しかったです(小並感)。皆さんと喋ったあとは席に座って、後ろの席の竹雄さんとずっと喋っていました。帰り際に前の席のrunomさんともお話しできて、大満足のオンサイトでした。

感想

本当に、最高に楽しかったです。競プロをやる上での夢の一つだった「賞金をとる」という夢まで叶ってしまい、本当に言葉がありません。5位という結果は完全にまぐれなので、頑張って精進して、今度は実力で賞金を得られるように修行していきたいです。

最後に、話してくださった方々、そしてCODE THANKS FESTIVALを開いてくださった方々、本当にありがとうございました!!!!

AOJ2732 - Modern Announce Network

AOJ グラフ問題 最短経路問題 最小シュタイナー木問題

問題

Modern Announce Network | Aizu Online Judge

解法

入力より生徒を頂点、コネクションを重み1の辺とするグラフを構築することができます。このようにして得られたグラフから、さらに各学年の生徒を一つの頂点にまとめたグラフ G = (V, E)を考えます。あらかじめネットワークを構築しておけば、スタートとなる頂点は任意に選べることから、解くべき問題は今まとめた3個の頂点をターミナル集合 Tとする最小シュタイナー木問題となります。最小シュタイナー木問題はNP困難な問題であることが知られていますが、今回はターミナルが3つであることから多項式時間解法が存在します。

証明は省略しますがターミナルが3つの場合、最小シュタイナー木はパスグラフまたはY字型のグラフにしかなり得ません。よって各ターミナル t \in Tについて、 tを始点、( tから vまでの距離、経路中の最小の頂点番号)を値とする最短経路を求めます。そして各頂点 v \in Vに対して、各ターミナルからの距離の和と、含みうる頂点番号の最小値を計算します。この中で最適なものが解となります。

ソースコード

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

using P = pair<int, int>; // (距離，パス上の最小頂点id)
using PPI = pair<P, int>;

const int inf = 1 << 28;

int N, A, B, C;

P cost[3][20000];
vector<int> G[20000];
int old_id[20000]; // 変換後のグラフG'の頂点v'に対応する元の頂点v

void dijkstra(int s) {
    for (int v = 0; v < N; v++) {
        cost[s][v] = {inf, inf};
    }

    cost[s][s] = {0, old_id[s]};

    priority_queue<PPI, vector<PPI>, greater<PPI>> Q;
    Q.push({{0, old_id[s]}, s});
    while (!Q.empty()) {
        auto q = Q.top();
        Q.pop();
        P val = q.first;
        int v = q.second;

        if (cost[s][v] < val) {
            continue;
        }

        for (int to : G[v]) {
            P nval = make_pair(val.first + 1, min(val.second, old_id[to]));
            if (cost[s][to] > nval) {
                cost[s][to] = nval;
                Q.push({nval, to});
            }
        }
    }
}

int main() {
    static int num[3];
    cin >> N;
    for (int i = 0; i < 3; i++) {
        cin >> num[i];
    }
    static int min_id[3] = {inf, inf, inf};

    static int group[20000];
    memset(group, -1, sizeof(group));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < num[i]; j++) {
            int x;
            cin >> x;
            x--;
            group[x] = i;
            min_id[i] = min(min_id[i], x);
        }
    }
    map<int, int> mp;
    int id = 3;

    for (int i = 0; i < 3; i++) {
        old_id[i] = min_id[i];
    }

    for (int v = 0; v < N; v++) {
        if (0 <= group[v] and group[v] < 3)
            mp[v] = group[v];
        else {
            mp[v] = id++;
            old_id[mp[v]] = v;
        }
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;

        G[mp[x]].emplace_back(mp[y]);
        G[mp[y]].emplace_back(mp[x]);
    }

    // Dijkstra
    for (int s = 0; s < 3; s++) {
        dijkstra(s);
    }

    P ans = {inf, inf};
    for (int v = 0; v < id; v++) {
        ans = min(ans, {cost[0][v].first + cost[1][v].first + cost[2][v].first,
                        min({cost[0][v].second, cost[1][v].second,
                             cost[2][v].second})});
    }
    cout << ans.first << " " << ans.second + 1 << endl;

    return 0;
}

感想

某企画の4問目です。femtoさんとペアプロしながら通しました。三点を結ぶ最小ネットワークの構築する問題としてはARC019C - 最後の森があります。

雑の記

雑記

DTM(DeskTopMusic)を始めてみたいと思ったので、Mac標準の音楽ソフトであるところのGarageBandをダウンロードしました。無料だけど割と高機能らしい。よきかなよきかな。登録するのが面倒ですが、Studio oneのPrime版も無料でかつなかなか性能が良いらしいです。そのうちゲーム音楽みたいなのを作れるようになるのが理想ですけど、たぶん無理なのでしばらくはおもちゃ感覚で付き合っていくつもりです。というか寝て起きたら飽きてそう(ア
参考になりそうなページ
dtm-hyper.com
www.riyu-haru.com
dtm.55-52.com
dtm-beginner.me

後代数学をさらっと学ぼうと思った時にお世話になりそうなページを見つけてきました。
ufcpp.net
こういった代数学関連のあれこれはセグメントツリーや行列累乗を深く使うにあたって避けられない事だと思うのでしっかり勉強しておかなきゃいけませんね…

【追記】代数学のページだどこっちの方が詳しそうです。
login - [物理のかぎしっぽ]


後広義明日からは『中学生からの数学オリンピック』も読み進めようと思います(INF回言ってる…)

Codeforces #426(Div. 2) C - The Meaningless Game

Codeforces 数学的問題

問題

codeforces.com

SlastyonaとPushokがヒントなしの数当てゲームをしている。数当てゲームは0回以上のラウンドからなっており、各プレイヤーは最初、得点として1が与えられている。各ラウンドごとに当てなければならない数 kが与えられ、そのラウンドの勝者の得点はk^2倍、敗者の得点はk倍されることになる。n個の得点の組(a, b)が与えられるので、その組が各ゲームの最終結果としてありうるかどうかを判定せよ。

続きを読む