こしあん
2018-10-07

[ABC006] C – スフィンクスのなぞなぞ

Pocket
LINEで送る
Delicious にシェア

792{icon} {views}



ディープラーニングの訓練中暇なので、AtCoderの過去問解いてみることにしました。どこまで解けるかはわかりませんが、ABCのC問題、D問題中心に解いてみます。全部書くのはきついので自分が面白いなと感じた問題をピックアップしていきます。

最初に取り上げるのはABC006のC問題「スフィンクスのなぞなぞ」です。一見、再帰やメモ化を匂わせるような問題ですが、実はそれを使わなくてもスマートに解ける面白い問題です。

問題文

新学期に向けて新たな気持ちで通学しているあなたの前に、スフィンクスが立ちふさがっています。
このスフィンクスは「なぞなぞ」を出すことで有名で、このなぞなぞに答えられない場合、留年します。

なぞなぞは以下のとおりです。
「この街には人間が N 人いる。人間は、大人、老人、赤ちゃんの 3 通りだ。
この街にいる人間の、足の数の合計は M 本で、大人の足は 2 本、老人の足は 3 本、赤ちゃんの足は 4 本と仮定した場合、存在する人間の組み合わせとしてあり得るものを 1 つ答えよ。」

新学期早々留年したくないあなたは、このなぞなぞに正解する必要があります。
なぞなぞの答えとなる「この街に存在する人間の組み合わせ」を 1 つ出力してください。
もし、そのような組み合わせが存在しない場合は-1 -1 -1と出力してください。

https://beta.atcoder.jp/contests/abc006/tasks/abc006_3

条件

  • $1\leq N \leq 10^5$, $1\leq M \leq 5\times 10^5$
  • 大人、老人、赤ちゃんの人数は0人以上の整数
  • 部分点あり(詳細は省略)

連立方程式で解く

部分点無視していきなり満点解答でいきます。まず、NとMが大きすぎるのでforループで貪欲に解くのはダメです。$10^{10}$クラスになりおそらくオーバーします。

まず大人の人数をa, 老人の人数をb, 赤ちゃんの人数をcとしましょう。連立方程式で整理します。

  $2a+3b+4c=M $
  $ a+b+c=N$

連立方程式を解くには最低でも変数分の式が必要なので、これは一意に解を求めることができません。逆に言えばこの場合は式が2本だったら解けます(ここポイント)。

今これは数学の問題ではないので、足りなそうな値はforループで与えてしまえばいいのです。ループが速そうなのでcを与えるものとしましょう。今、仮に与えたcを$c^*$とします。

  $2a+3b=M-4c^* $
  $ a+b=N-c^*$

これは変数2個、式2本の連立方程式なので一意に解を求めることができます。数学的にaとbを解いていきましょう。下の式を2倍して上の式から引くと、

  $ b=M-2N-2c^* $

これを代入して、

  $ a=-M+3N+c^* $

と求められます。あとはforループで回せば終わりですね。

コード

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var N = vals[0];
            var M = vals[1];

            //連立方程式を解く
            //a=大人、b=老人、c=子どもとして、
            // 2a+3b+4c=M
            // a+b+c=N
            //c=c*として与えられたら、
            // a = -M + 3N + c*
            // b = M - 2N - 2c*
            //で計算できる
            for(var child = 0; child <= Math.Min(N, M/4); child++)
            {
                var adult = -M + 3 * N + child;
                var silver = M - 2 * N - 2 * child;
                if(adult >= 0 && silver >= 0)
                {
                    Console.WriteLine($"{adult} {silver} {child}");
                    return;
                }
            }
            Console.WriteLine("-1 -1 -1");
        }
    }
}

今回の場合は連立方程式の解が小数にならないので小数のチェックは不要です。0以上の制約だけ見ればいいです。

以上です。解法の1つですが連立方程式で整理するとエレガントに解けますね。



Shikoan's ML Blogの中の人が運営しているサークル「じゅ~しぃ~すくりぷと」の本のご案内

技術書コーナー

【新刊】インフィニティNumPy――配列の初期化から、ゲームの戦闘、静止画や動画作成までの221問

「本当の実装力を身につける」ための221本ノック――
機械学習(ML)で避けて通れない数値計算ライブラリ・NumPyを、自在に活用できるようになろう。「できる」ための体系的な理解を目指します。基礎から丁寧に解説し、ディープラーニング(DL)の難しいモデルで遭遇する、NumPyの黒魔術もカバー。初心者から経験者・上級者まで楽しめる一冊です。問題を解き終わったとき、MLやDLなどの発展分野にスムーズに入っていけるでしょう。

本書の大きな特徴として、Pythonの本でありがちな「NumPyとML・DLの結合を外した」点があります。NumPyを理解するのに、MLまで理解するのは負担が大きいです。本書ではあえてこれらの内容を書いていません。行列やテンソルの理解に役立つ「従来の画像処理」をNumPyベースで深く解説・実装していきます。

しかし、問題の多くは、DLの実装で頻出の関数・処理を重点的に取り上げています。経験者なら思わず「あー」となるでしょう。関数丸暗記では自分で実装できません。「覚える関数は最小限、できる内容は無限大」の世界をぜひ体験してみてください。画像編集ソフトの処理をNumPyベースで実装する楽しさがわかるでしょう。※紙の本は電子版の特典つき

モザイク除去から学ぶ 最先端のディープラーニング

「誰もが夢見るモザイク除去」を起点として、機械学習・ディープラーニングの基本をはじめ、GAN(敵対的生成ネットワーク)の基本や発展型、ICCV, CVPR, ECCVといった国際学会の最新論文をカバーしていく本です。
ディープラーニングの研究は発展が目覚ましく、特にGANの発展型は市販の本でほとんどカバーされていない内容です。英語の原著論文を著者がコードに落とし込み、実装を踏まえながら丁寧に解説していきます。
また、本コードは全てTensorFlow2.0(Keras)に対応し、Googleの開発した新しい機械学習向け計算デバイス・TPU(Tensor Processing Unit)をフル活用しています。Google Colaboratoryを用いた環境構築不要の演習問題もあるため、読者自ら手を動かしながら理解を深めていくことができます。

AI、機械学習、ディープラーニングの最新事情、奥深いGANの世界を知りたい方にとってぜひ手にとっていただきたい一冊となっています。持ち運びに便利な電子書籍のDLコードが付属しています。

「おもしろ同人誌バザールオンライン」で紹介されました!(14:03~) https://youtu.be/gaXkTj7T79Y?t=843

まとめURL:https://github.com/koshian2/MosaicDeeplearningBook
A4 全195ページ、カラー12ページ / 2020年3月発行

Shikoan's ML Blog -Vol.1/2-

累計100万PV超の人気ブログが待望の電子化! このブログが電子書籍になって読みやすくなりました!

・1章完結のオムニバス形式
・機械学習の基本からマニアックなネタまで
・どこから読んでもOK
・何巻から読んでもOK

・短いものは2ページ、長いものは20ページ超のものも…
・通勤・通学の短い時間でもすぐ読める!
・読むのに便利な「しおり」機能つき

・全巻はA5サイズでたっぷりの「200ページオーバー」
・1冊にたっぷり30本収録。1本あたり18.3円の圧倒的コストパフォーマンス!
・文庫本感覚でお楽しみください

北海道の駅巡りコーナー

日高本線 車なし全駅巡り

ローカル線や秘境駅、マニアックな駅に興味のある方におすすめ! 2021年に大半区間が廃線になる、北海道の日高本線の全区間・全29駅(苫小牧~様似)を記録した本です。マイカーを使わずに、公共交通機関(バス)と徒歩のみで全駅訪問を行いました。日高本線が延伸する計画のあった、襟裳岬まで様似から足を伸ばしています。代行バスと路線バスの織り成す極限の時刻表ゲームと、絶海の太平洋と馬に囲まれた日高路、日高の隠れたグルメを是非たっぷり堪能してください。A4・フルカラー・192ページのたっぷりのボリュームで、あなたも旅行気分を漫喫できること待ったなし!

見どころ:日高本線被災区間(大狩部、慶能舞川橋梁、清畠~豊郷) / 牧場に囲まれた絵笛駅 / 窓口のあっただるま駅・荻伏駅 / 汐見の戦争遺跡のトーチカ / 新冠温泉、三石温泉 / 襟裳岬

A4 全192ページフルカラー / 2020年11月発行


Pocket
LINEで送る
Delicious にシェア

Tags:, ,

Add a Comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です