ICPC2019国内参加記 team_YARUDAKE編

初めまして!二年生のkuroku(でんそん)です。サークルのブログをはじめて執筆するのでどんな雰囲気で書けばいいかいまいちわかりませんが、先日行われたICPC国内予選の感想などを伝えられたらなと思います!

我々の先輩方の参加記(Tech_ONS編)もあるのでそちらも合わせてご覧ください!

(ブログ慣れてないのでリンクとか参考とかはTech_ONS編から飛ぶか自分で調べて!)

チーム概要

そもそもチームについてなんですが、他の有名つよつよ大学に比べてうちの大学の競プロer人口が少ないです(それはそう

なので、チームを組むにあたってはサークル内のゲーム制作ニキ(AtCoderにはお触り済み)たちに声をかけて一緒に出てもらうことになりました。

いっちーさん、まんじゅうくんありがとうございました。

準備としては国内模擬の際の1完でやばいと感じつつ、全探索とグラフのおべんきょをがんばったつもりでした(つもりね

国内予選当日

1コマ目の授業が監督の先生の授業だったので終了後挨拶に行って、リハーサルを一通りやって昼食、一つ授業を挟んで14:30にガナリヤさんと同着で会場入り。

なんとなく早く来たものの、普段VisualStudioの設定はそのままでやっているので環境構築RTAの練習もせず、1完はやだなぁとか考えていました。

そんなこんなで16:30になり、コンテストが始まりました。ほとんどのチームはA、Bあたりは分担して解くと思いますが、自分たちのチームはとりあえず3人で1問解こうみたいな感じの方針でした。

A問題は苦戦することなくAC(列が生徒だったのが少し気持ち悪かったですが(転置とったらどーですか

B問題は現在の座標を持って二重ループを回し、始点と終点のマンハッタン距離を測っていきました。しかしサンプルケースの答えが合わずインデックスがずれたか見てると、決定ボタンを押した回数も答えに入れるよと教えてもらい提出。実行時に9sくらいかかってたけど無視して提出したらACでした。

C問題に取り掛かり、mの制約をみて全探索っぺぇ~と思いながら考察へ。見立て通り分銅は「左に乗せる」、「右に乗せる」、「乗せない」の3通りしかないのでO(3^m)だとわかったのですが実装ができん(あれ、全探索。。。

30分くらい詰まったのでいったんDを見に行って、「これ、AtC●derでやったとこだ!」と思いつつよくわかりませんでした。順位表を見てもCを飛ばしてDをACしているチームは少なかったのでまたCに戻って頭を悩ましていました。

長いようで長かった3時間が過ぎ、初めてのICPC国内予選は2完という結果でした。感想としては全探索がしっかりかければ3完できそうだなぁっていうのと、チームでコンテストに参加するのはたのしいってところでしょうか。

今回の後日談(まとめ)

最近競プロ以外のことに目移りしまくりでしたが、ICPCはモチベ上昇にもなってもっと精進したいと思いました。

コンテスト終了後にガナリヤさんにC問題を教えていただいて、そういう勉強会的なのも面白いと思います。(もっと競プロerが増えればやってもいいねっておっしゃっていたのでもっと増えてどうぞ

ぼく個人の目標は今年中にAtCoder水色になることで、来年のICPCでは4完したいですね。(なお今のratingは…

まんじゅうくんも前回のABCでC問題を解けていたので来年は水色行けるでしょ(鼻ほじ←C解けなかったやつ

後輩たちにもどんどん競プロでハラス布教して勉強会できるくらいの人を集めてみたいですね。

来年のICPCに向けていろんな希望をもったところでこの記事を締めたいと思います。

以上、kurokuでした~!(文字だらけでごめんね!

新入生へ:TNPにはどんな人がいるのか

やっぱり気になると思う点

はいほー!どうもでったーです。

先輩(ガナリヤさん)がブログをじゃんじゃん書いてくれと大義名分っぽいことを宣言してくれたので元来書き物と自分語り(違う)を得意とする僕が今回も新入生ガイドライン的な感じで
「TNPにはどんな先輩がいるんだろう・・」という疑問に勝手に答えていきたいと思います

断言します。ここはオタクの止まり木です

「いやそんなこと言うなよ」って声を上げる部員もいるかもしれませんがこのサークルで交わされるプログラミング以外の会話の大半はオタクジャンルの話ですしネットスラングも多数飛び交います。(オタク以外来るなって意味では決してありません)

このサークルは創作活動だけでなくオタクという志を持った人たちと繋がる、という意味でも機能してるのかなぁという風に(少なくとも僕は)考えています。それを僕はタイトルにある「止まり木」という表現をするわけです。

どんなジャンルのオタクがいるか

TNP、正直多種多様なオタクがいます。一般的なオタクジャンルは大体履修してる人がいるはずです。(一般的の尺度が微妙なので確証は持てませんが)

今のところVtuber系に強い人が多少多めかなーって程度です。(ちなみに僕の履修ジャンルはアイマスなんでプログラミングやりたいプロデューサーがいたら是非来てほしいなぁと思っています。)

好きなゲームジャンルも色々です。上の年代は格ゲー中心ですが僕らの年代なんかはもうバラバラです。今流行りのゲームなんかの話題ならまあ結構通じると思います。

活動時間中はどんな感じか

ここからは少し話の本筋からは外れますが活動時間中のサークルの雰囲気的なものを紹介します。(尺稼ぎともいいます)

活動時間中は基本的にみんな一つの部室の中で個々で創作活動をしているのでスタイルもかなりバラバラです。音楽を聴きながら、独り言を呟きながら、同じような言語で開発している人とアイディアなどを共有、アドバイスしあったり・・・かなり自由な空気なんで楽しく開発、創作をできるんじゃないかなーと思います。

活動の中で「月末報告会」というのがあるのでメンバーの活動を見て刺激を受けることができます。これは予想以上に制作のモチベーションに繋がります。アイディアも湧いてくるので面白いです。(まあこれは見てもらった方が早いんで説明しづらいのですが)

まとめ

サークル棟はこんな感じ、大学敷地の端にあるので配布するチラシを頼りに来てほしいです

とりあえずプログラミングやコンテンツ制作に興味があるなら一度部室に足を運んでほしいなぁって切実に思ってます。経験未経験は全く問いませんしプログラミング以外でもゲーム音楽やイラスト製作をしたいと思っている人も大歓迎です(ぶっちゃけグラフィック系の人材が足りな過ぎてやばいです)

気になっている人はTwitter公式アカウント(@tnp_ko)などに気軽に色々質問してみてください。このブログの過去記事なんかも参考になるかもです。

それでは皆さん、入学後の部活・サークル紹介で会いましょう!お待ちしています!
サークル紹介での僕の目印は「EScape」(分かる人は分かるネタ)、でったーでした!

新入生へ: 生協パソコンを買う前に少し考えてもいいんじゃないだろうかという話(個人差があります)

ここから下の内容は一個人の意見・推論です

来たる新入生へ

合格おめでとうございます。

これから始まる新生活に、新入生の方々は胸踊らせ、日々楽しみ、もしくは多少の不安を感じていることでしょう。

そう、4月は始まりの季節。

楽しいことや不安なことが一気に押し寄せ、この時期はかなり精神的にブレが生じる時期でもあります。

そして、この時期はパソコンを買い換える時期で、大学に入学準備に行くとパソコンを勧められます。

彼らは学生の味方です。しかし、営利団体でもあります。
儲けを出さないといけません。
そこは理解しないといけません。


パソコンの話

合格が決まると、彼らは大学にきて、彼らの一員になることを強いてきます。
これは仕方ありません。彼らの意見を飲みましょう。
ここは気持ちを抑えてスパイになるのです。

ただし、生協パソコンは買う前には色々と考え直してみましょう。
多くのTNP部員が被害にあっています。


彼らはかなり低スペックのPCを高い値段で売ってきます。
おそらく彼らの言い分は

「保険がつく」だの
「パワポがつく」だの
「頑丈」だの

電気店でも言われることを言ってきます。
鵜呑みにしてはいけません。自分で考えて行動しましょう。

同じ値段でどれ位のパソコンが買えるでしょうか?

例えば、「MacBook Pro」が買えます。

ほぼ同じ値段で、保険がつき、Macというかっこいいものが買えます。
Macはプログラミングのおける環境構築がWindowsに比べて遥かにしやすくUIも統一されています。
・・・Linux?そういうのもあるのか

僕はMac派なのでMacを押します。
現在、キャンペーン中なので、割引+二万円キャッシュバックがついてきます。

さらにMacのいいところは、売るときの値段が大体買った値段の半分です。
これが強い

持ち運びじゃない、デスクトップならiMacが買えますね。
そこそこのスペックが買えます。
四年間のプログラミングには有り余る性能があります。

Windowsがいい??
ならば、Surfaceなどの選択肢があります。
薄くて使いやすく性能もいい。
生協パソコンが駄目とはいいませんがなにかと入らないものがついていたり、彼らの懐にはいるお金がおそらく多い。

BTOもありです。

私がいいたいのは、生協パソコンに甘んじてはいけないということです。


最後になりますが、まだ間に合うのなら、他のMac製品や、Windowsパソコン、BTOなどを見てみるといいです。

大学では優しい人もいますが、汚い大人がうじゃうじゃいます。
自分で考えて行動すると良さそうです。

ガナリヤでした


追伸

自分で選んだパソコンでのプログラミングは非常に楽しいです!!!
四年間付き合うと思って大事に選んであげてください!!!
Macはいいぞ!(後方彼氏面)

バージョンが上がってLaTeX出来るようにした話

こんにちえるえる〜〜

なんか久しぶりですね。

ガナリヤです。新しいバージョンにしたせいか、色々と不具合が起きて辛いです・・・なんとかします・・・


WordPressのバージョンが上がった話、使い方とLaTeXの話をします


WordPressのバージョンが上がった話

WordPressというシステムを現在、TNPでは使っています。

WordPressはPHPで構成されているフレームワークであり、拡張しやすく、これまでブログよりも使いやすい点があります。
また、WordPressに移行した理由として

  • 全員が使える。
  • HTMLを知らなくても書ける(ビジュアルで書ける)

という点があります。

現在、そのバージョンが上がり、新しいエディタGutenbergというものが導入されました。

このエディタでは、ブロック構造が採用され、各段落を一つのブロックとして構成します。

上記の段落は、以下の図のようなブロックとしてなっており、ブロックは自由に移動できます。

今回のエディタによって、よりノンプログラミングにブログをかけるようになりました。

ただ、これまでのブログのエディタに慣れていた人には辛いですが(現在辛いです・・・)

使ってみると分かると色々と分かると思います〜


マークダウンを使うときは

プログラマーには、マークダウンというものに慣れている人がいます。
僕もその一人です。
マークダウンを使うとより高速にブログを書くことが出来ます。(ビジュアル操作を気にしなくていいと言うと伝わりやすいでしょうか・・・)

現在のエディタでマークダウンを書くには以下のようにしてください。

自分のパソコンの「Boostnote」などでマークダウンを書き、ブロックにコピペしてください。

すると、自動でマークダウンから、普段どおりの大きさやリスト、水平線に変換されます。

よって、現在は、このWordPressエディタ上でマークダウンはかけません。(一部はかけます。)
これからWordPress上で書けるようにする方法はないか模索します。


改行の仕方

ブロックごとに書きますが普通に改行すると(エンターを押すと)

このように一行多く空きます。

なので、ブロックないで改行しようかな〜〜ていうときは「Shift + Enter」をしてください。
すると、一行多く空けない通常の改行ができます。


コード挿入の仕方

ソースコードを挿入したい時があると思います。
そのようなときは以下のようにしてください。

「フォーマット」に入っている「Highilghing Code Block」というものを選び、ソースコードを挿入してください。

すると、ソースコードを挿入できます。


LaTeXの使い方

プログラミングの記事を書くときは
変数を$x$としたり、
$$ y = 10x + 2$$

のように数式を使いたくなると思います。

これはLaTeXというもので実現できます。(TeXがもとであり、それを拡張したものがLaTeXだと思っていいかと思います。)

LaTeXを書くには半角の「ドルマーク $」でLaTeXしたいものを囲ってください。

つまり、 $x$と言った感じです。(これは、ドルマークを全角で表現しています。ここで半角にしてしまうと、LaTeXになって、どのようになるかが表現できないので・・・)

よって、LaTeXしたいときは、半角のドルマークで数式などを囲ってください。

また、中央に
$$ y = x$$

のように表示したいときは半角のドルマークを
$$ y = x $$

のようにすると、中央寄せができます。


最後に

多分伝わらないと思います・・・(すいません)

今度部室で使い方をきちんと説明したいと思います。
また、実際に触ってみると使い方がわかると思います。

自分もまだこれに慣れてないので、大分読みづらいかと思います。すいません。

改善できるようにいろいろ工夫していこうと思います。

ガナリヤでした〜

ゲームジャム~平成最後の春休み編~

皆さんこんにちは!TNP部員2年次のYutaです。初投稿であまり慣れてなく読みにくいところがあるかもしれませんが, どうか温かい目でご覧下さいませ。

さて, 3/1(金)~3/2(土)の2日間, TNP部室にてゲームジャムが開催されました。

「ゲームジャム」とは, 最初にテーマが与えられた上で, 「短時間でゼロからゲームを作ってみよう!」というイベントです。 今回は1年次2人, 2年次3人が参加しました。

テーマは「数字」, 「お菓子」, 「飛ぶ」に決定し, 主にこれに沿って各々が自由にゲームを制作しました。

それでは, 皆さんの作品を紹介させていただきます。


製作者:ズッキー(1年次)

製作物:飛行機ゲーム

開発環境:Unity

飛行機を操縦して, 穴が開いた場所まで行き, タイミング良くアイテムを投下させて穴に入ればクリア!というゲームとのこと。飛行機の動きがリアルでカッコよく, 完成度も高くてびっくりしました。私もUnityでゲーム作りをしているのですが, 乗り物シミュレーション系に興味があるので参考になりました。


製作者:まんじゅう(1年次)

製作物:東方非想天則RPG(仮)

開発環境:RPGツクール

東方非想天則をモチーフにしたRPGゲームとのこと。JavaScriptの解読が非常に大変だったそうです。私は触れたことのない言語なので何が書いてあるかさっぱり分からず, これに粘り強く取り組めることにすごいと思いました。パラメータなどもたくさんあり, 様々な努力が感じられるゲームです。RPGツクールって奥が深いんですね…。


製作者:いっちー(2年次)

製作物:パズルゲーム

開発環境:DXライブラリ

数字をテーマとしたパズルゲームとのこと。ブロックを操作して他のブロックに触れると積まれていきます。シンプルな画面もまた味があっていいですね。当たり判定などに非常に苦労したそうです。DXライブラリはUnityなどのように簡単にGUI環境で手軽に当たり判定が実装できないので, 1からコードを書いて工夫してやるのはすごいと思いました。


製作者:うおちー(2年次)

製作物:ブラフゲーム&3Dモデリング

開発環境:Siv3D

ボードゲームの「ブラフ」を元にしたゲームとのこと。ボードゲームをプログラミングで再現するというアイデアに驚きました。短時間でこういったゲームが作れるのはすごいと思いました。

さらに, 時間が余ったということで「3Dモデリング」でいくつか作品を作ったそうです。うおちー氏はTNP子の3Dモデルを制作するなど, その道に関しては技術がすごいです。

キャンディやCD, お菓子の筒, フライドポテト, Tが付く企業のあの鳥など, 短時間でここまでリアルなものが作れるとは…さすがです。特にストローが蛇腹の部分まで細かく作り込まれていることにびっくりしました。


製作者:Yuta

製作物:ペットボトルロケットを飛ばそう

開発環境:Unity

私は最初何も思いつかなかったので, 「とりあえずUnityでなんか飛ばそう!」と思い, そこからペットボトルロケットになりました。「空気注入」ボタンを押して空気を貯めて, 発射ボタンを押すと飛んでいきます。発射台は自由に方向が変えられるようになっています。ペットボトルロケットが空間に存在するアイテム(お菓子)にぶつかるとポイントが獲得できます。アイテムはボタンを押すとランダムに生成されます。

コード自体は大して難しくはなかったのですが(簡単な動きの組み合わせだったので…), 手こずったのは座標軸とカメラの動きでした。ローカル座標系とワールド座標系が一致してないと頭が混乱します。カメラも思い通りに動かすにはまだまだ勉強不足でした。

あと, アイテムを増やしすぎるとfpsが低下して全体の動きが非常に重くなるのです(そりゃそうだ)。Time.deltaTimeを使えばよかったのでは?などの課題が残りました。


今回, 私は初めてゲームジャムに参加したのですが, 短時間でアイデアを考えて形にするのはなかなか難しかったです(基本マイペースなので)。でも限られた時間の中でどれだけのものが作れるのか試すことができ, 良い経験になりました。自分自身への良い刺激にもなったと思います。

ゲームジャムに参加する前は, 時間に追われ殺伐とした雰囲気でやるのかしらんなどとイメージしていたのですが, 実際はそうでもなく, 持ち寄ったお菓子をみんなで食べたりしながら楽しく制作ができたと私は思っています。

灯油ヒーターがつかず寒い部室でしたが, 心は温まりました。またやりたいですね, こういうの。

そろそろサイトを弄っていこうかという話

どうも皆さん、お初にお目にかかります。Web&Twitter担当となりました初年次のでったーと申します。

 

「もうそんな季節か」と思う人もいれば「この時期に「初めて」?」と思う人もいるでしょう。TNPにとって11月はそろそろ初年次が表に出てくる時期なんです(恐らく)。自己紹介とかもしたいところですけどそれはまた今度にするとします。

 

11月、TNPは秋大祭を終えて代替わりの季節、今まで役職がなかった初年次にも様々な役職が割り振られるわけであります。新しいオリジナルゲーム等の開発にも本腰を入れ一気にサークルに新しい雰囲気が流れ込んでくるんじゃないのかな、と初年次ながら期待に胸膨らませている次第なんです。

 

新しい役職云々に関しては恐らく二年次が後々記事にしそうなところなんで省略するとして今回の題材は僕の担当する「TNP公式サイト」についてです。

 

WordPressをプラットフォームとしたこの公式サイトは昨年の今頃、現三年次のガナリヤさんによって作られたものでサークル全体としては3つめのサイトだったりするらしいです。(統合はかなり大変とかなんとか)

 

まあ非常に大雑把に事を話すと今のサイトの改造権限は僕にあるわけです。引き継がれたんだから当然のことです。

 

だから改造したい!!しよう!!と意気揚々とサイトの工事に入ろうとしたのですが・・・

 

知 識 不 足

 

というわけでありまして・・・まったくもって現状目に見えて弄った点はたったの一つという有様・・・全て俺が悪いよ、申し訳ない。お恥ずかしい限りですが取り敢えず唯一の改造点を今回ご報告しておきます。

 

 

改造点

サイドバーにTNP公式アカウント(TNP子)のツイートを表示するようにしました。

 

と大層なアップデートのように見せてはいますがからくりはTwitter Publishを用いて得たHTMLをサイドバーのカスタムHTMLウィジェットに張り付けただけです・・・ただ「それっぽさ」を追及してるだけですから!!

 

とまあこんなもんです。しかしこれでもトップページにサイドバーが表示されないんで「(トップページにだけ)目立たない改修」というか・・・もう少し仕様を調べてちゃんと表示されるようにしたいですね。

 

 

これからの目標

もっとなんかいい感じにしたい(雑)。分かりやすく軽快にをモットーに改造していきたいなぁというのが今のところの考えです。もっとも自分のスキルアップが第一なんですけどね。

 

あとブログも連載的な企画とかもできるならやってみたいなぁと、これは部員のみんなの協力が不可欠ではあるんですがね・・・(それ以前にお前は何様だという問題が生じますが)

 

取り敢えずこれからのTNPブログにどうぞゆるくご期待ください!でったーでした!

TNGとは?

この記事は今後、大きく加筆・修正される予定です!!

(中の人は学祭当日未明、この記事を書いています…

 

「TNG」はTNPのゲームを一括管理・公開するために作られたランチャーのような何かです。同じ役割を担っていた、先代の「ゲームジェネレーター」の改良版として、一年前から制作されてきました。(ただし今もバグまみれの模様)

制作は私サバと、現会長のコショウ氏が主に行い、アイコンは蟹氏に描いていただきました。イメージは魚のタナゴだそうです。(TNG+魚要素=タナゴ)

ちなみにTNGは「Tnp’s Next generation Game launcher」の略です。さらに展開すると、「The next generation programmer’s Next generation Game launcher」という php のような再帰的頭字語みがある気がして気に入ってます。

 

AtCoder Beginner Contest 112

こんばんえるえる〜〜〜〜
ガナリヤです
大学の後期がついに始まりましたね
今週一週間は毎日しんどくて未だに体の疲れが取れません。
コミュニケーション能力を付けないとこのままではまずい気がします。

今回は、AtCoderBeginnerContest112に出ました。
結果としては、ABCD4完は出来ましたが、Cで4WAしているのでもうちょっと細かい部分に意識をしないといけませんね・・・
早速内容を振り返っていきましょう!


A 「Programming Education」

問題文

AtCoderはクソデカ年商となり、プログラミング教育をするようになった。
入力から自分の年齢Nが入力される。
N=1なら”Hello, World”と出力せよ。
N=2ならA+Bの答を計算せよ。

解法

やるだけです。
もう20秒ぐらい早くとけるようになりたいです。


B 「Time Limit Exceeded」

問題文

Xさんは、外から家に帰ろうとしています。
現在位置から家に帰るルートは、N個存在しますが、それぞれに係る時間tiと、かかるコストciがあります。
時間T以内に、帰らなければいけない時、最小のコストを求めてください。

解法

時間T以内なので、時間T以内のルートのみを列挙して、さらにその中でも一番コストの低いものを出力してしまえばいいです。
気をつける点としては、ルートが一つもない場合はTLEと出力しないといけないので、最初の変数の初期化で上限いっぱいにしておいて、値が更新されてなければTLEとしないといけません。
実装に2分もかかったので半分ほどにするひつようがあります。

コード


int main() {
 
    LL N, T;
    cin >> N >> T;
 
    LL cost = LONG_LONG_MAX;
    for (int i = 0; i < N; i++) {
        LL c, t;
        cin >> c >> t;
        if (t <= T) {
            S_MIN(cost ,c);
        }
    }
 
    if(cost == LONG_LONG_MAX){
        OUT_L("TLE");
    }else{
        OUT_L(cost);
    }
 
    return 0;
}


Pyramid

問題文

問題文長すぎるのでここを見て→ https://beta.atcoder.jp/contests/abc112/tasks/abc112_c

解法

内容としては簡単だったのですが、3つ特殊ケースがあり、そのケースに気づくまで時間がかかってしまいました。

制約を見るとCxもCyも0~100以内なので、全探索しても余裕で間に合うことが分かります。
中心のCx、Cyを仮に全探索してみます。
すると、中心の高さHを求めたいわけですが、この高さは他の点1つを選んでしまえば逆算することが出来ます。
そうして求めたHと他の点を全て比べて、条件を満たせばそれが答えになります。

しかし、この解法だけだとうまくいかない場合があり、参考にする点が高さ0の場合です。
高さ0の場合、もともと高度は(H -|X – Cx| – |Y – Cy|, 0)のため、マンハッタン距離で0だったのか、最初から0だったのか判断することが出来ません。
よって、関係ない答を出力してしまう可能性があります。
よって、そのケースは省いて計算する必要があります。
体感的にBレベルでしたが、特殊ケースだけはDレベルな感じがしました。

コード

int main() {
 
    int N;
    cin >> N;
 
    VLL x(N), y(N), h(N);
    REP(i, N) cin >> x[i] >> y[i] >> h[i];
 
    for (LL i = 0; i <= 100; i++) {
        for (LL j = 0; j <= 100; j++) {
            LL H = 0;
            for (LL k = 0; k < N; k++) {
                if (h[k] != 0) {
                    H = h[k] + ABS(i - y[k]) + ABS(j - x[k]);
                    break;
                }
            }
            if (H <= 0) continue;
            bool good = true;
            for (int k = 0; k < N; k++) {
                LL _h = C_MAX(H - ABS(i - y[k]) - ABS(j - x[k]), 0LL);
                if (_h != h[k]) good = false;
            }
            if (good) {
                cout << j << " " << i << " " << H << endl;
                return 0;
            }
        }
    }
 
    return 0;
}


D Partition

問題文

整数N, Mが与えられます。
a1 + a2 + ・・・ + aN = Mとなるような長さNの数列aにおいて、a1~aNの最大公約数となる最大値を求めてください。

解法

Mが与えられるので、可能性のあるaの組み合わせを作成し、その最大公約数を求める必要があります。
最大の最大公約数であるため、少し工夫しないといけません。なぜなら、制約でNが10万のため、計算量的にNlogNが最大であるためです。

そこで、最大公約数について一度考え直して見ます。
最大公約数は、a全てにおいて、共通の約数を持っており、共通の約数ということは同じ倍数を持っているということに等しいです。
共通の倍数をKとすると
Kb1 + Kb2 + ・・・ + KbN = Mということになります。
つまりM = K * (b1 + b2 + ・・・ + bN)というわけで、Mは因数としてKを持つことが分かります。
よって、Mに対して、約数を列挙し、その約数の中で、NをかけてもMを超えないものが答となります。
約数をTとして、T
N < Mのとき、数が余らないか?というう話になりますが、Mも因数Kを持つため、うまく配分すれば全ての変数がKを因数に持つことが分かります。

素因数分解はO(√N)でできるので、計算量的にも間に合うことが出来ます。

今回のDは3分で通せたので、成長を感じます。(なお、C)

コード



//nの約数
template<typename T>
vector<T> DIVISOR(T n) {
    vector<T> v;
    for (LL i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) {
                v.push_back(n / i);
            }
        }
    }
    sort(v.begin(), v.end());
    return v;
}
 

int main() {
 
    LL N, M;
    cin >> N >> M;
 
    auto divisors = DIVISOR(M);
    LL maxV = 1;
 
    for (int i = 0; i < SZ(divisors); i++) {
        if(divisors[i] * N <= M){
            maxV = divisors[i];
        }
    }
    OUT_L(maxV);
 
    return 0;
}
 
 

### 感想

今回の問題は、Cが一番難しかった感じがあります。
4WAは流石に出しすぎなので、もうちょっとミスを減らさないといけませんね・・・

ガナリヤでした!