AtCoder参戦日記 ARC104 ― Scalaの限界を知る

AtCoderの4回目の参加となった2020/10/03 ARC104の記録です。

2完でした。

2問目のACまでに20分も消費してしまいました。

その後約40分をCに時間かけ、コードを書きましたが、最後まで書ききれずに、提出することなくあきらめてDに移りました。

Dでも残り時間約40分かけて、コードを書いて提出までしましたが、細かいバグ取りと処理時間の問題を解決できずに時間切れとなりました。Scalaで取り組んだのですが、無理でした。

問題 結果 言語
A Python (競技後にRuby)
B Scala
C 競技後にJava
D 競技後にScala, Java, C++, Ruby, Perl, Elixir
E
F

過去の記録

A - Plus Minus

問題

競技中はPythonで書きました。あとで他言語の練習としてRubyでも書きました。

[a, b] = input().split(" ")
a = int(a)
b = int(b)

print("%d %d" % ((a + b) / 2, (a - b) / 2))
a, b = gets.strip.split(" ").map(&:to_i)
printf("%d %d\n", (a + b) / 2, (a - b) / 2)

B - DNA Sequence

問題

Scalaで書きましたが、とても汚いコードです。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val s = sc.next();

  val answer = (1 to (n/2)).map(2 * _).map { m =>
    var k1 = (0 until m).count(i => s(i) == 'A');
    var k2 = (0 until m).count(i => s(i) == 'T');
    var k3 = (0 until m).count(i => s(i) == 'C');
    var k4 = (0 until m).count(i => s(i) == 'G');
    (0 to (n-m)).count { i =>
      if (i > 0) {
        s(i - 1) match {
          case 'A' => k1 -= 1;
          case 'T' => k2 -= 1;
          case 'C' => k3 -= 1;
          case 'G' => k4 -= 1;
          case _ => ;
        }
        s(i + m - 1) match {
          case 'A' => k1 += 1;
          case 'T' => k2 += 1;
          case 'C' => k3 += 1;
          case 'G' => k4 += 1;
          case _ => ;
        }
      }
      k1 == k2 && k3 == k4;
    }
  }.sum;

  println(answer);

}

C - Fair Elevator

問題

競技中は40分ぐらい考えましたが、いい解法が思いつきませんでした。無理やりな解法は考えてコードを書いたのですが、コードが複雑すぎて書ききれずでした。

以下は競技後に解説を見てから書いたコードです。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    int n2 = 2 * n;
    var abs = new int[n2];
    for (int i = 0; i < n; i++) {
      abs[2 * i    ] = sc.nextInt();
      abs[2 * i + 1] = sc.nextInt();
    }
    var table = new int[n2];
    var table2 = new boolean[n];
    for (int i = 0; i < n; i++) {
      var a = abs[2 * i    ];
      var b = abs[2 * i + 1];
      if (a > 0 && b > 0 && a >= b || a > 0 && table[a-1] != 0 || b > 0 && table[b-1] != 0) {
        System.out.println("No");
        return;
      }
      if (a > 0) table[a-1] = i + 1;
      if (b > 0) table[b-1] = -(i + 1);
      if (a > 0 && b > 0) table2[i] = true;
    }
    var dp = new boolean[n];
    for (int i = 0; i < n; i++) {
      for (int j = -1; j < i; j++) {
        boolean flag = (j < 0) || dp[j];
        if (!flag) continue;
        int ij2 = i - j;
        int l = 0;
        for (int k = 0; k < ij2; k++) {
          int a = table[2 * (j+1) + k];
          int b = table[2 * (j+1) + k + ij2];
          if (a < 0) {
            flag = false; break;
          } else if (b > 0) {
            flag = false; break;
          } else if (a > 0 && b < 0 && a + b != 0) {
            flag = false; break;
          }
          if (a > 0 && b == 0 && table2[a-1]) {
            flag = false; break;
          } else if (a == 0 && b < 0 && table2[-b-1]) {
            flag = false; break;
          }
        }
        if (l != 0) flag = false;
        if (flag) {
          dp[i] = flag;
          break;
        }
      }
    }
    if (dp[n-1]) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

D - Multiset Mean

問題

競技中に解法を見出して、コードを提出までしましたが、細かいバグ取りと処理時間の問題を解決できずに時間切れとなりました。

競技後に以下の記事のとおり、各言語で解いています。この記事のとおり、Scalaでは厳しいことを実感しております。

curlコマンドとwgetコマンドでバイナリをPOST

curlコマンドまたはwgetコマンドを使い、HTTP(S) POSTメソッドのリクエスト本体でバイナリを送る方法です。

httpbin

HTTP(S)の通信をテストするには httpbin というサイトが便利です。

以下のようにhttpbinにHTTPリクエストを送信すると、リクエストの内容がレスポンスとして返されます。

$ curl 'http://httpbin.org/get' 
{
  "args": {}, 
  "headers": {
    "Accept": "*/*", 
    "Host": "httpbin.org", 
    "User-Agent": "curl/7.68.0", 
    "X-Amzn-Trace-Id": "Root=1-5f8bd296-24f5bbf764560c2432655930"
  }, 
  "origin": "999.999.999.999", 
  "url": "http://httpbin.org/get"
}

X-Amzn-Trace-Id というリクエストヘッダーは curl コマンドが付与するものではなく、AWSのALBが付与するものです。httpbinのサービスがALBの後ろで動いているんだと思います。

curlコマンド

--data-binary というオプションでバイナリの保存されているファイル名を指定します。ファイル名の前に @ を付けます。

$ curl -H "Content-Type: application/octet-stream" -X POST --data-binary @data.txt 'http://httpbin.org/post'
{
  "args": {}, 
  "data": "data:application/octet-stream;base64,YQBigGM=", 
  "files": {}, 
  "form": {}, 
  "headers": {
    "Accept": "*/*", 
    "Content-Length": "5", 
    "Content-Type": "application/octet-stream", 
    "Host": "httpbin.org", 
    "User-Agent": "curl/7.68.0", 
    "X-Amzn-Trace-Id": "Root=1-5f8bd13d-70f0515e6ebaa60411533998"
  }, 
  "json": null, 
  "origin": "999.999.999.999", 
  "url": "http://httpbin.org/post"
}

レスポンスのdataが "data:application/octet-stream;base64,...という表記になっていますが、httpbinはバイナリを受け取るとBASE64エンコードして返すようです。ソースコードを見るとわかります。

curlコマンドのオプションを --data-binary @- とすれば標準入力からバイナリを取り込みます。

$ printf "a\0b\x80c" | curl -H "Content-Type: application/octet-stream" -X POST --data-binary @- 'http://httpbin.org/post'

ちなみに -d ではバイナリを扱えません。

$ curl -H "Content-Type: application/octet-stream" -X POST -d @data.txt 'http://httpbin.org/post'
{
  "args": {}, 
  "data": "a", 
  "files": {}, 
  "form": {}, 
  "headers": {
    "Accept": "*/*", 
    "Content-Length": "1", 
    "Content-Type": "application/octet-stream", 
    "Host": "httpbin.org", 
    "User-Agent": "curl/7.68.0", 
    "X-Amzn-Trace-Id": "Root=1-5f8bcfb2-16756c172d8a435a142afea7"
  }, 
  "json": null, 
  "origin": "999.999.999.999", 
  "url": "http://httpbin.org/post"
}

なお、data.txt は以下のコマンドで作成したファイルです。これはUTF-8ではデコードできないバイナリです。

$ printf "a\0b\x80c" > data.txt 

wgetコマンド

--post-file というオプションでファイル名を指定します。

$ wget --post-file=data.txt --header='Content-Type: application/octet-stream' 'http://httpbin.org/post' -q -O -
{
  "args": {}, 
  "data": "data:application/octet-stream;base64,YQBigGM=", 
  "files": {}, 
  "form": {}, 
  "headers": {
    "Accept": "*/*", 
    "Accept-Encoding": "identity", 
    "Content-Length": "5", 
    "Content-Type": "application/octet-stream", 
    "Host": "httpbin.org", 
    "User-Agent": "Wget/1.20.3 (linux-gnu)", 
    "X-Amzn-Trace-Id": "Root=1-5f8bd025-012893945a1be31b382629db"
  }, 
  "json": null, 
  "origin": "999.999.999.999", 
  "url": "http://httpbin.org/post"
}

--post-file=---post-file=/dev/stdin などとしても標準入力は使えませんでした。

AWS SAMとCloudFormationで同じ構成のAPI Gateway + Lambdaを構築

API Gateway + Lambdaの同じ構成をSAMとCloudFormationの2通りで作成しました。

SAMのほうが簡単に作成できるのですが、細かい設定が中途半端に隠蔽されている感じが好きではないです。

CloudFormationのほうがテンプレートが長いのですが、細かい設定ができます。

SAM

aws-sam-cli のインストールが必要です。

$ pip install aws-sam-cli

$ sam --version
SAM CLI, version 1.6.2

SAMのテンプレートの雛形をコマンドで作成します。

$ sam init --runtime python3.8
Which template source would you like to use?
        1 - AWS Quick Start Templates
        2 - Custom Template Location
Choice: 1

Project name [sam-app]: hello1

Cloning app templates from https://github.com/awslabs/aws-sam-cli-app-templates.git

AWS quick start application templates:
        1 - Hello World Example
        2 - EventBridge Hello World
        3 - EventBridge App from scratch (100+ Event Schemas)
        4 - Step Functions Sample App (Stock Trader)
        5 - Elastic File System Sample App
Template selection: 1

-----------------------
Generating application:
-----------------------
Name: hello1
Runtime: python3.8
Dependency Manager: pip
Application Template: hello-world
Output Directory: .

Next steps can be found in the README file at ./hello1/README.md

でき上がったテンプレートのファイル構成は以下のとおりです。

$ cd hello1

$ tree
.
├── events
│   └── event.json
├── hello_world
│   ├── app.py
│   ├── __init__.py
│   └── requirements.txt
├── README.md
├── template.yaml
└── tests
    └── unit
        ├── __init__.py
        └── test_handler.py

4 directories, 8 files

template.yamlsamコマンドにより自動生成されますが、Resourcesは次の内容が書かれています。CloudFormationで書くよりも短いです。

Resources:
  HelloWorldFunction:
    Type: AWS::Serverless::Function
    Properties:
      CodeUri: hello_world/
      Handler: app.lambda_handler
      Runtime: python3.8
      Events:
        HelloWorld:
          Type: Api
          Properties:
            Path: /hello
            Method: get

これをデプロイするには以下のコマンドです。 --profile AWS_CREDENTIAL_PROFILE_NAME のところは ~/.aws/credentials に複数のプロファイルが設定されている場合に必要に応じて指定するものです。 --s3-bucket MYBUCKET_NAME はLambdaのソースコードを保存するS3バケット名を指定します。

$ sam package --profile AWS_CREDENTIAL_PROFILE_NAME --template-file template.yaml --output-template-file packaged.yaml --s3-bucket MYBUCKET_NAME --s3-prefix hello1

$ sam deploy --profile AWS_CREDENTIAL_PROFILE_NAME --region ap-northeast-1 --template-file packaged.yaml --stack-name hello1 --capabilities CAPABILITY_IAM

これでAPI Gatewaycurlコマンドでアクセスできます。

$ curl 'https://xxxxxxxxxx.execute-api.ap-northeast-1.amazonaws.com/Prod/hello'
{"message": "hello world"}

このSAMにより作成されるCloudFormationのStackのテンプレートは以下のコマンドで確認できます。JSON形式です。

$ aws --profile AWS_CREDENTIAL_PROFILE_NAME cloudformation get-template --stack-name hello1 | jq .TemplateBody -C | less -R

CloudFormation

上記SAMで作成したAWSのリソースとほぼ同じ構成をCloudFormationで作成します。

次のようなディレクトリ構成で2ファイルのみです。

$ tree
.
├── hello_world
│   └── app.py
└── template.yaml

1 directory, 2 files

template.yaml は以下の内容です。

AWSTemplateFormatVersion: '2010-09-09'
Resources:
  HelloWorldFunction:
    Type: AWS::Lambda::Function
    Properties:
      Code: hello_world
      Handler: app.lambda_handler
      FunctionName: hello2
      Role: !GetAtt HelloWorldFunctionRole.Arn
      Runtime: python3.8
      Timeout: 3
  HelloWorldFunctionRole:
    Type: AWS::IAM::Role
    Properties:
      AssumeRolePolicyDocument:
        Version: 2012-10-17
        Statement:
          - Action:
              - "sts:AssumeRole"
            Effect: Allow
            Principal:
              Service:
                - lambda.amazonaws.com
      ManagedPolicyArns:
        - "arn:aws:iam::aws:policy/service-role/AWSLambdaBasicExecutionRole"
  ServerlessRestApi:
    Type: AWS::ApiGateway::RestApi
    Properties:
      Body:
        info:
          version: 1.0
          title: !Ref AWS::StackName
        paths:
          "/hello":
            get:
              x-amazon-apigateway-integration:
                httpMethod: POST
                type: aws_proxy
                uri: !Sub arn:aws:apigateway:${AWS::Region}:lambda:path/2015-03-31/functions/${HelloWorldFunction.Arn}/invocations
        swagger: 2.0
  ServerlessRestApiProdStage:
    Type: AWS::ApiGateway::Stage
    Properties:
      DeploymentId: !Ref ServerlessRestApiDeployment
      RestApiId: !Ref ServerlessRestApi
      StageName: Prod
  ServerlessRestApiDeployment:
    Type: AWS::ApiGateway::Deployment
    Properties:
      RestApiId: !Ref ServerlessRestApi
      StageName: Stage
  HelloWorldFunctionHelloWorldPermissionProd:
    Type: AWS::Lambda::Permission
    Properties:
      Action: lambda:InvokeFunction
      Principal: apigateway.amazonaws.com
      FunctionName: !Ref HelloWorldFunction
      SourceArn: !Sub
        - arn:aws:execute-api:${AWS::Region}:${AWS::AccountId}:${__ApiId__}/${__Stage__}/GET/hello
        - __Stage__: "*"
          __ApiId__: !Ref ServerlessRestApi

hello_world/app.py はSAMのケースと同じPythonソースです。次の内容です。

import json

def lambda_handler(event, context):
    return {
        "statusCode": 200,
        "body": json.dumps({
            "message": "hello world",
        }),
    }

これをデプロイするには以下のコマンドです。 --profile AWS_CREDENTIAL_PROFILE_NAME のところは ~/.aws/credentials に複数のプロファイルが設定されている場合に必要に応じて指定するものです。 --s3-bucket MYBUCKET_NAME はLambdaのソースコードを保存するS3バケット名を指定します。

$ aws --profile AWS_CREDENTIAL_PROFILE_NAME cloudformation package --template-file template.yaml --s3-bucket MYBUCKET_NAME --s3-prefix hello2 --output-template-file packaged.yaml

$ aws --profile AWS_CREDENTIAL_PROFILE_NAME cloudformation deploy --template-file packaged.yaml --stack-name hello2 --capabilities CAPABILITY_IAM

これでAPI Gatewaycurlコマンドでアクセスできます。

$ curl 'https://xxxxxxxxxx.execute-api.ap-northeast-1.amazonaws.com/Prod/hello'
{"message": "hello world"}

このCloudFormationのStackのテンプレートは以下のコマンドで確認できます。といってもローカルに残っている package.yaml と同じです。YAML形式です。

$ aws --profile AWS_CREDENTIAL_PROFILE_NAME cloudformation get-template --stack-name hello2 | jq .TemplateBody -r | less

JavaScript AWS SDKでS3にある画像をブラウザに表示

JavaScriptAWS SDKを使って、S3にある画像ファイルをブラウザから直接取得して表示してみました。

前提

  • S3バケットに画像ファイルが保存されています。
  • S3バケットはパブリックアクセスを拒否しています。IAMユーザが必要です。
  • IAMユーザのアクセスキー、シークレットキーをJavaScriptのソースにハードコーディングしてもよいものとします。
  • ローカルでの検証で、ブラウザ上のURLはhttp://localhost:8080とします。

S3バケットのCORS設定

S3バケットにてCORS(Cross-Origin Resource Sharing)の設定が必要です。この設定がないと、ブラウザのコンソールに以下のようなエラーメッセージが表示され、画像が表示できません。

Access to XMLHttpRequest at 'https://example.s3.ap-northeast-1.amazonaws.com/1.jpg' from origin 'http://localhost:8080' has been blocked by CORS policy: Response to preflight request doesn't pass access control check: No 'Access-Control-Allow-Origin' header is present on the requested resource.

CORSについては以下のAWS公式ドキュメントに説明があります。

AWSマネジメントコンソールからはS3バケットのPermissionsのCORS configurationのところにXMLを書くことで設定できます。

f:id:suzuki-navi:20201015165112p:plain

以下の内容のXMLを書いておきます。

<?xml version="1.0" encoding="UTF-8"?>
<CORSConfiguration xmlns="http://s3.amazonaws.com/doc/2006-03-01">
    <CORSRule>
        <AllowedOrigin>*</AllowedOrigin>
        <AllowedMethod>GET</AllowedMethod>
        <AllowedHeader>*</AllowedHeader>
    </CORSRule>
</CORSConfiguration>

ソースコード

HTMLファイルとJSファイルの2ファイルです。

$ tree
.
├── index.html
└── lib.js

0 directories, 2 files

AWS SDKをHTMLファイルから読み込んでいます。

Vue.jsも使ってますが、便利だから使ったのみで、ここでは本質的ではありません。

index.html

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<title>S3 Image Viewer Sample</title>
<script src="https://cdn.jsdelivr.net/npm/vue@2.6.12" defer></script>
<script src="https://sdk.amazonaws.com/js/aws-sdk-2.771.0.min.js" defer></script>
<script src="lib.js" defer></script>
</head>
<body>
  <div id="body">
    <s3-image></s3-image>
  </div>
</body>
</html>

lib.js

// リージョンとS3バケット名と画像ファイルのパス
AWS.config.region = "ap-northeast-1";
const s3BucketName = "BUCKETNAME";
const s3Key = "KEY";

// IAMユーザのアクセスキーとシークレットキー
const credentials = new AWS.Credentials();
credentials.accessKeyId = "XXXXXXXXXXXXXXXXXXXX";
credentials.secretAccessKey = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
AWS.config.credentials = credentials;

const s3ImageData = {
    content: false,
};

const s3 = new AWS.S3();
s3.getObject({
    Bucket: s3BucketName,
    Key: s3Key,
}, function (err, data) {
    if (err) {
        console.log(err);
        return;
    }
    s3ImageData.content = data.Body;
    console.log(data);
});

Vue.component("s3-image", {
    data: function () { return {
        s3ImageData: s3ImageData,
    };},
    computed: {
        imgurl: function () {
            if (s3ImageData.content === false) return "";
            const bytes1 = s3ImageData.content;
            var bytes2 = "";
            for (var i = 0, len = bytes1.byteLength; i < len; i++) {
                bytes2 += String.fromCharCode(bytes1[i]);
            }
            return "data:image/jpeg;base64," + window.btoa(bytes2);
        },
    },
    template: `
        <img v-bind:src="imgurl">
    `,
});

new Vue({ el: "#body" })

実行

以下のようなコマンドで、ローカル検証用の簡易的なHTTPサーバが立ち上がります。

$ python -m http.server 8080

HTTPサーバ起動後にブラウザで http://localhost:8080 にアクセスすると、S3にあった画像が表示されています。エラーがあればブラウザのコンソールにエラーメッセージがあるかもしれません。

AtCoder参戦日記 ABC179 ― 茶色になる

AtCoderの3回目の参加となった2020/09/19のABC179の記録です。

3完でした。4問目と5問目は、どちらもコードを書きましたが、時間内に正答に至りませんでした。

問題 結果 言語
A Java
B Scala (競技後にPython)
C Scala (競技後にPython)
D 競技後にJava
E 競技後にJava
F

茶色にはなれました。

f:id:suzuki-navi:20201013221841p:plain

A - Plural Form

問題

JavaendsWithに相当するメソッドがほかの言語ですぐに出てこなかったので、Javaで書きました。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    var s = sc.next();
    if (s.endsWith("s")) {
      System.out.println(s + "es");
    } else {
      System.out.println(s + "s");
    }
  }
}

B - Go to Jail

問題

JavaっぽいScalaコードになりました。練習のためにJava/Scala以外の言語を選択すればよかった。。。と思ったので、時間後にPythonで書きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val ds = Array.fill(n)((sc.nextInt(), sc.nextInt()));
  val ds2 = ds.map { case (a, b) => a == b }
  var c1: Int = 0;
  var c2: Int = 0;
  (0 until n).foreach { i =>
    if (ds2(i)) {
      c2 += 1;
      if (c1 < c2) {
        c1 = c2;
      }
    } else {
      c2 = 0;
    }
  }
  println(if (c1 >= 3) "Yes" else "No");
}
n = int(input())
ds = [[int(s) for s in input().split()] for _ in range(n)]

count = 0
for i in range(n):
    if ds[i][0] == ds[i][1]:
        count += 1
        if count == 3:
            print("Yes")
            exit(0)
    else:
        count = 0
print("No")

C - A x B + C

問題

この問題においていちばん書きやすいScalaになりました。時間後に練習のためにPythonでも書きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val answer = (1 to (n-1)).map(i => (n-1) / i).sum;
  println(answer);
}
n = int(input())
answer = sum([(n - 1) // a for a in range(1, n)])
print(answer)

D - Leaping Tak

問題

動的計画法で素直に解いてTLEになったあと、高速化の手法が思いつきませんでした。

以下は解説を読んだあとに書いたコードです。

import java.util.Scanner;

class Main {
  private static int[] table;
  private static int m = 998244353;
  private static int[][] lrs;

  private static void calc(int x) {
    long sum = table[x - 1];
    if (x == 2) sum = 0;
    for (int i = 0; i < lrs.length; i++) {
      int s = lrs[i][0];
      int e = lrs[i][1];
      if (x - e > 1) {
        sum = (sum + m - table[x - e - 1]) % m;
      }
      if (x - s >= 1) {
        sum = (sum + table[x - s]) % m;
      }
    }
    table[x] = (int)sum;
  }

  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    lrs = new int[k][2];
    for (int i = 0; i < k; i++) {
      lrs[i][0] = sc.nextInt();
      lrs[i][1] = sc.nextInt();
    }
    table = new int[n + 1];
    table[1] = 1;

    for (int i = 2; i <= n; i++) {
      calc(i);
    }
    var answer = table[n];
    System.out.println(answer);
  }
}

E - Sequence Sum

問題

m-1 またはその約数で周期性があると思い込んでしまっていたので、WAを解決できませんでした。以下は解説を読んで、勘違いに気がついたあとに書いたコードです。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    long n = sc.nextLong();
    int x = sc.nextInt();
    int m = sc.nextInt();

    long answer = 0;
    int x2 = x;
    long i = 0;

    var s = new int[m];
    var sb = new int[(m + 31) / 32];
    for (; ; i++) {
      if ((sb[x2 / 32] & (1 << (x2 % 32))) != 0) {
        int j = (int)i - 1;
        for (; j >= 0; j--) {
          if (s[j] == x2) {
            break;
          }
        }
        long answer2 = 0;
        for (int k = j; k < i; k++) {
          answer2 += s[k];
        }
        answer += (n - i) / (i - j) * answer2;
        i += (n - i) / (i - j) * (i - j);
        break;
      }
      if (i >= n) break;
      answer += x2;
      s[(int)i] = x2;
      sb[x2 / 32] |= 1 << (x2 % 32);
      x2 = (int)((long)x2 * x2 % m);
    }
    for (; ; i++) {
      if (i >= n) break;
      answer += x2;
      x2 = (int)((long)x2 * x2 % m);
    }

    System.out.println(answer);
  }
}

MNISTのニューラルネットワークでの学習の隠れ層のニューロン数と精度の関係

前回の記事に続いて、今回は隠れ層のニューロンの数と精度の関係を見てみました。

size hidden_size process_time train_loss train_accuracy test_loss test_accuracy
60000 [8] 29.06 0.2370 0.9328 0.2473 0.9296
60000 [64] 44.79 0.0208 0.9942 0.0928 0.9740
60000 [512] 103.64 0.0047 0.9985 0.0797 0.9830
60000 [64, 64] 41.83 0.0159 0.9947 0.1170 0.9722
60000 [64, 64, 64] 44.94 0.0199 0.9934 0.1090 0.9757

左から、訓練用データサイズ、隠れ層のニューロン数、処理時間(秒)、訓練データでの損失関数値、訓練データでの精度、テストデータでの損失関数値、テストデータでの精度です。

隠れ層を2層、3層にしたときも試したので、隠れ層のニューロン数を配列で表現しています。

層を増やしてもあまり精度は変わらなかったです。

Pythonコード

Pythonコードを残しておきます。前回の記事とほとんど同じです。Google Colaboratoryで実行しました。

import time
import numpy as np
from matplotlib import pyplot as plt
import tensorflow as tf
from tensorflow.keras.datasets import mnist

plt.rcParams['figure.figsize'] = (16.0, 7.0)

(x_train, y_train), (x_test, y_test) = mnist.load_data()

# 入力と出力サイズ
in_size = 28 * 28
out_size = 10

# モデル構造を定義
def createModel(hidden_size):
  model = tf.keras.models.Sequential()
  if len(hidden_size) == 1:
    model.add(tf.keras.layers.Dense(hidden_size[0], activation='relu', input_shape=(in_size,)))
    model.add(tf.keras.layers.Dense(out_size, activation='softmax'))
  else:
    model.add(tf.keras.layers.Dense(hidden_size[0], activation='relu', input_shape=(in_size,)))
    for i in range(1, len(hidden_size)):
      model.add(tf.keras.layers.Dense(hidden_size[i], activation='relu'))
    model.add(tf.keras.layers.Dense(out_size, activation='softmax'))
  return model

# 学習の様子をグラフへ描画
def plotLearning(result):
  fig = plt.figure()

  xs = range(1, len(result.history['loss']) + 1)

  # ロスの推移をプロット
  ax1 = fig.add_subplot(1, 1, 1)
  ax1.set_ylim(0, 2.5)
  ax1.set_ylabel('Loss')
  ax1.plot(xs, result.history['loss'])
  ax1.plot(xs, result.history['val_loss'])

  # 正解率の推移をプロット
  ax2 = ax1.twinx()
  ax2.set_ylim(0.75, 1.0)
  ax2.set_ylabel('Accuracy')
  ax2.plot(xs, result.history['accuracy'])
  ax2.plot(xs, result.history['val_accuracy'])

  plt.title('Loss & Accuracy')
  plt.legend(['train', 'test'], loc='upper left')
  plt.show()

def calc(train_size, epochs, hidden_size):
  model = createModel(hidden_size)

  # モデルを図で表示
  display(tf.keras.utils.plot_model(model, show_shapes=True))

  # モデルを構築
  model.compile(
      loss = "categorical_crossentropy",
      optimizer = "adam",
      metrics=["accuracy"])

  start = time.time()
  print("train_size: %d, epochs: %d" % (train_size, epochs))
  x_train_reshape = x_train.reshape(-1, in_size).astype('float32') / 255
  x_test_reshape = x_test.reshape(-1, in_size).astype('float32') / 255
  y_train_onehot = tf.keras.backend.one_hot(y_train, out_size)
  y_test_onehot = tf.keras.backend.one_hot(y_test, out_size)

  x_train_reshape = x_train_reshape[:train_size]
  y_train_onehot = y_train_onehot[:train_size]

  # 学習を実行
  result = model.fit(x_train_reshape, y_train_onehot,
      batch_size=50,
      epochs=epochs,
      verbose=1,
      validation_data=(x_test_reshape, y_test_onehot))

  processTime = time.time() - start
  print("train_size: %d, epochs: %d, processTime: %f" % (train_size, epochs, processTime))
  plotLearning(result)

  return "| %d | %s | %5.2f | %6.4f | %6.4f | %6.4f | %6.4f |" % (train_size, str(hidden_size), processTime,
    result.history['loss'][-1], result.history['accuracy'][-1],
    result.history['val_loss'][-1], result.history['val_accuracy'][-1])

table = []
table.append(calc(60000, 15, [8]))
table.append(calc(60000, 15, [64]))
table.append(calc(60000, 15, [512]))
table.append(calc(60000, 15, [64, 64]))
table.append(calc(60000, 15, [64, 64, 64]))
for s in table:
  print(s)

AtCoder参戦日記 ABC178 ― 奇跡的な好成績

AtCoderの2回目の参加となった2020/09/13のABC178の記録です。約1ヶ月前のことです。

5問目まで解法を偶然すぐに思いつくことができましたので、奇跡的に成績がよかった回となりました。

正答を出せた5問で使った言語はPythonScalaScalaC++Scalaでした。簡単な問題はPythonが短く書けてよさそう。ロジックが単純に繰り返し処理が中心の場合はC++もよさそう。

問題 結果 言語
A Python
B Scala
C Scala
D C++
E Scala
F

A - Not

問題

短く書けそうなPythonにしました。

a = int(input())
print(1 - a)

B - Product Max

問題

Pythonで完結に書ける自信がなく、パッと書けそうなScalaになりました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val a, b, c, d = sc.nextLong();
  val answer = List(a * c, a * d, b * c, b * d).max;
  println(answer);
}

C - Ubiquity

問題

惰性でScalaで書きました。

以下のコードはコンテスト中に書いたコードですが、自分にとってあまりきれいでなく、のちにElixirでABC178のC Ubiquityを解いてみるの記事でElixirとScalaで書き直しています。

object Main extends App {
  val m = 1000000007;
  def pow(a: Long, b: Int): Long = {
    var x: Long = 1;
    var a2: Long = a;
    var b2: Int = b;
    while (b2 > 0) {
      if ((b2 & 1) != 0) {
        x = x * a2 % m;
      }
      a2 = a2 * a2 % m;
      b2 = b2 >> 1;
    }
    x;
  }
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val a1 = pow(10, n); // all
  val a2 = pow(8, n);  // 0も9も存在しない
  val a3 = (pow(9, n) + m - a2) % m;  // 0は存在するけど9は存在しない
  val answer = (a1 + 3L * m - 2L * a3 - a2) % m;
  println(answer);
}

D - Redistribution

問題

ここで唐突にC++を選択しました。

あとで解説を見たら、2重ループにしなくてももうちょっと簡単に解ける方法があったようです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  long m = 1000000007;

  int s;
  cin >> s;

  if (s < 3) {
    cout << 0 << endl;
    return 0;
  }

  vector<long> series(s + 1);
  series[0] = 0;
  series[1] = 0;
  series[2] = 0;
  for (int i = 3; i <= s; i++) {
    long a = 1;
    for (int j = 0; j <= i - 3; j++) {
      a += series[j];
      a = a % m;
    }
    series[i] = a;
  }
  long answer = series[s];
  cout << answer << endl;
}

E - Dist Max

問題

解き方をちょっと悩みましたが、45度傾いた長方形で囲んで長いほうの辺の長さを求めればいいだけだと気が付けました。

簡潔に書ける言語としてScalaを選択しました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val xys = Array.fill(n)((sc.nextInt, sc.nextInt));
  val xys2 = xys.map { case (x, y) => (x + y, x - y) }
  val x_min = xys2.map(_._1).min;
  val x_max = xys2.map(_._1).max;
  val y_min = xys2.map(_._2).min;
  val y_max = xys2.map(_._2).max;
  val answer = (x_max - x_min) max (y_max - y_min);
  println(answer);
}

F - Contrast

問題

Yes/Noはわかるけど、そのあとの解法が思いつきませんでした。コンテスト中は無理やりScalaで書いたのですが、失敗するテストケースがあり、そのままわからずじまい。