AWS SAM を用いたサーバーレスアプリケーションのデプロイ（ApiGatewayV2とLambda）
本稿の目的
本稿の対象者
- AWSのリソースをコードで管理したい。
- Lambdaをテストしたい
- CloudFormationに興味がある
- パイプラインで自動テスト、ビルド、デプロイまで行いたい
はじめに
こんにちは。新卒1年目のさっちゃんです。早いもので、社会人になって半年も経ちました。この半年は分からないことだらけで、チームのリソースを割いてもらいながら、少しずつ出来ることを増やせたかなと思ってます。新人なんてそんなもんだ。
さて、AWSを触っていると次のような疑問が湧いてきます。
- 使うサービスが多すぎて何作ったか、どんな設定をしたか分からん...。
- Lambdaのテストどうすりゃいいんじゃ...。
- どれを消したらどこまで影響するんだ...。
- 人間の操作ではなく自動でデプロイしてほしい...。
これらを解決してくれるのが AWS SAM (Serverless Application Model) です。
AWS SAMとは
SAMとはなんなのか、公式の説明を引用してみましょう。
AWS サーバーレスアプリケーションモデル (SAM、Serverless Application Model) は、サーバーレスアプリケーション構築用のオープンソースフレームワークです。迅速に記述可能な構文で関数、API、データベース、イベントソースマッピングを表現できます。リソースごとにわずか数行で、任意のアプリケーションを定義して YAML を使用してモデリングできます。デプロイ中、SAM が SAM 構文を AWS CloudFormation 構文に変換および拡張することで、サーバーレスアプリケーションの構築を高速化することができます。 （AWS SAM より引用）
とのことです。なるほど完全に理解した。実はもっとわかりやすい記事があって、大変参考にしたのでここに置いておきます。（この記事見ずにこちらに飛んだ方がいいかもしれない）
記事を移動するのが面倒な方のために、SAMとは何かの部分を引用します。
Serverless Application Model（SAM）は Lambda や API Gateway, DynamoDB のようなサービスを活用したサーバーレスアプリケーションのデプロイに特化した、AWS CloudFormation の拡張機能です。通常の CloudFormation テンプレートと同様に YAML/JSON でテンプレートを定義しますが、素のテンプレートより簡潔に記載できるのが特徴です。 (AWS SAM CLI 再入門 2021.08 より引用)
両者を見ると、SAM が CloudFormation の拡張機能であるということがよくわかります。知らない方もいると思いますので説明しておくと、CloudFormationとはリソースをyaml形式のファイルで一元管理、作成できるAWSのサービスです。テンプレートファイルで AWS リソース(API Gateway, Lambda, Dynamo, Cognitoなどなど)を定義し、S3に保存してコンソール上で指定するか手でアップロードすればそれらを自動で作成してくれます。すごいですね。
SAMの基本はCloudFormationなのですが、CLIベースでより簡潔に、便利にリソースを作成する事ができます。早速やってみましょう。
早速やってみよう
sam-cliのインストールについてはAWS SAM CLI 再入門 2021.08通りにやればいいのでコマンドだけ置いておきます。
brew tap aws/tap brew install aws-sam-cli
また、AWS アカウントを持っていてIAMユーザーを作成したら、aws-cliをインストールして aws configure コマンドで設定を済ませておいてください。
さて、実際にコマンドラインでチャチャっとサーバーレスなアプリケーションを作ってみます。
- sam init
$ sam init
Which template source would you like to use?
1 - AWS Quick Start Templates
2 - Custom Template Location
Choice: 1
What package type would you like to use?
1 - Zip (artifact is a zip uploaded to S3)
2 - Image (artifact is an image uploaded to an ECR image repository)
Package type: 1
Which runtime would you like to use?
1 - nodejs14.x
2 - python3.9
3 - ruby2.7
4 - go1.x
5 - java11
6 - dotnetcore3.1
7 - nodejs12.x
8 - nodejs10.x
9 - python3.8
10 - python3.7
11 - python3.6
12 - python2.7
13 - ruby2.5
14 - java8.al2
15 - java8
16 - dotnetcore2.1
Runtime: 2
Project name [sam-app]:
Cloning from https://github.com/aws/aws-sam-cli-app-templates
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: sam-app
Runtime: python3.9
Architectures: x86_64
Dependency Manager: pip
Application Template: hello-world
Output Directory: .
Next steps can be found in the README file at ./sam-app/README.md
2 . sam deploy -g
cd sam-app
sam deploy -g
Configuring SAM deploy
======================
Looking for config file [samconfig.toml] : Not found
Setting default arguments for 'sam deploy'
=========================================
Stack Name [sam-app]:
AWS Region [ap-northeast-1]:
#Shows you resources changes to be deployed and require a 'Y' to initiate deploy
Confirm changes before deploy [y/N]: y
#SAM needs permission to be able to create roles to connect to the resources in your template
Allow SAM CLI IAM role creation [Y/n]: y
HelloWorldFunction may not have authorization defined, Is this okay? [y/N]: y
Save arguments to configuration file [Y/n]: y
SAM configuration file [samconfig.toml]:
SAM configuration environment [default]:
Looking for resources needed for deployment:
Creating the required resources...
Successfully created!
Managed S3 bucket: aws-sam-cli-managed-default-samclisourcebucket-10c3jq4829zh7
A different default S3 bucket can be set in samconfig.toml
Saved arguments to config file
Running 'sam deploy' for future deployments will use the parameters saved above.
The above parameters can be changed by modifying samconfig.toml
Learn more about samconfig.toml syntax at
https://docs.aws.amazon.com/serverless-application-model/latest/developerguide/serverless-sam-cli-config.html
Uploading to sam-app/c6ce8fa8b5a97dd022ecd006536eb5a4 847 / 847 (100.00%)
Deploying with following values
===============================
Stack name : sam-app
Region : ap-northeast-1
Confirm changeset : True
Deployment s3 bucket : aws-sam-cli-managed-default-samclisourcebucket-10c3jq4829zh7
Capabilities : ["CAPABILITY_IAM"]
Parameter overrides : {}
Signing Profiles : {}
Initiating deployment
=====================
Uploading to sam-app/3dae71abecd1456ad194f6b7925a4129.template 1126 / 1126 (100.00%)
Waiting for changeset to be created..
CloudFormation stack changeset
-------------------------------------------------------------------------------------------------
Operation LogicalResourceId ResourceType Replacement
-------------------------------------------------------------------------------------------------
+ Add HelloWorldFunctionHell AWS::Lambda::Permissio N/A
oWorldPermissionProd n
+ Add HelloWorldFunctionRole AWS::IAM::Role N/A
+ Add HelloWorldFunction AWS::Lambda::Function N/A
+ Add ServerlessRestApiDeplo AWS::ApiGateway::Deplo N/A
yment47fc2d5f9d yment
+ Add ServerlessRestApiProdS AWS::ApiGateway::Stage N/A
tage
+ Add ServerlessRestApi AWS::ApiGateway::RestA N/A
pi
-------------------------------------------------------------------------------------------------
Changeset created successfully. arn:aws:cloudformation:ap-northeast-1:470529257240:changeSet/samcli-deploy1633806768/fb9f510d-4b14-46da-8558-d7a6b81caf48
Previewing CloudFormation changeset before deployment
======================================================
Deploy this changeset? [y/N]: y
2021-10-10 04:13:10 - Waiting for stack create/update to complete
CloudFormation events from changeset
-------------------------------------------------------------------------------------------------
ResourceStatus ResourceType LogicalResourceId ResourceStatusReason
-------------------------------------------------------------------------------------------------
CREATE_IN_PROGRESS AWS::IAM::Role HelloWorldFunctionRole -
CREATE_IN_PROGRESS AWS::IAM::Role HelloWorldFunctionRole Resource creation
Initiated
CREATE_COMPLETE AWS::IAM::Role HelloWorldFunctionRole -
CREATE_IN_PROGRESS AWS::Lambda::Function HelloWorldFunction -
CREATE_COMPLETE AWS::Lambda::Function HelloWorldFunction -
CREATE_IN_PROGRESS AWS::Lambda::Function HelloWorldFunction Resource creation
Initiated
CREATE_IN_PROGRESS AWS::ApiGateway::RestA ServerlessRestApi -
pi
CREATE_IN_PROGRESS AWS::ApiGateway::RestA ServerlessRestApi Resource creation
pi Initiated
CREATE_COMPLETE AWS::ApiGateway::RestA ServerlessRestApi -
pi
CREATE_IN_PROGRESS AWS::ApiGateway::Deplo ServerlessRestApiDeplo -
yment yment47fc2d5f9d
CREATE_IN_PROGRESS AWS::ApiGateway::Deplo ServerlessRestApiDeplo Resource creation
yment yment47fc2d5f9d Initiated
CREATE_IN_PROGRESS AWS::Lambda::Permissio HelloWorldFunctionHell Resource creation
n oWorldPermissionProd Initiated
CREATE_IN_PROGRESS AWS::Lambda::Permissio HelloWorldFunctionHell -
n oWorldPermissionProd
CREATE_COMPLETE AWS::ApiGateway::Deplo ServerlessRestApiDeplo -
yment yment47fc2d5f9d
CREATE_IN_PROGRESS AWS::ApiGateway::Stage ServerlessRestApiProdS -
tage
CREATE_IN_PROGRESS AWS::ApiGateway::Stage ServerlessRestApiProdS Resource creation
tage Initiated
CREATE_COMPLETE AWS::ApiGateway::Stage ServerlessRestApiProdS -
tage
CREATE_COMPLETE AWS::Lambda::Permissio HelloWorldFunctionHell -
n oWorldPermissionProd
CREATE_COMPLETE AWS::CloudFormation::S sam-app -
tack
-------------------------------------------------------------------------------------------------
CloudFormation outputs from deployed stack
-------------------------------------------------------------------------------------------------
Outputs
-------------------------------------------------------------------------------------------------
Key HelloWorldFunctionIamRole
Description Implicit IAM Role created for Hello World function
Value arn:aws:iam::470529257240:role/sam-app-HelloWorldFunctionRole-1RPJFCRUSMHQJ
Key HelloWorldApi
Description API Gateway endpoint URL for Prod stage for Hello World function
Value https://7k76tde9fj.execute-api.ap-northeast-1.amazonaws.com/Prod/hello/
Key HelloWorldFunction
Description Hello World Lambda Function ARN
Value arn:aws:lambda:ap-northeast-1:470529257240:function:sam-app-
HelloWorldFunction-a1yhY93DihkE
-------------------------------------------------------------------------------------------------
Successfully created/updated stack - sam-app in ap-northeast-1
この状態でAWS コンソール上でCloudFormation、Lambda、Api Gatewayをそれぞれみるとリソースが作成されたことが確認できます。
さらに、作成されたAPI GatewayにあるAPIを叩くと動作する事が確認できます。これでサーバーレスなアプリケーションの初めの一歩をデプロイできました。（/Prod とステージ名を入れるのを忘れないように注意です。）
さて、ここまでで行ったことは sam init と sam deploy -gのみで、LambdaやAPI Gatewayの設定は書いた覚えがありません。これらの設定は、sam-app（プロジェクト名）ディレクトリの中のtemplate.yamlにあります。
AWSTemplateFormatVersion: '2010-09-09' Transform: AWS::Serverless-2016-10-31 Description: > sam-app Sample SAM Template for sam-app # More info about Globals: https://github.com/awslabs/serverless-application-model/blob/master/docs/globals.rst Globals: Function: Timeout: 3 Resources: HelloWorldFunction: Type: AWS::Serverless::Function # More info about Function Resource: https://github.com/awslabs/serverless-application-model/blob/master/versions/2016-10-31.md#awsserverlessfunction Properties: CodeUri: hello_world/ Handler: app.lambda_handler Runtime: python3.9 Architectures: - x86_64 Events: HelloWorld: Type: Api # More info about API Event Source: https://github.com/awslabs/serverless-application-model/blob/master/versions/2016-10-31.md#api Properties: Path: /hello Method: get Outputs: # ServerlessRestApi is an implicit API created out of Events key under Serverless::Function # Find out more about other implicit resources you can reference within SAM # https://github.com/awslabs/serverless-application-model/blob/master/docs/internals/generated_resources.rst#api HelloWorldApi: Description: "API Gateway endpoint URL for Prod stage for Hello World function" Value: !Sub "https://${ServerlessRestApi}.execute-api.${AWS::Region}.amazonaws.com/Prod/hello/" HelloWorldFunction: Description: "Hello World Lambda Function ARN" Value: !GetAtt HelloWorldFunction.Arn HelloWorldFunctionIamRole: Description: "Implicit IAM Role created for Hello World function" Value: !GetAtt HelloWorldFunctionRole.Arn
注目してほしいのは、 Resourcesの中のType: AWS::Serverless:Functionです。これにより、この部分はLambdaの設定であることが宣言されており、それに伴ってPropertiesの項目が決定されます。どのリソースにどのようなPropertiesがあるかは公式のリファレンスと睨めっこして書いていきます。この設定の中に
Events: HelloWorld: Type: Api # More info about API Event Source: https://github.com/awslabs/serverless-application-model/blob/master/versions/2016-10-31.md#api Properties: Path: /hello Method: get
と言う部分がありますが、ここではこのLambdaがどういう時に起動するかをTypeで決めています。ApiということはApiGatewayから呼ばれることを指しており、他にもHttpApiはApiGatewayV2から、CognitoはCognitoのトリガーに紐づけられること指します。Propertiesに書かれていることは簡単ですね。
しかしここで思うのは、API Gatewayの設定はどこにも書いていません。また、このLambdaがどのAPI Gatewayに紐づくかも書いていません。実はSAMではCloudFormationと違い、どこにも紐づかないLambdaを作成した場合自動でAPI Gatewayを作成してくれます。これをSAMのドキュメントでは implicit なAPI Gatewayと言っています。（最初見た時はなんのことかわかりませんでした。）また、API GatewayにLambdaを呼び出す権限（ポリシー）をアタッチするなど、権限周りも”いい感じ”にしてくれます。
SAMが勝手にリソースを作成してくれるのは便利ですが、Cognitoによる認証を設定するなどの細かい設定をしたい場合は自分でAPI Gatewayを作成するtemplateを書く必要があります。API Gatewayを書くtemplateの例はいくつもあったので、ここではAPI GatewayV2で作成してみたいと思います。API GatewayV2（HTTP API） については 高速、低コストで、より良いAPIの構築 – HTTP APIが利用可能（GA）になりました | Amazon Web Services ブログをご覧ください。
AWSTemplateFormatVersion: "2010-09-09" Transform: AWS::Serverless-2016-10-31 Description: > sam-app Sample SAM Template for sam-app # More info about Globals: https://github.com/awslabs/serverless-application-model/blob/master/docs/globals.rst Globals: Function: Timeout: 3 Resources: HttpApi: Type: AWS::Serverless::HttpApi Properties: StageName: Prod # Cognitoによる認証を行う場合 # Auth: # Authorizers: # CognitoAuth: # IdentitySource: "$request.header.Authorization" # JwtConfiguration: # issuer: !Sub https://cognito-idp.${AWS::Region}.amazonaws.com/${UserPool} # audience: # - HelloWorldFunction: Type: AWS::Serverless::Function # More info about Function Resource: https://github.com/awslabs/serverless-application-model/blob/master/versions/2016-10-31.md#awsserverlessfunction Properties: CodeUri: hello_world/ Handler: app.lambda_handler Runtime: python3.9 Architectures: - x86_64 # VpcConfig: VPCの設定 # Policies: Lambdaに対する権限の追加 Events: HelloWorld: Type: HttpApi # More info about API Event Source: https://github.com/awslabs/serverless-application-model/blob/master/versions/2016-10-31.md#api Properties: Path: /hello Method: get # API Gateway の場合は RestApiId。今回はAPI GatewayV2 ApiId: !Ref HttpApi # Cognitoによる認証を挟む場合 # Auth: # Authorizer: CognitoAuth # Cognitoによる認証を行いたい場合 # UserPool: # Type: AWS::Cognito::UserPool # Properties: # UserPoolName: test # Policies: # PasswordPolicy: # MinimumLength: 8 # RequireLowercase: true # RequireNumbers: true # RequireSymbols: true # RequireUppercase: true # UsernameAttributes: # - email # Schema: # - AttributeDataType: String # Name: email # Required: false Outputs: HelloWorldApi: Description: "API GatewayV2 endpoint URL for Prod stage for Hello World function" # ここも変えたよ Value: !Sub "https://${HttpApi}.execute-api.${AWS::Region}.amazonaws.com/Prod/hello/" HelloWorldFunction: Description: "Hello World Lambda Function ARN" Value: !GetAtt HelloWorldFunction.Arn HelloWorldFunctionIamRole: Description: "Implicit IAM Role created for Hello World function" Value: !GetAtt HelloWorldFunctionRole.Arn
deployしてみます。sam deploy(-g は不要)
できました。嬉しい。ぴーすぴーす✌️
sam deleteでリソースを一括で消します。
sam delete
Are you sure you want to delete the stack sam-app in the region ap-northeast-1 ? [y/N]: y
Are you sure you want to delete the folder sam-app in S3 which contains the artifacts? [y/N]: y
- Deleting S3 object with key sam-app/c6ce8fa8b5a97dd022ecd006536eb5a4
- Deleting S3 object with key sam-app/124bee4a9ce8b2a3aac7814cb28ec561.template
- Deleting S3 object with key sam-app/19ddbe63ffda195b5668e7fc8c0391c6.template
- Deleting S3 object with key sam-app/3dae71abecd1456ad194f6b7925a4129.template
- Deleting S3 object with key sam-app/a64b7c7012f3a53e9bbb4c723db373d3.template
- Deleting Cloudformation stack sam-app
Deleted successfully
綺麗さっぱりなくなりました。
gitlabのパイプラインで自動テスト、デプロイ
書くのに疲れてきました...。
AWS SAM CLI 再入門 2021.08をみると、sam pipeline bootstrap, sam pipeline init --bootstrapで.gitlab-ciなど必要なファイルは生成されます。ここにはpytestやdeployをパイプラインで行うための雛形が書かれているのでここから自分用に変えていけばLambdaのテストも可能です。例えばAPI GatewayからのLambdaの呼び出しに対してのモックの仕方はsamによって自動生成されているのでありがたいです。
import json import pytest from hello_world import app @pytest.fixture() def apigw_event(): """ Generates API GW Event""" return { "body": '{ "test": "body"}', "resource": "/{proxy+}", "requestContext": { "resourceId": "123456", "apiId": "1234567890", "resourcePath": "/{proxy+}", "httpMethod": "POST", "requestId": "c6af9ac6-7b61-11e6-9a41-93e8deadbeef", "accountId": "123456789012", "identity": { "apiKey": "", "userArn": "", "cognitoAuthenticationType": "", "caller": "", "userAgent": "Custom User Agent String", "user": "", "cognitoIdentityPoolId": "", "cognitoIdentityId": "", "cognitoAuthenticationProvider": "", "sourceIp": "127.0.0.1", "accountId": "", }, "stage": "prod", }, "queryStringParameters": {"foo": "bar"}, "headers": { "Via": "1.1 08f323deadbeefa7af34d5feb414ce27.cloudfront.net (CloudFront)", "Accept-Language": "en-US,en;q=0.8", "CloudFront-Is-Desktop-Viewer": "true", "CloudFront-Is-SmartTV-Viewer": "false", "CloudFront-Is-Mobile-Viewer": "false", "X-Forwarded-For": "127.0.0.1, 127.0.0.2", "CloudFront-Viewer-Country": "US", "Accept": "text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8", "Upgrade-Insecure-Requests": "1", "X-Forwarded-Port": "443", "Host": "1234567890.execute-api.us-east-1.amazonaws.com", "X-Forwarded-Proto": "https", "X-Amz-Cf-Id": "aaaaaaaaaae3VYQb9jd-nvCd-de396Uhbp027Y2JvkCPNLmGJHqlaA==", "CloudFront-Is-Tablet-Viewer": "false", "Cache-Control": "max-age=0", "User-Agent": "Custom User Agent String", "CloudFront-Forwarded-Proto": "https", "Accept-Encoding": "gzip, deflate, sdch", }, "pathParameters": {"proxy": "/examplepath"}, "httpMethod": "POST", "stageVariables": {"baz": "qux"}, "path": "/examplepath", } def test_lambda_handler(apigw_event, mocker): ret = app.lambda_handler(apigw_event, "") data = json.loads(ret["body"]) assert ret["statusCode"] == 200 assert "message" in ret["body"] assert data["message"] == "hello world" # assert "location" in data.dict_keys()
おわりに
今回は
を目標として、SAMについて説明し実際にAPIGatewayV2、Lambdaを作成しました。特にAPI GatewayV2のテンプレートに関する記事は少なくて苦労しました...。 また、SAMを使ってデプロイしようとするとどうしてもCloudFormationの文法が必要になるので、一石二鳥（？）で勉強できます。楽しいね。 個人的にはCloudFormationの公式ドキュメントは見づらいし機械翻訳も変なので、慣れていないうちはterraformのリファレンスと見比べながら見てました。
Neptune, SAMときたら次は何について書こうか思案中です。pytestでlambdaの単体テストを書いてみようかな。
参考
【AWS Black Belt Online Seminar】AWS Serverless Application Model
Amazon Neptune 触ってみた。~グラフDB楽しい。~
はじめに
本稿の対象者
- グラフDBについて興味がある人
- グラフがどう使われるか知りたい人
- Amazon Neptune をサービスに取り入れたい人
自己紹介
こんにちは。4月から東京にて仕事でパソコンをぽちぽちしているさっちゃんです。開発未経験でIT企業に入って5ヶ月(研修3ヶ月、配属されて2ヶ月)、普段はバックエンドでAPIの設計、実装(Java, Spring boot)、テストの自動化をアジャイルで開発してます。二週間ほど前に突然AWSに関する仕事があったので参加させてもらって色々勉強していたところ、Amazon Neptuneが面白かったので共有したいと思います。AWSについては何も知らなかったんですが便利ですね。
本稿の構成
Amazon Neptune はフルマネージドのグラフDBなんですが、話の流れとしてはまずグラフの基本的な用語と身の回りのグラフ構造について説明します。その後でグラフDBについて簡単に言及した後でAmazon Neptuneとその query言語である Gremlin について書きます。ここまで読めばjupyter notebookを使ってAmazon Neptuneに触ることは可能なのですが、サービスに組み込む際やAWS Lambdaを使う際にはpythonやJavaなどで扱えた方がいいと思います。ここではpythonを使ってグラフDBを触るためにgremlin_pythonというライブラリの紹介をします。
グラフとは何か。我々の身の回りにあるグラフ構造について。
本章では本稿で言うグラフとは何かと、グラフの例について挙げます。
グラフとは
本稿で言うグラフとは次の画像のようなものです。
もう少し詳しく説明すると、グラフ理論におけるグラフとは大雑把に言うと頂点（vertex, node）と辺（edge）から成る集合（有向グラフは順序対
, where
: 集合,
: 順序対
のこと）ですが、本稿で言うグラフはそれに加えて各頂点と辺に「どういう種類のノード、辺か」（上の例で言う person, cat, food, Loves, Knows）というラベルと、それぞれの頂点と辺に対してpropertyという情報を持たせたものです。これを用いると、現実世界にある物（人間、猫、アカウントなど）とそれらの関係を表現することができます。
永続化の手段としてのグラフDBについて
ここまでの話をまとめると、グラフとは頂点（vertex）と辺（edge）とpropertyから成る、何らかの関係性を表す図のことでした。本節では永続化の手段としてグラフDBを使用する意義について述べます。
私が（そしておそらく多くの方が）永続化の手段として真っ先に思い浮かぶのはRelational DBです。物の関係性には1対1、1対多、多対多がありますが、1対1ならもちろんAmazon Dynamo DBなどのkey-value形式で保存できるDBを使えばいいですし、1対多はRDBが得意とするところだと思います。ここで多対多の場合について考えると、RDBだと中間テーブルを使うなどして多対多を1対多に落とし込む方法が一般的だと思いますが、テーブルが多くなるにつれて実現したいことに対してクエリが複雑になったりパフォーマンスが落ちるということがあります。そのような問題を回避する策として、保存したい対象がグラフ構造を持っているならばグラフDBという選択肢があります。
グラフDBとは、上にあげた例のようなモデリングされたグラフ構造を"そのまま"保存してしまうという方法です。これによって複雑な関係を持つデータでも比較的簡単なクエリで直感的に操作できます。また、パフォーマンスについては保存したい対象に寄ると思いますが、データが少ないうちはRDBの方が速いがデータ量が多くなるとグラフDBの方がデータの探索は速くなるという論文もありました。どうやらデータ数が増えるとテーブルのJoinがボトルネックになるようです。
Comparison of Graph Databases and Relational Databases When Handling Large-Scale Social Data
Amazon Neptuneとgremlinについて
グラフDBの選択肢の一つとして Amazon Neptune があります。Amazon Neptune はAWSのサービスの一つで、フルマネージドのグラフDBです。詳しくは公式サイトを見てほしいのですが、個人的には他のAWSサービスと連携させやすい点や使おうと思えばすぐに使い始められるところ、jupyter notebookから操作できることが気に入っています。Amazon Neptune ML を使えば機械学習を使ってノードを分類したりプロパティを推論することができるようです。
また、Neptune はクエリ言語としてApache TinkerPop Gremlin というものを使っていますが、これが慣れれば直感的にグラフを操作できるのでとても気に入っています。（クエリを流すのに少し癖がありますが...。）また多くの言語に対してdriverが用意されており、自分はAWS Lambdaの中でgremlin_pythonというライブラリを使ってグラフを生成したり探索しています。本章の残りでは実際にjupyter notebookからグラフを作ってみます。
jupyter notebookでグラフを触ってみる
AWS アカウントは作っている前提で進めます。aws consoleにいって、Neptune を検索します。あとは流れに乗って適当にぽちぽちやって（notebookの名前は適当にtestとかにしておく）数分待つとnotebookが生成されます。左側のナビゲーションのNotebooksからopen notebookを選択するとjupyter notebookに入れます。Gremlinの使い方はこのNotebooksに載っていますが、試しに本稿の例であげたグラフを作ってみましょう。
適当なディレクトリで、右側にあるNewボタンからPython3を選択してnotebookを作ります。Untitledをクリックするとノートの名前を変えられるので、testとかでもしておきましょう。
頂点を作ってみる
では早速グラフを生成してみます。次のコマンドを実行してみてください。
%%gremlin
g.addV("person").property("name", "Toshiaki").property("age", 24)
%%gremlinはGremlinというクエリ言語を使うという宣言で、この宣言がされるとgというのは暗黙のうちにグラフ全体を表すオブジェクトになります。このコマンドでname: Toshiaki, age: 24をpropertyに持つ頂点をグラフに加えることができます。
頂点ができているか確認する
本当にできているかは次のコマンドで確認できます。
%%gremlin
g.V().hasLabel("person").has("name", "Toshiaki")
このコマンドについて補足すると、g.V()まででグラフ上の頂点全てを取ってきます。g.V().hasLabel("person")でpersonというラベルを持つ頂点に絞り、.hasでプロパティを使って絞る事ができます。ただこれだと分かりにくいので、最後に.valueMap()をつけると頂点のプロパティの中を見る事ができます。
%%gremlin
g.V().hasLabel("person").has("name", "Toshiaki").valueMap()
また、次のコマンドでもっと見やすい形にできます。
%%gremlin -p v,oute,inv g.V().path().by(elementMap())
一つのセルで複数のクエリを実行する
頂点を二つ生成しようとしても、次のようなコマンドはfoodラベルを持った頂点しか生成されません。(g.V()コマンドで確認してみてください)
%%gremlin
g.addV("cat").property("name", "Azuki").property("age", 3)
g.addV("food").property("type", "cat-food").property("company", "HOGEHOGE-FOOD")これを思ったように実行するには、次の二通りがあります。
%%gremlin
g.addV("cat").property("name", "Azuki").property("age", 3).next()
g.addV("food").property("type", "cat-food").property("company", "HOGEHOGE-FOOD")%%gremlin
g.addV("cat").property("name", "Azuki").property("age", 3)
.addV("food").property("type", "cat-food").property("company", "HOGEHOGE-FOOD")これらの違いとしては、前者はクエリをnext()の部分で分けて流しているのに対して後者は一つのクエリとして流しているらしいです。
辺を描く
ここまでで頂点が三つ生成できるようになりました。
では続いて辺を描いてみましょう。
%%gremlin
g.addE("Likes").from(g.V().hasLabel("person").has("name", "Toshiaki"))
.to(g.V().hasLabel("cat").has("name", "Azuki"))構文的には g.addE("Label").from(頂点).to(頂点)と直感的です。辺ができたかどうかは次のコマンドで確認できます。
%%gremlin -p v,oute,inv g.V().outE().inV().path()
あとは同じように辺を作れば完成です。お疲れ様でした。
%%gremlin
g.addE("Loves").from(g.V().hasLabel("person").has("name", "Toshiaki"))
.to(g.V().hasLabel("cat").has("name", "Azuki")).next()
g.addE("Knows").to(g.V().hasLabel("person").has("name", "Toshiaki"))
.from(g.V().hasLabel("cat").has("name", "Azuki")).next()
g.addE("Loves").to(g.V().hasLabel("food"))
.from(g.V().hasLabel("cat").has("name", "Azuki"))
辺を辿って頂点を見つける
personというラベルを持つ頂点からLovesというラベルを持つ辺の先にある頂点を探すには次のようにします。
%%gremlin
g.V().hasLabel("person").out("Loves").valueMap()
次にやること
もっと触ってみたいと思ったら、Notebookにあるgetting-startedやサンプルをやっていくと楽しいです。また、pythonなどで扱うためにgremlin_pythonというライブラリもあります。例えばAmazon API Gateway のオーソライザーとしてcognitoを使って認証を行い、そのユーザー情報を使ってLambdaの中でログインしてきたユーザーの頂点を作って、アプリケーションの中でフォローなどの関係ができたらNeptuneに辺を作成しにいく。そしてグラフを使ってリコメンデーションする。みたいな使い方もできそうですね。Pythonを使ってNeptuneを操作する
最後にpythonを使って上記と同じことを行うコードを置いておきます。ここではAWS Lambdaからグラフを操作することを想定しています。 gremlin_pythonは少し癖があるますが、慣れれば使うのは簡単です。接続の設定などは調べてもらう必要がありますが、雰囲気はこんな感じになると思います。toList()でクエリを流します。 ちなみにlocalで書いたコードをAWS Lambdaにデプロイするための方法の一つとして、インストールしたパッケージごとzipで固めてaws cliでぽちぽちやる方法がありますが、ここではAWSコンソール上でコードを書いてみてください。（ある程度コード量が多くなるとコンソール上ではコードをいじれなくなる。） ちゃんと書けているかはprintしてCloutWatchでログを見るか、jupyter notebookで見ると良いと思います。
from gremlin_python.driver.driver_remote_connection import DriverRemoteConnection
from gremlin_python.process.anonymous_traversal import traversal
from gremlin_python.process.traversal import T
def lambda_handler(event, context):
# 接続の設定は調べてね。
g = traversal().withRemote(DriverRemomteConnection("wss://(endpoint_name):(port_number)/gremlin','g'"))
# 頂点の生成
person_vertex = g.addV("person")\
.property("name", "Toshiaki")\
.property("age", 24).toList()[0]
cat_vertex = g.addV("cat")\
.property("name", "Azuki")
.property("age", 3).toList()[0]
food_vertex = g.addV("food")\
.property("type", "cat-food")\
.property("company", "HOGEHOGE-FOOD").toList()[0]
# 辺の生成
g.addE("Loves").from_(person_vertex).to(cat_vertex).toList()
g.addE("Knows").from_(cat_vertex).to(person_vertex).toList()
g.addE("Loves").from_(cat_vertex).to(food_vertex).toList()
# グラフを探索
g.V().hasLabel("person")\
.has("name", "Toshiaki")\
.out("Loves").toList()
g.V().hasLabel("person")\
.has("name", "Toshiaki")\
.out("Loves")\
.out("Loves").toList()
# 頂点のidを自分で指定する(idは頂点を作成するときにのみ指定でき、作った後で変更することはできない)
g.addV("person")\
.property(T.id, 1)\
.property("name", "hogehoge").toList()
hogehoge_vertex = g.V().has(T.id, 1).toList()[0]
『アルゴリズム実技検定 公式テキスト』を読みました。よかった。
さっちゃん（twitter: @toshiakisan1127）です。
アルゴリズム実技検定（以下PAST本）を手を動かしながら読みました。とても面白く、買ってよかったです。
よかったと思う点
- 解説がわかりやすい
- 理解しやすい実装
- アルゴリズムの導入が丁寧
- 読んでいて面白い
解説はとても分かりやすいです。蟻本は初見ではわからないことが多いのですが、本書は少しずつ読み進めればほとんど理解できました。（簡単というわけではない。）
ダイクストラや巡回セールスマン問題などは分かっているつもりで本番ではコピペすることが多かったのですが、本書を読んで自分で手を動かして書いているとどこが本質的なのか分かるようになり、ソラで書けるようになりました。「理解したな」と思ったら本を閉じて最初から問題を解いてみると理解が深まっていいかと思います。
また進めていく中で、ある問題に対して今までで既出のアルゴリズムは何故使えなくて、じゃあどうすればいいかというストーリー性を持って学べるので飽きずに楽しめました。特に、幅優先探索からダイクストラに移る時の説明はいいなーと感心しました。
今までのアルゴリズムを組み合わせて上級の問題を解いてみる7章は、強い人の頭の中を覗き見たような面白さがありました。
よくないと思った点
- 初版なのでまだ誤字がある
- もっと多くのアルゴリズムを解説してほしい
誤字は仕方ないですね。しかしながら致命的なものではないので普通に読んでれば困ることはないと思います。物理の本を読んでいる時は３日考えてたら「それ誤字やで」って言われたりはよくありました。
また、本書でカバーしているアルゴリズムの範囲はそんなに広くないと思っています。AtCoder 茶色上位以上の方であれば知らないアルゴリズムはほとんどないかと思います。私（茶色上位）の場合は最小全域木は知りませんでしたが、他は知っていましたし問題でも使ったことがありました。ソラで書けるほど理解していませんでしたので読んだ価値はありましたが。
このとても良い解説で蟻本に載っているような他の典型アルゴリズムを見たいです。要するに続編【中級〜上級編】希望ということです。でもレベルが上がると読みたい人が減るので出ないでしょうね。800ページくらいあっても構わないよ私は。
誰が読むといいか
AtCoderのレートで言うと 100 から 1000 くらいまでな気がしています。
100以下の人はさすがに、まずはアカウント作ったり入力の仕方を身につけたりしたほうがいいんじゃないでしょうか。1000以上なら本書の内容は深く理解していると思うので買うなら 7 章目当てになると思います。値段もそこそこするので、本屋で立ち読みして決めたらいいんじゃないでしょうかね。一番向いていると思うのは茶色の人で、新しいアルゴリズムもありつつ知識も整理したり、「強い人ってこうやって思考するのかー」みたいなことを感じられるのでおすすめです。
お気持ち
緑いきたいよー。
セグメント木を勉強する時に見るサイト一覧
人類ならセグメントツリーを勉強する機会があると思います。しかし私は蟻本を見ても分からなかったので、以下のサイトを見て勉強しました。後の自分のためにまとめておきます。
C++でもPythonでも大丈夫です。
セグ木ってなに？という人
セグ木ってなに？という人はこのページが分かりやすいです。モノイドというものが出てきますが、単位元の概念などは重要なので頑張って読んでください。すごい丁寧です。
beet-aizu.hatenablog.com
実際にどうやって実装するの？
実装について一番分かりやすかったのは次のサイトです。完全二分木の親ノードと子ノードのインデックスの関係にさえ馴染めばそこまで難しくないと感じられそうです。これも丁寧。
tsutaj.hatenablog.com
AtCoder Beginner Contest 192 (A,B,C,D,E) 感想
SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest192)
ABC192の感想です。先に解きたい人は解いてから見てねー。（定型文）
A問題(Star)
これくらいなら40秒でちょいちょいですよ！！！
a = int(input()) print(100-a%100)
B問題(uNrEaDaBlE sTrInG)
タイトルは "unreadable string" です。
python のストリング型にはislowerというメソッドがあるのでそれを使えば簡単です！ここまで5分！
s = input() for i in range(len(s)): if i %2 ==0: if not s[i].islower(): print("No") exit() else: if s[i].islower(): print("No") exit() print("Yes")
C問題(Kaprekar Number)
カプレカ数というやつらしいです。愚直に実装すればよさそうですね。
関数を作ろうかなと思いましたが、速さを重視して適当に書いちゃいました。10分！
N, K = map(int, input().split()) ans = [N] for i in range(K): g1 = list(str(ans[-1])) g1.sort(reverse=True) g1 = "".join(g1) g1 = int(g1) g2 = list(str(ans[-1])) g2.sort() g2 = "".join(g2) g2 = int(g2) ans.append(g1-g2) print(ans[-1])
D問題(Base n)
これに１時間かかってしまいました。難易度は水色です。
愚直にやると無理そうなのは X = 11, K = 10**18 とか考えると分かります。なのですこし考えなければなりません。
Xをn進数だと思って10進数に直した結果というのはnに関して狭義単調増加なんですよね。（これはちゃんとコンテスト中にも示した。）なのでKを超える境目を二分探索で探せばいいです。めぐる式二分探索で検索検索ぅ！！
最後は一桁の場合がコーナーケースで、そこさえ乗り越えればクリアです。私は二分探索までは10分で気づきましたがコーナーケースで50分溶かしました。
def is_ok(d): # 条件を満たすかどうか？問題ごとに定義 res = 0 for i in range(len(X)): res += int(X[i])*pow(d,len(X)-i-1) if res <= M: return True elif res: return False def meguru_bisect(ng, ok): ''' 初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す まずis_okを定義すべし ng ok は とり得る最小の値-1 とり得る最大の値+1 最大最小が逆の場合はよしなにひっくり返す ''' while (abs(ok - ng) > 1): mid = (ok + ng) // 2 if is_ok(mid): ok = mid else: ng = mid return ok X = input() M = int(input()) if len(X) == 1: X = int(X) if X <= M: print(1) else: print(0) exit() d = list(X) d.sort() d = int(d[-1]) # print(res) ans = meguru_bisect(10**18+10,d) - d print(ans)
E問題(Train)
またもやE問題解けませんでした‥。（もはや定型文）
今回はD問題がE問題より難しいので実質E問題解けたというか溶けたというか...。
典型的なダイクストラの問題ですね。時間切れでコンテスト中には出来ませんでしたが、典型ダイクストラを貼っつけてコストの部分を本問に合うようにすれば終わりです。(INFを10**9とかにすると弱いので10**18にしておきます。また、コストが確定した点はcontinueで飛ばすようにしないとafter_contestで落ちます。)
from heapq import heappush, heappop import math INF = 10 ** 18 def dijkstra(s, n): # (始点, ノード数) dist = [INF] * n hq = [(0, s)] # (distance, node) dist[s] = 0 seen = [False] * n # ノードが確定済みかどうか while hq: v = heappop(hq)[1] # ノードを pop する if seen[v] == True: continue seen[v] = True for to, cost, k in g[v]: # ノード v に隣接しているノードに対して if seen[to] == False and math.ceil(dist[v]/k)*k + cost < dist[to]: dist[to] = math.ceil(dist[v]/k)*k + cost heappush(hq, (dist[to], to)) return dist v, e, X, Y = map(int, input().split()) g = [[] for _ in range(v)] for _ in range(e): a, b , t, k = map(int, input().split()) a -= 1 b -= 1 g[a].append([b,t,k]) g[b].append([a,t,k]) # print(g) ans = dijkstra(X-1,v) # print(ans) if ans[Y-1] != INF: print(ans[Y-1]) else: print(-1)
感想
ABCD4完(パフォーマンス1093)でレートが50あがりました！うれぴよ。
最近は東京への引っ越しの費用を貯めるために一ヶ月くらいABCに参加できていなかったり、基本情報技術者試験やTOEIC、JavaScript ネットワーク docker AWS など色々勉強していて精進もまったくしていないのでレートが上がって一安心しました。毎週問題は見てますが、手を動かさないと忘れてしまいますね。
ARCは上位層にレートを吸収されるので出ません！（しかし面白いから出ちゃう。悔しい。）
【報告】大学院を辞めて就職することにしました。
タイトル通り、大学院を辞めて就職することにしました。（本日11月27日は私の誕生日です。おめでとー。24歳になりました。）
経緯や思っていたことを書いておきます。
人生って不思議ですね。半年前はこんなことになるとは思ってませんでした。
自分について
さっちゃん（twitter: @toshiakisan1127）です。
Twitterでは、日々趣深いことを呟いています。
お腹すいた。
— さっちゃん (@toshiakisan1127) 2020年11月23日
偏差値45くらいの高校を卒業してフリーター（自宅浪人）を一年した後、大阪大学理学部物理学科に入学、卒業して現在は大阪大学大学院の理学研究科M1で素粒子論をやろうとしてました。（残念ながら入門レベルにも達した気がしないし、立ってないのでしょうが。）
猫が好きで、趣味はTwitterで猫を集めることと、猫カフェに行くこと、一人カラオケ、読書、競技プログラミング（AtCoder まだ茶色、緑はもうすぐ、水色は数年後？）です。
小中高とサッカーをしていたので、社会人になったら運動不足にならないように月1,2くらいでフットサルをやりたいと思ってます。
自宅浪人時代から2年弱カフェでアルバイトをして、今は塾講師4年目です。資格は運転免許（立派な国家資格！）くらいで、TOEIC受けたことないです。しかし就活で話すネタには困りませんでした。（就職活動でネタを探している方の参考には多分なりませんが、何を話したかは「就職について」で書きます。）
大学院を辞めることについて
一言で言うと社会に出たくなったからです。（明るい話ばかりではないのでどこまで言うか、書いている今も迷います。）
研究室が嫌になったわけではない。
決して、よくあるブラック研究室がどうこうとかではないです。むしろ私は研究室が大好きで、良い方ばかり（もちろん全員を知っているわけではないですが、少なくとも関わっている人は）ですし、就職について理由を述べたときも相談に乗っていただいたりしました。自分のために時間を割いていただいて恐縮でしたが「いつでもいいから何でも聞いてくれればいいし、困ったことがあれば言ってください。」と気さくに言っていただき感謝しています。
人生を再考した結果、就職を選んだだけ
自分の家は父親がおらず母が派遣で働いていたのですが、コロナウイルスの影響で職を失ってしまいました。ただ、去年介護士の資格を取っていた（50すぎてから学校に行って勉強する母すごい。）ので現在は介護士として働いています。そんな中でも、自分は大学と大学院は学費全額免除で通っていたし（正確には大学の入学金と一年生の授業料だけは自宅浪人時代のアルバイトの貯金で払いました）、アルバイトをしていて奨学金も借りているので生活が困窮するほどではなかったです。しかしながら、母の腰も悪くなってきてトイレを手伝うこともあったりしたので（現在は元気です。電子レンジの待ち時間は踊っています。僕も一緒に踊ってます。）、自分だけ、自分のために大学院にただ通っていていいのか、修士で出ることを決めていて何のために大学院に行くのかを見つめ直す日が増えてきました。（借金増やして若い時間を費やしてまでこれ以上行くべきか？とかね。）あとは単純に、働くならコード書くのも嫌いじゃないしwebアプリケーションとか1人で作れるようになりたいので、エンジニアが面白そうだなーと思っていて、それなら大学院行く必要ないよなーとかも思ってました。
結局就職することに決めましたが、別に物理が嫌いになったとか生活に困窮していち早く金が欲しいからとかではなく、「自分を見つめ直すきっかけができたから考えてみた結果就職してみることにした」という感じです。全然悲観的ではなくていくつかある選択肢の一つを取っただけですし、むしろ来年から始まる社会人生活にワクワクしています。（なので直接会った時に触れづらい話題とかではないよ！）
就職活動について
就職活動は案外楽しくやっていた
毎日「無い内定〜♪無い内定〜♪今日も元気に無い内定〜♪」って歌ってました。
就職先はもう決まっていて、東京にあるIT系の自社開発企業でエンジニアになります。（といっても何か作った経験はないので、最初は見習いです。ポテンシャル採用ありがたいです。配属は、機械学習エンジニアは楽しそうだなーと思いますが、PRMLすら読んでいるとイライラしてくる自分には無理かもしれません。いろんな世界を見て楽しそうなところに行きます。）
2022年卒業のつもりでインターンのために就職活動を始めたのが2020年4月で、21卒に切り替えて本選考に応募し始めたのが7月の始めごろだったように思います。そこから20社くらい応募して、8月の最後に一番好きな企業に内定をもらいました。10社くらい、中途採用しかやってないところに「入れろー」って応募してたりしました。決めるのは向こうなので最初から諦めなくてもいいだろって。迷惑な。
TOEICも受けたことないしWebテストの勉強も結局しませんでしたが、塾講師で中学数学はかなり詳しくなったので特に困りませんでした。面接で話すネタですが、自分は以下のようにたくさんあって（一つ一つは小さいですが）、履歴書に適当に散らしといて向こうが聞きたそうな話や話したいことを話してました。
- 偏差値45の高校から独学で、創立以来初めて大阪大学に合格した話
偏差値45から大阪大学に合格した話 - 平凡な物理学徒の日記
- 自宅浪人で鬱になったのでアルバイトを始めた話
- 大学に入って周りの優秀さと自分を比べて劣等感まみれになって、一年生の時の口癖が「大学やめたい」だった話
- 数物セミナーやKEKサマーチャレンジで、みんなで物理や数学と格闘した話
- 大学構内で七輪でサンマ焼いたり焼肉してる話
- 大学3年10月から始めた量子カオスの研究を根気よく続けていたら論文にできた話(修士1年の6月に雑誌の査読に通った！これが短い大学院生活で一番嬉しかった。)
- 卒業論文（宇宙論）の話
- 塾講師の話 (手のかかる子っている？と聞かれたので、他人の学ぶ機会を邪魔する子どもは大体話が通じないので大変ですと言ったら微妙な反応をされました。)
- 競技プログラミングの話（AtCoderのコンテストに毎週参加している話をすると好印象で、内定先にも競技プログラミング部があるみたいなので楽しみです！）
- ブログの話（月大体1000viewくらい。）
他にもあった気がしますが忘れました。常に「この話を通じて自分のどういうところを見せたいか」を考えて、うまく答えられなかった質問はメモして自分を深く知るきっかけにしたり、案外楽しくやってました。
なんというか、いわゆる「バイトリーダー！ボランティア！」とかいう感じのことではなく、ただ自分がやってきたことをお喋りしていたので、就活こうした方がいいよ！みたいな一般化できることは分かりません。一人称も「私」にするとぎこちなくなるので「僕」を使ってましたし、エントリーシートの添削も鵜呑みにせずに最終的に自分がいいと思ったものを送りつけていました。（大学生が大学生のエントリーシートを添削をするって自分にはよく分からないが、書いた文章を客観的に見てもらえるのはありがたいのでそういうサービスは使っていた。）
内定先は楽しそうなところだが、大人の話を信じてはいけない。
内定先については、オンラインで懇親会をやったり技術を共有する勉強会にも参加しましたが、意見が言いやすい良い感じのゆるさがあってすごい好きです。内定者懇親会でも髪色がピンクの人がいたりして「自由だなー」と思いました。と思ったら京大の人も何人かいたり、大学院出身の方もかなり多くてびっくりしました。働いてからも個人での勉強時間確保のために残業がすくないと言ってましたが、社会人の言うことは信用ならんので話半分で聞いてます。こちらとしては修行だと思っているのである程度の残業は一向にかまいませんが。給与は一年目・二年目としては満足しています。（初任給30何万とかではない。できれば月5000兆円ほしいです。）あと、大学院中退者が社内に割といて面白かったです。
お気持ち表明
『東京の家賃高すぎん？』
『猫可愛い。』
ひたすらに周りの人に恵まれたなーと思います。友達と教員の方々とバイト先の方々に相談に乗ってもらいましたが、理由もなく反対する人はいませんでした。母は寂しそうでしたが、兄がいるので数年は我慢してもらいます。
今は競技プログラミングで遊びつつ、引越しの初期費用のためにバイトしまくったり、会社に入ってついていけるように基本情報やSQL、Gitの本とか読みあさってます。なにかおすすめの本とか分野があれば教えていただきたいです。
健康第一に、適当にがんばりまーす。
大阪の方々、お茶会しましょう〜！
東京の方々、2月末ごろに家を探しにいきますので遊びましょう。浅草というところに行きたいです。
何年目くらいから猫と暮らせるんですかねー。
AtCoder Regular Contest 108 (A,B) 感想
ARC108の感想です。先に解きたい人は解いてから見てねー。（定型文）
[https://atcoder.jp/contests/arc108:title=atcoder.jp
A問題(Sum and Product)
よくある全探索の問題ですね。
NとM両方動かすと大変なので、一文字消去して1ループにするっていうのはあるあるです。制約が10^12なので、そのsqrtまで探せばok.
S, P = map(int, input().split()) for i in range(1,10**6+1): if i * (S-i) == P: print("Yes") exit() print("No")
B問題(Abbreviate Fox )
これは見て10秒くらいで、"fox"を見つけたら削除して、二文字前から探索しなおせばいいやーんと思いました。Twitterには難しく考えすぎて解けなかった人が割といたので、盲点のような問題なのかもしれません。逆に自分のように知識がない人は迷う必要がないので楽なのかもしれませんね。
N = int(input()) s = input() i = 0 while i<len(s): if s[i:i+3] == "fox": s = s[:i] + s[i+3:] i = max(i-3,-1) i += 1 print(len(s))
感想
今回はバイトがあって参戦しませんでした。B問題簡単に解けたので（茶色ですけど‥）、今回参加してたら初めてARCのB問題とけたかもしれませんが、そんなのはやってみないと分からないですね。
C問題は解説に「全域木」という単語が出てきているので勉強してから寝ます。
今週はABCのE問題を少し解いたので、明日のABCも頑張りたいと思います。ほいなら~。
