2019-10-27

paizaでフリーザの戦闘力を体験しよう！～エンジニア戦闘力を53万まで上げる方法～

paiza

はじめに

最近、paizaのスキルチェックに『エンジニア戦闘力』というものが表示されるようになりました。（まだベータテスト中らしいです）

f:id:kato_robotics:20191022121003p:plain — paizaのエンジニア戦闘力

このエンジニア戦闘力については、公式のpaiza開発日誌ブログに詳しい解説があります。

paiza.hatenablog.com

『戦闘力』と聞いてまず気になることと言えば、「どうすれば戦闘力を53万まで上げることができるのか」ということだと思います。もちろん、戦闘力53万とは漫画『ドラゴンボール』に登場する『フリーザ』の第一形態における戦闘力のことですね。あの憧れのフリーザと同じ戦闘力になりたい、という夢は誰しもが持っていると思います。

しかし、これまでフリーザの戦闘力を体験しようと思ってもその手段がありませんでした。なぜなら「戦闘力を計測する」という機能を持った装置（スカウターなど）やシステムがこの世界に存在しなかったからです（もしかしたら私が知らないだけで存在しているかもしれません）。そのためフリーザになりたいという夢が叶うことはありませんでした。

そんなとき、paizaに『エンジニア戦闘力』というドラゴンボールでいうところの『スカウター』が登場しました。おそらくpaiza開発者の方々の中にも私と同じくフリーザになりたいという夢を持った方がいたのでしょう。

ついに、フリーザの戦闘力を手にする時が来ました。

この記事ではpaizaを利用して戦闘力を53万まで上げる方法をまとめます。

みんなでフリーザの戦闘力を体験しましょう！

はじめに
目次
エンジニア戦闘力とは何か
エンジニア戦闘力の仕組み
問題の難易度について
効率の良い戦闘力の上げ方
おすすめの問題ランクと難易度
初めてpaizaを利用する方におすすめの問題
スキルチェックの問題が難しいと感じたら
現在の私の戦闘力
おわりに

エンジニア戦闘力とは何か

paizaのスキルチェックの問題は「S, A, B, C, D」という5つのランクに分かれています。しかし、さすがに5段階のランクだけではスキルの評価を行うためには不十分かもしれないという話になり、そこで誕生したのが『エンジニア戦闘力』らしいです。

エンジニア戦闘力とはその人のスキルを数値によって表したものです。（だいたい1～百万くらいまで）

このエンジニア戦闘力が高い方がpaizaの世界においては強いということになります。

詳しいことはpaiza開発日誌を読んでみてください（再掲）。分かりやすく説明されています。

paiza.hatenablog.com

エンジニア戦闘力の仕組み

paizaのエンジニア戦闘力はスキルチェックの問題を解くことによって上げることができます。逆に問題を解くのに失敗すると戦闘力は下がることになります。

この画像は私のエンジニア戦闘力のグラフです。グラフが上がったり、下がったりしているのは、私が問題を解くのに成功したり、失敗したりしているからです。

問題を解いてエンジニア戦闘力を上げるには以下の条件を満たす必要があります。逆にこの条件を満たさないと「失敗」という扱いになって戦闘力が下がります。

各問題に設定されている「想定回答時間」以内に回答を提出する
提出した回答がすべてのテストケースをクリアする（スコア100点を取る）

そしてこのエンジニア戦闘力は「より難しい問題を解くと、より大きく上がる」という仕組みになっています。詳しくは以下に続きます。

問題の難易度について

スキルチェックの問題にはそれぞれ「難易度」というものが存在します。これは問題に設けられたレーティングであり、難易度が高いほど難しいということを表しています。

下の画像は問題のランクと難易度のイメージ図です（私が適当に描いたものなので正確ではありません）。

f:id:kato_robotics:20191026002811p:plain — 問題のランクと難易度のイメージ図

この図から分かる通りランクが高い問題ほど、難易度が高くなっていきます。しかし、Sランクよりも難易度が高いBランクの問題も存在したりします。

ちなみに、問題の難易度は私が調べたところ、だいたい以下のようになっていました。

	難易度
Dランク	700 ～ 1400
Cランク	1300 ～ 2000
Bランク	1500 ～ 2300
Aランク	1800 ～ 2400
Sランク	2200 ～ 2500

効率の良い戦闘力の上げ方

ではさっそくどうすればエンジニア戦闘力を53万まで上げて、フリーザの力を体験できるのかという話をしていきます。

まずpaiza開発日誌のエンジニア戦闘力についての解説を読むと、 より難易度の高い問題を解くと、エンジニア戦闘力も大きく上がると書いてあります。

つまり難しい問題を解けば解くほどエンジニア戦闘力が上がっていくということになります。しかし、当たり前のことですが問題が難しければ難しいほど失敗する可能性が高くなっていきます。また難しい問題ほど解くまでに時間がかかってしまいます。

そう考えると自分にとって難しいと感じる問題を解くことは、エンジニア戦闘力を上げるためには必ずしも必要ではないと思われます。そこで私が考える最も効率の良いエンジニア戦闘力の上げ方は以下のものです。

自分が確実に解ける問題の中で最も難易度が高い問題を解いていく

勉強の目的でスキルチェックの問題を解くなら難しそうな問題にもチャレンジしていくべきだとは思いますが、エンジニア戦闘力を53万まで上げることを目的としてスキルチェックの問題を解くならば確実に解ける問題を解いてくことが最も効率が良い方法だと思います。

なぜならエンジニア戦闘力を上げるためには、スキルチェックの問題を解き、かつ、失敗しないように解く必要があるからです。この「失敗しないように解く」ということが重要で、一問失敗するだけでガクッと戦闘力が落ちることもあります（失敗した問題の難易度によって落ち方は変わります）。そのため確実に解ける問題を解いていくことが大切だと思います。

初めてpaizaを利用する方におすすめの問題

この記事を読む方の中には、「フリーザの戦闘力を体験したいからpaizaを始めたけど、どの問題を解けばいいのか分からない」という方もいらっしゃると思います。そこで私が今までに解いた問題からいくつかおすすめの問題を選んでみます。どの問題を解けばいいか迷っている方がいらっしゃいましたら参考にしてみてください。特におすすめの問題は赤くしておきます。（かっこの中の数字は各問題の難易度です。）

Dランク問題

D007 : N倍の文字列 (1244)
D014 : 小文字を大文字に (865)
D029 : サイコロの裏面 (857)

Cランク問題

C-16 : Leet文字列 (1324)
C034 : 先生の宿題 (1623)
C061 : 繰り上がりのない足し算 (1699)

Bランク問題

B031 : コインのウラとオモテ (1953)
B041 : 繰り返し模様 (2076)
B063 : 支払う枚数とお釣りの枚数 (2162)
B068 : 駒の到達範囲 (2023)

Aランク問題

A003 : 盤面ゲーム (1821)
A004 : あみだくじ (1869)

Sランク問題

S007 : データヒストグラム (1830)
S015 : ABC文字列 (2303)

スキルチェックの問題が難しいと感じたら

スキルチェックの問題が難しくて解けない、という人もいるかと思います。そんなときは競技プログラミングの勉強をしてみるというのも一つの手だと思います。「競技プログラミング」「プログラミングコンテスト」などをキーワードに検索してみるといろんな情報が出てきます。

ちなみに、私がおすすめするのはAtCoderです。

atcoder.jp

AtCoderでは毎週プログラミングコンテストを開催しています。また過去問も豊富で全ての問題に解説も備わっているため、問題が解けなくても解説を読んで勉強することができます。

そう言われてもAtCoderで何をすればいいか分からない、という人には以下の記事がおすすめです。とても分かりやすく何をすればいいかがまとまっています。

qiita.com

書籍をお探しの方には以下がおすすめです。プログラミングコンテストで必要とされるアルゴリズムを勉強することができます。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者: 渡部有隆
出版社/メーカー: マイナビ出版
発売日: 2015/01/30
メディア: Kindle版
この商品を含むブログを見る

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (36件) を見る

現在の私の戦闘力

「わたしの戦闘力は530670です」

f:id:kato_robotics:20191027142804p:plain — わたしの戦闘力は530670です

私もようやくフリーザの第一形態と同程度の戦闘力を手にすることができました。思った以上に時間がかかってしまいましたが（なんやかんや50時間くらいかかった）、フリーザと戦闘力で並ぶことができたという満足感と感動で胸が満たされています。

ちなみに、エンジニア戦闘力は百万を超えることも可能らしいので、フリーザの第二形態における戦闘力も体験できる仕様になっているということです。よく考えられていますね。

おわりに

今回はpaizaを利用してフリーザの戦闘力を体験する方法についてまとめました。エンジニア戦闘力53万になって体から力がみなぎっています。このネタ記事を書くために50時間くらい費やしましたが、特に後悔もなく、清々しい気持ちになっています。合計で百問以上問題を解いたので、 paizaにはかなり満足しました。 paizaには面白い問題も多く、就活もできるということでとても良いサービスだと思います。みなさんもぜひ、paizaを活用して、就活したり、転職したり、フリーザになったりしてみてください！

2019-10-20

AtCoder Beginner Contest 143 D - 今日から始める競プロ日記

AtCoder

はじめに
D - Triangles
コンテスト中に解いた方針
コンテスト中に書いたコード（ちょっといじった）
想定解の方針
解説動画を参考に書いたコード
おわりに
今日から始める競プロ日記まとめ

はじめに

AtCoder Beginner Contest 143（ABC143）に参加。

今回はDまで解いて4完。

D問題の想定解ではO(N^2 logN)で解けるらしいのだけど、 O(N^3)で解けてしまったので、解説動画を見ながら想定解の方も自分なりにまとめてみる。

atcoder.jp

D - Triangles

棒がN本
i番目の棒の長さはLi
ここから三本選んで三角形を作る
何種類の三角形が作れるか

制約

3 <= N <= 2*10^3
1 <= Li <= 10^3

コンテスト中に解いた方針

蟻本の三角形の問題で（p. 21）、三角形の条件は「最も長い棒の長さ > 他の2本の棒の長さの和」とあった。

なので棒の長さでソートして、一番長い棒、二番目に長い棒、それ以外の棒と分かった状態で判定していけば計算がちょっと少なく済みそうだなと思った。

あと、三本目を選ぶときに長い棒から選んでいるのである棒で三角形が作れないことが分かったら、それより短い棒でも三角形が作れないからそこで止めても良さそうだなと思った（枝刈りみたいな感じ）。

コンテスト中に書いたコード（ちょっといじった）

897ms

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

int main()
{
    // 入力
    int N;
    cin >> N;
    vector<int> L(N);
    for(int i = 0; i < N; i++) cin >> L[i];
    // 棒の高さをソート
    sort(L.begin(), L.end());
    // 組み合わせの個数をカウント
    long long cnt = 0;
    // L[i] : 候補の中で一番長い棒
    for(int i = N-1; i >= 2; i--)
    {
        // L[j] : 候補の中で二番に長い棒
        for(int j = i-1; j >= 1; j--)
        {
            // L[k] : それ以外の棒
            for(int k = j-1; k >= 0; k--)
            {
                // 条件を満たすか判定
                if(L[i] < L[j]+L[k]) cnt++;
                else break; // ダメだったらそれより短いものもダメだからbreak
            }
        }
    }
    // 解を出力
    cout << cnt << endl;
    return 0;
}

想定解の方針

公式の解説動画を見ながらまとめてみる。

www.youtube.com

まず三角形の条件をまとめる

三本の棒の長さを a < b < c とする
このとき、a + b > c となるように選択

この条件を満たすように効率よく棒を探索すればよい。

棒を長さでソート
aとbをfor文で回す（ただし、a < b）
そのときに a + b > c を満たす棒の範囲の端を二分探索で見つける

解説動画を参考に書いたコード

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

int main()
{
    // 入力
    int N;
    cin >> N;
    vector<int> L(N);
    for(int i = 0; i < N; i++) cin >> L[i];

    // ソート
    sort(L.begin(), L.end());

    // 組み合わせをカウント
    int cnt = 0;

    // aとbの棒をfor文二重で回す
    // 条件 : a < b < c and a + b > c
    for(int b = 0; b < N; b++)
    {
        for(int a = 0; a < b; a++)
        {
            // 二つの棒の長さの和
            int ab = L[a] + L[b];
            // 二分探索で条件を満たす三本目のグループの右端+1を見つける
            // （イテレータとイテレータの差をとって何番目か求めている）
            int r = lower_bound(L.begin(), L.end(), ab) - L.begin();
            // 左端
            int l = b+1;
            // カウント
            cnt += max(0, r-l);
        }
    }
    // 解を出力
    cout << cnt << endl;
    return 0;
}

おわりに

今回はたまたまコンテスト中に解けたからよかったけど、本来なら解けなかったかもしれない問題なのでしっかり覚えておきたい。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com

2019-10-19

AIZU ONLINE JUDGE ALDS1_1_D - 今日から始める競プロ日記

aoj

はじめに

螺旋本に載っている問題を解いていこうと思う。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
出版社/メーカー: マイナビ
発売日: 2015/01/30
メディア: 単行本（ソフトカバー）
この商品を含むブログ (7件) を見る

今日は2.5導入問題（p. 46）の「ALDS1_1_D : 最大の利益」

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D

最大の利益

ある通貨の時刻tにおける価格Rtが与えられる
Rj - Ri（j > i）の最大値を求めよ

制約

2 <= N <= 2*10^5
1 <= Rt <= 10^9

解いた方針

単純に解こうとするとO(N^2)でTLE。

ちゃんと考えればO(N)で解けそう。

時系列の状態を維持する必要があるからソートはできないけど、最安値は保持してもよさそうだということに気づく。

つまり、先頭から価格を順番に見ていった場合、すでに見た価格は時系列とか関係なくなる。

だからすでに見た価格の中から最安値を見つけて保持。

あとは次にくる価格と差をとって最大値を更新していくだけ。

提出したコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    // 入力
    long long N; cin >> N;
    vector<long long> v(N);
    for(int i = 0; i < N; i++) cin >> v[i];
    // 計算
    long long ans = -(1<<30);
    long long minv = v[0];
    for(int i = 1; i < N; i++)
    {
        // 差を計算
        long long tmp = v[i] - minv;
        // 最大値を更新
        ans = max(ans, tmp);
        // 最安値を更新
        minv = min(minv, v[i]);
    }
    // 解を出力
    cout << ans << endl;
    return 0;
}

おわりに

良い問題。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com

2019-10-16

ハル研究所プログラミングコンテスト2019の参加記録

プロコン

はじめに

ハル研究所が主催するプログラミングコンテスト2019（10/01～10/15）に参加しました。

www.hallab.co.jp

マラソン形式のコンテストへの参加はほぼ初めてでしたが、最初から最後まで楽しむことができました。

コンテストに取り組んでいた約二週間、やったことや考えていることなどを定期的にメモしていたので、この記事ではそのメモをまとめて参加記録を書きたいと思います。

問題

縦30マス × 横60マスのステージがある
ステージにはカメが何匹かとニンジンが何本かある
毎ターンそれぞれのカメは上下左右に1マス移動できる
カメがニンジンのあるマスに到達するとそのニンジンを食べる
すべてのニンジンを食べるとそのステージをクリア
クリアするまでにかかったターン数がスコアとなる
また、ニンジンには高さがある
例えば高さが3のニンジンは、カメが三匹重なる必要がある

ビューアの様子

公式のビューアは眺めているだけで楽しいです。緑色がカメ、オレンジ色がニンジンです。

f:id:kato_robotics:20191016002603p:plain — ビューアの様子

結果

総ターン数：76,196
順位：66位

＊ちなみに、チャレンジスコア（77,777）を超えた参加者は全体の48%らしいので、私はちょうど真ん中らへんということになりそうです。

一日目

コンテスト開始してすぐに問題パッケージをダウンロード。コンパイル、実行、Viewerの動作を確認。その後、サンプルコードのまま提出。

総ターン数：232,221
時間：4.2sec

ビューアを眺めてみると、明らかに無駄が多い。とりあえずの改善点を探す。

カメたちの動きがかぶっている
あっちこっち行き過ぎている

効率よくエサを回る経路を見つけたら良さそう。貪欲法とか焼きなまし法とか、いろいろあって良く分からないから全部試すくらいの気持ちでやっていく。

二日目

まずは単純に貪欲法を実装。カメを一か所に集めてから、カメ全員が近いエサを順番に取っていくようにした。

総ターン数：100,328
時間：2.9sec。

ターン数が半分くらいにはなった。ここからどれだけ減らしていけるかどうか。

マラソン形式のプロコンの定石とかあるのかなと思って、取り組み方をちょっと調べてみたらたくさんでてきたので読む。

読んでみて分かったこと

色々アルゴリズムはあるけど最も重要なのは考察
とりあえず貪欲法は強い
なんでもメモを取っておくといい
ランキングから得られる情報も大事だけど見過ぎるのも良くない
根気も大事

三日目

もっと効率良くエサを回ることができる経路を見つけたい。ということで焼きなまし法を使ってみたい。正直焼きなまし法がどんなものだったか覚えていないので、色々資料をあさりながら思い出してみる。

昔、講義で巡回セールスマン問題を焼きなまし法で解く方法を教わったのだけど、ほとんど覚えていなかった。

以下の記事を参考。

焼きなまし法のコツ Ver. 1.2（→1.3へ改装中） - じじいのプログラミング

四日目

昔書いたプログラムを参考に焼きなまし法を実装して、エサを回る最適な経路を求めようとしたけど、自分の環境で17万ターンくらいかかってしまってだめっぽい。さすがにこれは無理があった。というか最適な経路ってなんだ。

ふと思いついたけど、貪欲法で近いエサを順々に辿っていく経路を生成してから焼きなますといいかも。あと、スタート地点はすべてのカメの中心が良さげ。

もしくは最初に書いた単純な貪欲法で、エサの高さを考慮したアルゴリズムを考える。

コードを提出したらwarning-errorで落ちた。原因が分からない。 randが原因かな？ random_deviceはエラーになるらしいけどrandは使える？

次に何をやればいいか、電車の中でいろいろ考えていた。

やっぱり貪欲法で近似解ぽいものを作ってから、焼きなまし法でさらに経路を改善したらスコアが伸びる気がする。そんなに大きくは変わらないだろうけど。

あとステージを細かく分けて、その分割した範囲内で効率良くカメを動かしてみる方法はどうか。

五日目

結局のところ乱数生成は何を使えばいいのだろう。 randでいいのかなと思ったけど、調べてみるとなんか遅いらしい。あと、質もそこまで良くはないらしい。 XorShiftが早いらしいけどなぜかrandと変わらない。焼きなまし法の実装もあまり良くないのでとりあえず貪欲法でいけるとこまでいきたい。

再び自分の環境では通るのだけど提出するとなぜかエラーになる。

#include "parameter.hpp"

を消したら通った。なんかダメだったらしい。

六日目

ステージを四つに分割して一つの区画ごとをすべてのカメで探索。カメは一番近いエサを食べていく。

総ターン数：97,221
時間：3.5sec

思ったよりもスコアは伸びなかった。分割数とエサを回る経路を考えればもっと良くなりそう。

ステージを九分割して真ん中の区画から探索開始。そこからぐるっと渦を描くように区画を移動しながら探索していく。

それぞれのカメは近くのエサから食べていく。えさの高さ分だけカメは集まる。

総ターン数：88,938
時間：2.5sec

次に考えること

エサの総数によって探索方法を変える
探索順路をいろいろ試して一番いいのを選ぶ
ごりごりにシミュレートする

一万とか一気にスコアが上がるとは思えない。どうしようか。

ちょっとした改善でも数千くらいならスコアを減らせることに気が付いた。

何もしないターンを生み出してしまう処理を見つけたので、数行書き換えたら総ターン数が四千くらい減った。

総ターン数：84,533
時間：2.4sec

また自分の環境では通るのに、提出後に落ちた。このエラーを取るために時間をかけるのと、一から書き直すのどっちがいいのか。というかもっと細かく通るかどうか確認しておくべきだった。

色々変更しながら確認したら制限時間をオーバーしているだけだった。前にエラーで落ちたのもこれが原因だったのかも。

七日目

スコアが伸び悩んでいたので、どうしようかなーと考えていて、ふと思い出した。

今1位の人はコンテスト初日からスコアが高かった。ということはおそらく複雑なアルゴリズムではなく、典型的なアルゴリズムを使っているはず。（最初はみんな典型的な方法を試すはず）

ということでこれからやること

貪欲法で経路生成
焼きなまし法で改善
高さを考慮したカメの移動

やっぱりローカル環境とサーバ環境では実行速度が変わることもあるらしい。 time関数とかで時間を取得すると遅いとかかな。

八日目

ステージを再現してまるごとシミュレート。焼きなまし法で最善の探索方法を見つけたい（実装中）。

変更部分だけコストを計算し直すということをちゃんとやれば処理を削減できる気がする。

ステージを18分割してぐるっと回るように一区画ずつ回っていく。今のところ18分割した経路が一番スコアは良い。

経路改善に山登り法を使っているけど、どこかバグっている気がする。本来なら総ターン数は計算回数を増やすごとに減るか、とどまるはず。だけどなぜが増えた。あと、局所解にはまっている気もする。

九日目

高速化の話。乱数生成でrandは遅いからXorShiftの方がいいという話を聞いたけど、そんなに変わっている気がしない。というか乱数生成よりも重い処理があるのかも。

とりあえずvectorのコピーはかなり重いということが分かった。コピーしているところを二つ改善しただけで、倍以上早くなった。

ずっとよく分からないバグに悩まされていて、シミュレータの実装がおかしいのかと思っていたけど、変数の初期化を忘れていただけだった。

総ターン数：81,954
時間：38sec

シミュレータは重すぎて100回くらいしか回せないけど、それでも二千くらい総ターン数を減らせた。

今のところ手詰まり。もっとシミュレータを高速化させたいけど難しい。

ランキングを見ていたら、実行時間が一桁秒で載っている人もいたので、もっとスマートに効率の良い経路を探索できるらしい。

前回や前々回のハル研プロコンで提出されたソースコードや、そのソースコードの解説を読んでいたら、ビームサーチという単語を見つけた。

以前のコンテストの記事

chokudaiさんのビームサーチの説明

chokudai.hatenablog.com

十日目

他の用事のためなし。

十一日目

チャレンジスコアが発表された。 77,777は達成したい。

ヒントとしてステージには、エサが高め、低め、バランス良く、の三種類あるらしい。

あと自分で確認して分かったのが、エサの個数は40、60、80,100がある。

このへんに着目して改善できたらうれしい。

十二日目

ソースコードを色々書きすぎてファイルが迷子になった。応募履歴から提出したコードを見れることを初めて知った。そこから一番良かったものをコピペ。 gitで管理しとくべきだなって何回か思ってる。

ビームサーチとか焼きなましとか色々やってみて分かったことは、一気にスコア伸ばせたら嬉しいけど、実際は地道に少しずつ改善していくのが良さそう。

ステージを18分割してぐるっと渦を巻くように分割した区画を一つずつ回っていく。その流れにあうようにエサをソートしてみた。

総ターン数：78,587
時間：54sec

十三日目

あと少しでチャレンジスコアに届きそうだったので、山登り法の回数やシミュレートの回数をいじって越えようとしていたけど上手くいかない。そこで一度山登り法とシミュレートを行わなかったらどうなるかを調べたら、チャレンジスコアを超えた。

総ターン数：76,950
時間：3.5sec

山登り法の実装がなんかおかしくなっていたらしい。

十四日目

シミュレートを取り入れた。

総ターン数：76,196
時間：58sec

最終日

ランキングを眺めていた。

終わってから

まずはコンテストのアンケートに取り組んだ。粗品がもらえるらしい。

その後、Twitterでプロコンに参加した方々の解法ツイートを眺めていた。

1位 : chokudai search + 山登り
2位 : 順序を2手まで先読みする木探索、亀の割り当ては貪欲
3位 : 亀を集めて時計回りに食べる + 山登り、亀の割り当ては貪欲
その他 : TSP + 多点スタート山登り/焼きなまし、クラスタリングしてからTSP、等多くの亀の割り当ては貪欲
— リッキー (@rickytheta) October 15, 2019

思っていたよりは自分が考えていた方針は大きく外れていたわけではなさそう。だけどだからといってもっとスコアが伸ばせたかというとそれは違うんだろうなーとしみじみ思ってる。もっと精進しないとランキングには載れなさそう。

おわりに

コンテストのはじめの頃はランキングに載れたらいいな～と軽く考えていましたが、思っていた以上に参加している方々のレベルが高くて驚きました。そのため途中からはチャレンジスコアを達成できたらいいな～と目標を変えて取り組んでいました。結果としてチャレンジスコアは超えられたので良かったです。

コンテスト中は公式のビューアの存在がありがたかったです。自分が書いたプログラムの結果をすぐに確認できるし、ビューアのカメの動きを眺めているだけでも楽しめました。

ハル研プロコン2019は様々な経験ができた二週間となりました。最後まで楽しかったので、また来年も参加したいです。

2019-09-16

CODE FESTIVAL 2015 C - 今日から始める競プロ日記

AtCoder

はじめに

chokudaiさんの今日の一問を解いてみた。

CODE FESTIVAL 2015 チーム対抗早解きリレー C

問題自体は簡単だけど、早解きするとなると難しい。

今日の問題……じゃないけどお休みした分の問題にネタ枠をｗ
10人一組のリレーだからこそ出題出来た問題。10人いれば円周率覚えてる奴くらいいるだろ、みたいな感じ。
C - 円周率 https://t.co/meokD4Asur #chokudai今日の一問
— chokudai(高橋直大)🌸🍆🍡 (@chokudai) September 9, 2019

C - 円周率

一桁の整数Nが与えられる
そのNが円周率の何桁目に現れるか求めよ

atcoder.jp

解いた方針

円周率を50桁くらいコピペしただけ。

chokudaiさんのツイートを読んでなるほどなーとおもった。

円周率問題の解説！
asin(-1)とかMATH_PIとかを使うことで、double型の精度でのπを得ることができますが、この精度だとまだ0の時だけが求まりません。
でも0の時の答えはサンプルにあるので、0の時だけ分岐してあげれば、ACすることができます！覚えてなくても解ける！やさしい！
— chokudai(高橋直大)🌸🍆🍡 (@chokudai) September 10, 2019

コード

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

int main()
{
    string pi = "3141592653589793238462643383279502884197169399";
    char N;
    cin >> N;
    for(int i = 0; i < pi.size(); i++)
    {
        if(N == pi[i])
        {
            cout << i << endl;
            return 0;
        }
    }
}

おわりに

「問題を解けること」と「問題を早解きできること」は別物だなーということを改めて知った。

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

2019-09-16

AtCoder Beginner Contest 141 D - 今日から始める競プロ日記

AtCoder

はじめに

AtCoder Beginner Contest 141 （ ABC 141 ）に参加。

D問題でだいぶ躓いてしまったので、解いた方針をまとめておく。

ちなみに、priority_queue の存在を忘れていて、結局 multiset を使って解いた。

この記事では priority_queue を使ったほうでまとめる。

D - Powerful Discount Tickets

N個の品物を買う。
i番目の品物の値段はAi
割引券をM枚持っている
任意の品物に対して任意の枚数の割引券を使うことができる
割引券一枚で半額（小数点以下切り捨て）
最小いくらで買い物ができるか求めよ

atcoder.jp

解いた方針

方針はすぐに立った。

一番値段が高い品物から順々に割引券を使っていけば良い。

問題は実装方法。

一番大きい値段を知るために、常に配列をソートした状態にしたいが、愚直にやるとO(NM)になるはずだからダメ。

だからデータをどの型で扱うかを考える必要がある。

私はmultisetを使って解いたけど、解説を読んだらpriority_queueを使うといいよって書いてあって、「聞いたことある～」とちょっと悲しくなった。

コンテスト中にもっと早く気づきたかった。

cpprefjp.github.io

qiita.com

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
    // 入力
    ll N, M;
    cin >> N >> M;
    priority_queue<ll> pq; // ソートの状態でデータを保持
    for(int i = 0; i < N; i++)
    {
        ll a;
        cin >> a;
        pq.push(a);
    }
 
    // M回分、最大値を半分に
    for(int i = 0; i < M; i++)
    {
        ll maxv = pq.top() / 2LL;
        pq.pop();
        pq.push(maxv);
    }
 
    // 合計値を計算
    ll sum = 0;
    for(int i = 0; i < N; i++)
    {
        sum += pq.top();
        pq.pop();
    }
 
    // 解を出力
    cout << sum << endl;
    return 0;
}

おわりに

D問題までを早解きできるようになりたい（目標は三十分）。

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

2019-09-14

AtCoder Beginner Contest 111 C - 今日から始める競プロ日記

AtCoder

はじめに

chokudaiさんの今日の一問を解いてみた。

AtCoder Beginner Contest 111 C ( ABC 111 C )

方針はすぐに立ったけど、結局20分くらいかかってしまった。

たぶん方針の立て方が甘いのだと思う。

今日の問題は、 /\/\/\/！
……ごめん、名前のインパクトで選びました。でも普通に良い問題です。といてね！#chokudai今日の一問 https://t.co/1dhKInp8qS
— chokudai(高橋直大)🌸🍆🍡 (@chokudai) September 11, 2019

C - /\/\/\/

数列が与えられる。

この数列の偶数番目と奇数番目をそれぞれ同じ値にしたい。

値を書き換える最小回数を求めよ。

atcoder.jp

解いた方針

与えられた数列を偶数番目の数列と奇数番の数列に分ける
二つの数列においてそれぞれ最頻値と二番目の最頻値を求める
あとは最頻値となる値に数列を揃えればよい（書き換える最小回数を求める）
気を付けることは偶数番目と奇数番目の値は異なる必要があること
つまり最頻値となる値が同じ場合はどちらかを二番目の最頻値の値にすることが必要

コード

解いた方針とちょっと違うことをしてる。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
 
int main()
{
    // 入力
    map<int, int> mp1;
    map<int, int> mp2;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        if(i % 2 == 0) mp1[a]++;
        else mp2[a]++;
    }

    // 最頻値から答えを求める１
    int max1 = 0;
    int key = 0;
    for(pair<int, int> m: mp1)
    {
        if(m.second > max1)
        {
            max1 = m.second;
            key = m.first;
        }
    }
    int max2 = 0;
    for(pair<int, int> m: mp2)
    {
        // mp1の最頻値となるkeyとは異なる値を選ぶ
        if(m.second > max2 && m.first != key) max2 = m.second;
    }
    int ans1 = (N/2 - max1) + (N/2 - max2);

    // 最頻値から答えを求める２
    max1 = 0;
    key = 0;
    for(pair<int, int> m: mp2)
    {
        if(m.second > max1)
        {
            max1 = m.second;
            key = m.first;
        }
    }
    max2 = 0;
    for(pair<int, int> m: mp1)
    {
        // mp2の最頻値となるkeyとは異なる値を選ぶ
        if(m.second > max2 && m.first != key) max2 = m.second;
    }
    int ans2 = (N/2 - max1) + (N/2 - max2);

    // 答えを出力
    int ans = min(ans1, ans2);
    cout << ans << endl;
    return 0;
}

おわりに

無難に解けた

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

はじめに

目次

エンジニア戦闘力とは何か

エンジニア戦闘力の仕組み

問題の難易度について

効率の良い戦闘力の上げ方

おすすめの問題ランクと難易度

初めてpaizaを利用する方におすすめの問題

スキルチェックの問題が難しいと感じたら

現在の私の戦闘力

おわりに

はじめに

D - Triangles

コンテスト中に解いた方針

コンテスト中に書いたコード（ちょっといじった）

想定解の方針

解説動画を参考に書いたコード

おわりに

今日から始める競プロ日記まとめ

はじめに

最大の利益

制約

解いた方針

提出したコード

おわりに

今日から始める競プロ日記まとめ

はじめに

問題

ビューアの様子

結果

一日目

二日目

三日目

四日目

五日目

六日目

七日目

八日目

九日目

十日目

十一日目

十二日目

十三日目

十四日目

最終日

終わってから

おわりに

はじめに

C - 円周率

解いた方針

コード

おわりに

今日から始める競プロ日記のまとめページ

はじめに

D - Powerful Discount Tickets

解いた方針

コード

おわりに

今日から始める競プロ日記のまとめページ

はじめに

C - /\/\/\/

解いた方針

コード

おわりに

今日から始める競プロ日記のまとめページ