hiro_katoの競プロ精進記録

非情報系30歳が競技プログラミングを始めるとどうなるか?

AtCoder Beginner Contest 119 C - Synthetic Kadomatsu

はじめに

  • AtCoderで解けなかった問題(AtCoder Beginner ContestのC問題、D問題が中心になると思います)を復習しています.

  • 公式解説や上位者による解説ブログを読んで,自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです.


C - Synthetic Kadomatsu (300点)

概要

  • 竹が N本あり,その長さはそれぞれ l_{1},  l_{2}, ...,  l_{N}である
  • 目的:これらの竹を使って,長さ A B Cの3本の竹を作る
  • 3種類の魔法を任意の順に何度も使える
    • 延長:ある1本の竹の長さを1増やす.必要な MPは1
    • 短縮:ある1本の竹の長さが2以上である場合にその長さを1減らす.必要な MPは1
    • 合成:2本の竹を1本にする.その後も魔法を使える.必要な MPは10
  • 出力:目的を達成するために,必要な最小の MPを求める

読んだ解説のまとめ 1 2 3

  • 魔法は,合成を先にまとめて行って,必要に応じて延長や短縮を使用すればよい
    • それぞれの魔法をばらばらに実行するのと,上記の方法はほぼ等価なため
  • それぞれの竹は,竹 Aか竹 Bか竹 Cのいずれかで使用する場合と,全く使用しない場合の4通りがある
  • 制約条件から,最大でも 4^{8}=65,536通りしかない=全探索が可能
    • 以前見たりんご氏の解説によると,「使用する言語によって異なるものの,単純なループであれば1秒間で 10^{6} 10^{8}回計算できる」ため(要出典)
  • 深さ優先探索(dfs)で,竹の組み合わせと合成に必要な MPを計算
    • 組み合わせの全列挙が,この問題のキーポイント
  •  A B Cを作るのに,不足もしくは過剰な長さを延長もしくは短縮で調整する
  • 必要なMPの最小値を出力

実装のポイント

  • 再帰による組み合わせの全列挙
    • 基本ケース:再帰の深さが Nと等しいとき
    • 再帰ケース:竹 A B Cの構成要素かどうか,もしくは使用しないかの4通りについてdfsを並べる
    • 言語によっては,標準ライブラリを使用するという手もある
  • 再帰関数の引数・戻り値の例
    • 引数:再帰の呼び出し回数(再帰の深さ)
    • 引数:再帰関数を呼び出した時点での竹 A B Cの長さの合計値
    • 戻り値:必要な MPの合計値
  • 再帰ケースを呼び出すことにより,次の状態がどのように変化するかを一般化
    • 再帰の深さが1増える
    • ある竹 iが使用されない場合:竹 A B Cの長さの合計値はそのまま
    • ある竹iが使用される場合:竹 A B Cのいずれかの長さの合計値に加算する.最初の1本目以外は,必要な MPの合計値に10加算する
  • 合成後の長さの不足もしくは余りを調整する部分は,必要な竹 A B Cの長さとそれぞれの合成直後の長さとの差の絶対値を取る
  • 使う竹が1本も存在しない場合は,必要な MPを極端に大きな値として扱う(最小値とならないように例外的な処理をする)

筆者の到達度

  • それぞれの竹を選ぶかどうかを1(選ぶ)か0(選ばない)で管理する
  • 制約条件から最大でも 2^{8}通りしかない=dfsで全探索できそう
  • 各組み合わせとも合成を先にしてしまえばいい
  •  A B Cそれぞれについて,長さが足りないor余っている部分は後で調整すればよさそうだ
  • それぞれの竹を使って,長さがちょうど A B Cとなるように構成するするには, DPが必要?
    • ここで,自分の中での制限時間(1時間)が経過したため,解説を読むことに

想定解法と筆者の到達度とのギャップ

  • 必要な竹がどのように構成されるかという視点 vs それぞれ竹をどう使うかという視点
  • 再帰を使って,竹の組み合わせと長さ A B Cの竹を作るために必要なMPを,どのように管理すべきか思いつかず

ソースコードの一例

提出コード

得られた知見

  • ABCのC問題までは全探索で間に合う可能性が高い.数学的な解法やDPなどは,計算量の見積もりをしてからでも十分かも
  • 条件を整理して,操作の順番に依存しない部分/依存する部分をまとめる
  • 再帰ケースに直接,分岐条件を持たせるとシンプルに実装できる
  • 再帰の引数に,再帰の深さと求めたい状態を持たせる

感想

  • 再帰による全探索の基礎を学べて良かったです
  • 公式解説・解説ブログのコードを見て,その簡潔さと美しさに感動しました

つまづきポイント(○印が該当を表す)

問題 解けず 理解 発想 方針 実装
C

各項目の意味

  • 解けず:自力で解けたどうか
  • 理解:解法を理解するのに時間を要した問題
  • 発想:発想が難しい(思いつけば簡単)な問題
  • 方針:方針を見出すのが難しい問題
  • 実装:実装に手間取った問題

要復習・追加調査

  • 再帰のお気持ちを察することができるように,類題を解きまくる

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

【競技プログラミング】問題を解くときの切り口

はじめに

  • 競技プログラミングにおいて脱・初心者を目指して,問題を解いて得られた知見や先人の知恵・発想を少しずつまとめていきたいと思います.
  • (筆者としては)抽象的な表現で一般化を図っているつもりです.

    分かりづらい点・勘違い・誤解などがありましたらご指摘いただけると幸いです
    連絡先:@k_hiro1818

分類

全般

計算量の削減

  • 思いついた解法がTLEしてしまう
    • 愚直解(全探索)で,同じ(ような)計算を複数回していないか?
    • 回答に直接つながる部分を計算する前に,共通部分を事前に処理できないか?
  • 考慮すべき条件が複数あるように思える
    • 点や軸などの条件を1つに固定して,その他の条件を変えることはできるか?
    • 着目する範囲を限定できないか?(計算・考察しなくても済む部分はないか?)
    • 条件を整理して,操作の順番に依存しない部分/依存する部分をまとめられないか?

コーナーケースの特定

  • 制約条件に含まれる境界値から,回答の条件を満たさないケースを列挙

整数

最大公約数

  • 各項が kの倍数のとき、その合計も kの倍数
  • 数列において,整数同士の差を取り合うような状況にある

グリッド

  • 片方の軸にだけ注目するとどうなるか?
  • それぞれの軸は,独立として扱えないか?

実装における注意事項

  • 無限ループが発生していないか?

今後の予定

  • 知見の蓄積
  • 類型化した結果を図で表現

参考

https://github.com/hamko/procon/blob/master/typical.png

記事などを執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが、@k_hiro1818までご一報ください。

NIKKEI Programming Contest 2019 復習

はじめに

  • AtCoderで解けなかった問題(AtCoder Beginner ContestのC問題、D問題が中心になると思います)を復習しています.

  • AtCoderのレートでは,茶色上位~緑最下位を行ったり来たりしています.

  • コンテスト本番で解けなかった問題を,どのように考察・実装すればよかったのか?

  • 上位者による解説ブログを読んで,自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います.

  • 間違いや勘違いなどがございましたら、ご指摘・ご指導いただけると幸いです.


C - Different Strokes (400点)

コンテスト本番における筆者の到達度

  •  A_{i} -  B_{i}を取る  +αで一般化を図ればいいと思い込んだまま,無限に時間を溶かしました.
  •  A_{i} +  B_{i}の発想に至らず.

解説ブログの証明を読んだ感想

  • 公式解説 1を見てある程度納得したものの,自分がコンテスト本番で気がつけるかというのは全くの別問題だと感じました.

証明例1 2 3

  • 数式を読んで納得しました.
  •  Xの右辺において,異符号で打ち消しあう部分(第3項と第4項)をどのように思いつくのがポイントだったのではないか,と思っています.

    • 第3項:高橋君が料理 iを選択することで,青木さんが料理 iを取れなくなる→高橋君の幸福度の加算分
    • 第4項:青木さんが料理 iを選択することで,高橋君が料理 iを取れなくなる→高橋君の幸福度の減算分
    • と解釈しました.

感想

  • 考察の妥当性を明示できるため,数式を積極的に使っていこうと思います
  • コンテスト本番で,自分にとってはどのように思いつくのが(発想の飛躍が必要な場合もあり)難しいケースもあるかもしれません

証明例2 4

  • もっともシンプルな条件(この場合は,2つの要素の比較)から一般化を図る

感想

  • 考察のとっかかりとしてイメージしやすかったです
  • 一般化を図るときに,自分の数学力では嘘解法かどうかのチェックが難しいケースもあるかもしれません

実装のポイント

  •  A_{i} B_{i} A_{i} +  B_{i}の大きい順にソート
  • 方法1:tupleで  A_{i} B_{i},  A_{i} +  B_{i}を管理
  • 方法2:sorted()関数のkeyにlambda式で条件 A_{i} +  B_{i}を指定

ソースコードの一例

  • 解説ACに賛否両論あるかと思いますが,自分で実装できたほうが理解が深まると考えています
  • Python3で実装してみました
  • tuple版
  • sorted()関数版

得られた知見

  • 数式で定式化してみることはできてないか?
  • もっともシンプルな条件から一般化を図れないか?

感想

  • 標準ライブラリの便利さ・コードを簡潔に記述できるという点から,これまで以上に使っていこうと思います.
  • lambda式の理解が浅かったことを痛感しました(今も十分とは言っていないです)
  • コンテスト上位者は,思考に寄り道がない・少なく,実装もシンプル.だからこそ,短時間でACできるのだということを再確認しました.
  • 記事を執筆されている方々には,感謝してもしきれないです.

つまづきポイント(○印が該当を表す)

問題 解けず 理解 発想 方針 実装
D

各項目の意味

  • 解けず:自力で解けたどうか
  • 理解:解法を理解するのに時間を要した問題
  • 発想:発想が難しい(思いつけば簡単)な問題
  • 方針:方針を見出すのが難しい問題
  • 実装:実装に手間取った問題

参考

 5: http://cocodrips.hateblo.jp/entry/2017/04/11/032000

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが、@k_hiro1818までご一報ください。

【Docker】Ruby on Rails の環境構築(Win10・2019/01版)

競技プログラミングの精進記録と銘打って,なぜ環境構築なの?

  • AtCoderで精進するときに役立つWebアプリを作ってみたいと思ったからです.

今回の内容

  • Linux系の環境が手持ちでなかったため,
    docker-compose1,2を使ってRuby on Railsの環境を構築しました(Mac買えば(ry).
  • 公式ドキュメント3と先人の解説ブログ4を参考にしています.
    公式ドキュメントから変更した設定を中心に記事を書きました.
  • RubyRuby on Railsだけでなく,Dockerも初学者です.
    お気づきの点がありましたら,コメントなどでご指摘いただけると幸いです.

2019/01/17 追記

開発環境

ローカル環境

  • Windows10 Pro Version 1803
  • Docker for Windows Version 18.09.1

作成した環境

主な変更点

手順

docker-compose run web rails new . --force --database=mysql --skip-bundle
  • docker-compose buildを実行
docker-compose build
  • データベースに接続
    • config/database.ymlを一部書き換え
docker-compose up
docker-compose run web rails db:create

設定ファイル

Dockerfile

FROM ruby:2.6.0
RUN apt-get update -qq && apt-get install -y build-essential mysql-client node.js
RUN mkdir /myapp
WORKDIR /myapp
COPY Gemfile /myapp/Gemfile
COPY Gemfile.lock /myapp/Gemfile.lock
RUN bundle install
COPY . /myapp

Gemfile

source 'https://rubygems.org'
gem 'rails', '5.2.2'

Gemfile.lock




docker-compose.yml

version: '3'
services:
  db:
    image: mysql:8.0.13
    volumes:
      - ./tmp/db:/var/lib/mysql
      - ./mysql-confd:/etc/mysql/conf.d
  web:
    build: .
    command: bundle exec rails s -p 3000 -b '0.0.0.0'
    volumes:
      - .:/myapp
    ports:
      - "3000:3000"
    depends_on:
      - db

mysql-confd/default_authentication.cnf

[mysqld]
default_authentication_plugin= mysql_native_password

config/database.yml

default: &default
  adapter: mysql2
  encoding: utf8
  pool: <%= ENV.fetch("RAILS_MAX_THREADS") { 5 } %>
  username: root
  password: 
  host: db

development:
  <<: *default
  database: myapp_development

test:
  <<: *default
  database: myapp_test

公式リファレンスからの変更点やハマった点に関する備忘録

Dockerfile

項目 変更前 変更後
Rubyのバージョン 2.5 2.6.0
apt-getでインストールするパッケージ libpq-dev mysql-client

Gemfile

項目 変更前 変更後
Ruby on Railsのバージョン 5.2.0 5.2.2

docker-compose.yml

項目 変更前 変更後
データベースのイメージ postgres mysql
volumes .tmp/db:var/lib/postgresql/data ./tmp/db:/var/lib/mysql
volumes - ./mysql-confd:/etc/mysql/conf.d

補足

  • データベースを永続化するため,明示的にマウントするボリュームを指定
  • MySQL 8.0.xを使用するときに,後述するmysql認証に関するエラーが発生
    認証設定の変更とマウントするボリュームを指定5

rails newを実行

項目 変更前 変更後
--databaseオプション postgres mysql
--skip-bundle -- 追加

ハマった点

  • 現象:以下のエラーが発生
Get https://registry-1.docker.io/v2/: net/http: request canceled while waiting for connection
  • 対策:Dockerをrestart6

docker-compose buildを実行

ハマった点

  • 現象:以下のエラーが発生
Authentication plugin 'caching_sha2_password' cannot be loaded: /usr/lib/x86_64-linux-gnu/mariadb18/plugin/caching_sha2_password.so: cannot open shared object file: No such file or directory
  • 対策:docker-compose.ymlの補足の項目を参照されたし

データベース接続

項目 変更前 変更後
adapter postgresql mysql2
encoding unicode utf8

予定(順不同)

  • 今回の設定ファイルをGitHubにアップロード
  • Railsチュートリアルを実践
  • AtCoderに関するWebアプリを作成
  • Dockerの学習
  • RubyRailsなどがバージョンアップした場合への対応方法を調べる

更新履歴

  • 2018/12/17 作成
  • 2019/01/17 更新


  1. Docker Composeとは,Dockerにおいて複数のコンテナ(ホストOS上に作られる論理的な区画)をまとめて管理するためのツール.筆者のざっくりした認識では,設定ファイルを用意すればWebアプリケーションの本番環境が比較的容易に構築・再現できるものと思っています.

  2. 阿佐志保著,山田祥寛監修:プログラマのためのDocker教科書 インフラの基礎知識&コードによる環境構築の自動化,294p.,翔泳社,2015.11. 注:第2版が出版されており,大幅に加筆されている模様

  3. https://docs.docker.com/compose/rails/

  4. http://roronya.hatenablog.com/entry/2018/04/30/200909

  5. https://dev.mysql.com/doc/refman/8.0/en/caching-sha2-pluggable-authentication.html https://qiita.com/yensaki/items/9e453b7320ca2d0461c7

  6. https://github.com/docker/for-win/issues/611

はじめまして!

あなたは誰?

人生初の記事を投稿しました。

hiro_katoです。
よろしくお願いします。

さまざまな縁があって、30歳になった今年から競技プログラミング(略称して競プロと呼ばれることが多い)を始めました。

プログラミング歴は競技プログラミングに参加した時期とほぼ同じです。

日本語で出題される国内最大級のコンテスト(アルゴリズム部門)であるAtCoder Beginner Contestに20回以上参加し、本番中にC問題が解ける回も出てきたというレベルです。

過去問やコンテスト中に問題を解けたときの喜びが大きなモチベーションとなっています。

なぜ記事を投稿しようと思った?

自分にとって難しい問題(AtCoder Beginner ContestのC問題、D問題など)に出会ったときは、 こちらの情報を参考にしています。

  • 公式の解説放送 1や解説pdf 例えば 2
  • コンテスト上位陣の解説ブログ 例えば 3 , 4
  • コンテスト参加者の提出コード

敢えて記事を書き始めたのは、以下の理由があります

  • 複数の解説を参照できたことで、いくつもの疑問が解消された

    • ギブ・アンド・テイクのテイクの部分で少しでも貢献できるようになりたい
  • 思考のジャンプの幅が狭い筆者だからこそ気がつけることがあるかもしれない
    AtCoderに参加されている皆様は天才型が多い印象なので、需要は少ないかも…)

    • AtCoderのレート(茶色)から見た考察や実装のつまづきポイントが、もしかしたら誰かにとって役に立つかもしれないという淡い期待を込めて
  • 定期的にアウトプットをしていくことで、知識の定着や分かりやすい文章の作成能力の向上などを図りたい

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが、@k_hiro1818までご一報ください。