# 113

【エンジニア部門だより】競技プログラミングしようぜ！【113日目】

やっほーみなさんこんにちは！
わたなべは2週間くらい前？から、Atcoderという競技プログラミング（以下競プロ）にハマっています。この手の競技系は、食わず嫌いで挑戦できていなかったのですが、やってみると意外と面白くて毎日ちびちびやっています。競技系は他にも、機械学習系のKaggleやアルゴリズム力を問うyukicoderやAOJなどが有名らしいですが、僕はAtcoder以外はやったことがないので、今日はAtcoderのみの話に閉じてシェアします。

競プロについてぐぐってみると

> 競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。コンピュータサイエンスや数学の知識を必要とする問題が多く、採用活動などに使われることもある。多くのコンテストでオンラインジャッジが採用されている。

とありますね。
最近はIT系の企業でも、採用活動に競プロを活用している会社もあったりするみたいです。（とはいえ数は少ない、Atcoderでは27社のみ。）

エンジニア力（設計、技術選定等）を直接問うものではありませんが、「実装力」を問うにはもってこいの競技です。毎週の土日いずれかの夜（21:00〜、大体飲み会の時間と被るので、競プロerたちは、飲み会か、Atcoderかの苦渋の選択を迫れることになります。）に100分程度のコンテストが開催され、そのスコアに応じてランク付けされます。コンテストの難易度は毎週変動するため、そのときの参加者の得点具合によっての相対評価および、コンテスト参加回数でランクが決まります。ランクは色で表され、下から、灰色・茶色・緑・水色・青・黄・橙・赤という順番になっています。
まあこんなんはいいので、問題を紹介します。

■ 問題例（C問題、ABC085C - Otoshidamaより）

> 日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

■ 入出力例

入力は以下の形式で標準入力から与えられる。

N Y

出力
・N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
・N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

■ 宣伝

DAで一緒に競技プログラミングを始める人を募集します！
いま、後藤さん、道方さん、菱谷さんから参加表明をいただいています。
どうせならみんなで始めて、モチベーションを維持しながら遊んだほうが楽しいので、このタイミングでのゆるぼになります！興味あるひとは教えてね！
確実に実装力が付いていくので楽しいです！最初は慣れるまで時間がかかるものですが、続けた分だけ確実の実装力が身につきます。毎週数学のテストやってて、見直しもやってたら嫌でも力がつくのと一緒です。興味がある方はぜひ！別チャットでやることになると思います！

https://jobs.atcoder.jp/

■ 問題

> 「一滴でも飲むと20時間以内に腹痛を引き起こす毒（死なない、ちょっとだけお腹痛くなるだけ）」が、1000本のコーラ瓶のうち1本にだけ入っています。わたなべさんは意地汚いので、すべてのコーラを処分するという選択はなんとしても避けたいと考えています。幸いにも友だちは多かったので、友達に手伝ってもらって、どれが毒入りか調べようと考えました。24時間以内にどのコーラに毒が入っているかを調べるには、「何人の友だちが必要」で、「どのように調べれば」良いでしょうか？

※ この毒は、どれだけ薄めても効果は薄まりません。

貪欲に調べるには、友だちを1000人呼んで同時に飲んでもらえば、20時間後にどのコーラに毒が入っているかを調べることができますね。しかし、いくら人気者で陽キャのわたなべさんでも1000人はともだちがいないので、もう少し少ない人数で調べたいですね、何人くらいだと思いますか？