HACK TO THE FUTURE 2019予選 参加記 のまとめ

北大日立マラソン1st 参加記 のまとめ - minus9d's diary北大日立マラソン2nd 参加記 のまとめ - minus9d's diary に引き続き、HACK TO THE FUTURE 2019予選 - AtCoderの参加記を勝手ながらまとめました。

順位 atcoderのID URL 備考
1 kimiyuki HACK TO THE FUTURE 2019予選: A - ばらばらロボット
2 tomerun twitter
3 ats5515 twitter
4 sugim48
5 maroonrk
6 kurenai3110
7 shindannin HACK TO THE FUTURE 2019予選の反省 - じじいのプログラミング
8 hoshi524 twitter
9 WA_TLE
10 omi
11 not twitter (終了後、142k!)
12 spica314 twitter
13 hakomo twitter, twitter
14 packer_jp twitter
15 shamal_ref twitter
16 tanzaku twitter
17 tsukasa_diary twitter
18 YujiSoftware twitter
19 sumoooru twitter
20 iwashi31 twitter
21 math twitter
22 minus9d(自分です) minus9d's diary

HACK TO THE FUTURE 2019予選 参加記

HACK TO THE FUTURE 2019予選に参加しました。8時間中7時間半ほど参加して22位でした。前回より1位だけランクアップしましたが順位表の1ページ目には入れず残念。

試行ログ

まずは周囲に壁をつくるだけの初期配置を試し、80904点。


マークを盤面いっぱいにランダムに配置して点数を計算する方法を実装し、91248点。試行回数は手元で2700回ほど。


山登り法を実装。すなわち、ある盤面に対してランダムな位置にランダムなマークを配置し、点数が上がれば採用。114674点。このあたりで方向性がつかめてくる。


ベストなスコアを出す盤面について、付与されたマークの数を数えてみると、LやRの出現頻度がD, T, #よりもかなり多いことに気付く。そこでマークとしてLやRのみしか使わないようにする。119184点。


このあたりからはかなり怪しい修正を繰り返した。値は上がったり下がったりを繰り返していたので、どれがどれくらい効いたかがよくわからない。

  • 焼きなましの導入。点数の減少率が閾値以下であれば、ある確率でその変化を受け入れる。
  • マークを配置するマス目を左上からラスタスキャン順に全部試す
  • スコアが変わらなければ遷移
  • 変更するマスが必ず今と異なるマークとなるようにする(これは当たり前)
  • スコアの計算をするとき、停止カウントが4以上のマスにも点数に違いを与えて少しでもよい状態の方に遷移しやすくするように変更。

最終的なベストスコアは126504点で22位。正の点数を取った人が518人なので上位5%にすべりこめた。

本番中に気付いていたが実装できなかったアイデア

  • 点数再計算のとき、影響を受けるマス以降のみを再計算

本番中に気付かなかったアイデア

  • 命令列の圧縮
  • L, Rのマス上で動きに影響を受けるロボットだけ再計算する
  • 中央に近いマスから順番にマークを変える(終了後の動画より)
  • 初期盤面を全部Lで埋めて始める notさんのツイート
  • L, Rしか使わないと決めることでシミュレーションのコードを簡単化
  • example_01 の解をコードに埋め込む

感想と反省

終了後の動画解説の通り、L, Rだけ使うという方針に早期に辿りつけたのはよかったです。しかしD, T, #も用意されているからにはどこかで使うべきなのではないかとの疑念が頭を離れず、その後もちょくちょく復活を試みていたのは結果からいうと時間の無駄でした。また、LとRしか使わないことを決断してしまえばもっと高速化できる余地がありましたが、その発想に至れませんでした。

ずっとZipで配布された盤面のみを使って検討をしていましたが、検討が煮詰まってくるとローカルの点数から提出後の点数を予測するのが難しくなっていました。サボらず複数盤面からローカルの点数を算出したほうが結果的には無駄がなかったかなと思います。

LinuxにてWindows 10のインストーラUSBを作成する

家のWindows 10が不調になりました。他にWindowsマシンを持っていなかったので、手持ちのLinux (Ubuntu 16.04 LTS) を使ってWindows 10のインストーラUSBを作成しました。この記事はその記録です。

ISOイメージの取得

Windows 10 のディスク イメージ (ISO ファイル) のダウンロード から取得しました。

DVDにISOイメージを焼こうとして失敗

Brasero というソフトをsudo apt-get install braseroで入手して、 DVD-RにISOを焼こうとしたのですが、なぜか失敗しました。USB接続のDVDライターを適当に使ったのが怪しいですが深追いしていません。

WoeUSBのインストール

USBインストーラの作成にはWoeUSBというソフトを使いました。以下でインストールできます。(参考:WebUpd8 : Alin Andrei

$ sudo add-apt-repository ppa:nilarimogard/webupd8
$ sudo apt-get update
$ sudo apt-get install woeusb

なお、USBインストーラを作成するソフトにはEtcherというソフトもありますが、このソフトはWindowsのイメージは取り扱えません。Windowsのイメージを焼こうとすると以下のダイアログが出ました。 f:id:minus9d:20181112220257p:plain

USBインストーラの作成

WoeUSBのGUIアプリを起動します。

以下のように必要事項を埋めて

f:id:minus9d:20181112223527p:plain

"Install"を押したのち、rootのパスワードを入れると、

Installation failed!
Exit code: 256
Log:
WoeUSB v@@WOEUSB_VERSION@@
==============================
Error: Target device is currently busy, unmount all mounted partitions in target device then try again
Target device is busy, please make sure you unmount all filesystems on target device or shutdown the computer before detaching it.

というエラーで失敗します(画像版は以下)。

f:id:minus9d:20181112223815p:plain

先にUSBメモリをアンマウントする必要があるようです。GPartedというソフト(sudo apt-get install gpartedで入手可)で、USBメモリをさすデバイスを選んで右クリックし「アンマウント」を選ぶことでアンマウントできました。

この後WoeUSBをもう一度試すと無事インストーラUSBを作成できました。

Pythonのコード改善のためのツール5つを試してみた

Pythonのコードを改善するためのツールについて一通り試してみました。各ツールのインストール方法や使い方については Pythonのスタイルガイドとそれを守るための各種Lint・解析ツール5種まとめ! - Sider Blog に詳細にまとまっているのでおすすめです。

サンプルコード

以下のサンプルコードを対象に、各ツールの出力を確かめてみます。

import time
import sys
import fractions

def func1(varA,varB):
    '''return sum of a and b'''
    varC = 42
    return (varA + varB)


print(func1(fractions.Fraction(1, 2), fractions.Fraction(1, 3)))
3 + 5
sys.exit(0)

このスクリプトsample.pyという名前で保存したのち、以下のスクリプトで実験をしました。各ツールはすべてデフォルトです。

for name in pycodestyle \
            pydocstyle \
            pyflakes \
            flake8 \
            pylint
do
    echo "================="
    echo ${name}
    echo "================="
    echo "version:" $(${name} --version)
    ${name} sample.py
    echo ""
done

各ツールの紹介

pycodestyle

  • 用途:スタイルチェック
    • PEP 8で規定されているPython公式のスタイルガイドに違反する箇所を見つけてくれる。
  • 詳細

出力は以下のとおりです。空白行やスペースの不足が指摘されています。

version: 2.0.0
sample.py:5:1: E302 expected 2 blank lines, found 1
sample.py:5:15: E231 missing whitespace after ','

pydocstyle

出力は以下のとおりです。docstringに関するエラーのみが指摘されています。

version: 2.1.1
sample.py:1 at module level:
        D100: Missing docstring in public module
sample.py:5 in public function `func1`:
        D300: Use """triple double quotes""" (found '''-quotes)
sample.py:5 in public function `func1`:
        D400: First line should end with a period (not 'b')
sample.py:5 in public function `func1`:
        D403: First word of the first line should be properly capitalized ('Return', not 'return')

pyflakes

  • 用途:エラー解析
  • 詳細
    • ソースファイルを解析して、importしたけど使っていないモジュールや、未使用の変数などを報告。
    • pycodestyleとは違い、コードのスタイルについては分析しない。
    • 高速さに重点を置く。Pylintよりも高速。
    • 正しいコードを過ってエラーと報告しないように細心の注意が払われている。
    • 解析はファイル単位で行われるので、importで読み込むファイルにまたいだ解析はできない。
    • もっと詳しい分析が必要な場合は、Flake8を使う。

出力は以下のとおりです。未使用のimport文、未使用の変数が報告されています。

version: 1.2.3
sample.py:1: 'time' imported but unused
sample.py:7: local variable 'varC' is assigned to but never used

Flake8

  • 用途:スタイルチェック + エラー解析 + 複雑度チェック
  • 詳細

出力は以下のとおりです。ちょうど出力がpycodestyleとpyflakesの和になっていることがわかります。

version: 2.6.2 (pycodestyle: 2.0.0, mccabe: 0.5.3, pyflakes: 1.2.3) CPython 3.6.4 on Windows
sample.py:1:1: F401 'time' imported but unused
sample.py:5:1: E302 expected 2 blank lines, found 1
sample.py:5:15: E231 missing whitespace after ','
sample.py:7:5: F841 local variable 'varC' is assigned to but never used

Pylint

  • 用途:スタイルチェック + エラー解析
  • 詳細
    • 老舗のツール。effective pythonで推されていた。
    • Plugin機能がある。

出力は以下のとおりです。flake8では報告されなかった、変数名の規則違反(varAなど)や、意味のない文('3 + 5')が報告されています。 最終行にこのコードの得点が表示されるのが面白いです。この場合10点満点中0点という意味です。さらには負の点数になることもあります。

No config file found, using default configuration
 Python 3.6.4 |Anaconda custom (64-bit)| (default, Jan 16 2018, 10:22:32) [MSC v.1900 64 bit (AMD64)]
No config file found, using default configuration
************* Module sample
C:  5, 0: Exactly one space required after comma
def func1(varA,varB):
              ^ (bad-whitespace)
C:  8, 0: Unnecessary parens after 'return' keyword (superfluous-parens)
C:  1, 0: Missing module docstring (missing-docstring)
C:  5, 0: Argument name "varA" doesn't conform to snake_case naming style (invalid-name)
C:  5, 0: Argument name "varB" doesn't conform to snake_case naming style (invalid-name)
C:  7, 4: Variable name "varC" doesn't conform to snake_case naming style (invalid-name)
W:  7, 4: Unused variable 'varC' (unused-variable)
W: 12, 0: Statement seems to have no effect (pointless-statement)
W:  1, 0: Unused import time (unused-import)

------------------------------------------------------------------
Your code has been rated at 0.00/10 (previous run: 0.00/10, +0.00)

flake8のプラグイン

flake8のプラグインを別途インストールすることで、flake8にルールを追加することが可能です。pip search flake8-するとわかるのですが、大量のプラグインが存在しています。ここでは2つだけ紹介します。

hacking

  • 用途:Flake8にOpenstack社のルールを追加するプラグイン
  • 詳細
    • pip install hackingしたあとにflake8を呼び出すと、flake8に、Openstack社が独自に追加したルールが追加される

出力は以下のとおりです。Hで始まる行が、flake8に追加された検出された項目になります。この例だとimport文の順番がアルファベット順になっていなかったことで怒られています。

version: 2.6.2 (pycodestyle: 2.0.0, mccabe: 0.5.3, ProxyChecker: 0.0.1, hacking.core: 0.0.1, pyflakes: 1.2.3) CPython 3.6.4 on Windows
sample.py:1:1: F401 'time' imported but unused
sample.py:2:1: H306  imports not in alphabetical order (time, sys)
sample.py:3:1: H306  imports not in alphabetical order (sys, fractions)
sample.py:5:1: E302 expected 2 blank lines, found 1
sample.py:5:15: E231 missing whitespace after ','
sample.py:7:5: F841 local variable 'varC' is assigned to but never used

flake8-docstrings

  • 用途:Flake8にpydocstyleのルールを追加するプラグイン
  • 詳細
    • pip install pydocstyleしたあとにflake8を呼び出すと、flake8に、pydocstyleのルールが追加される

出力は以下のとおりです。Dで始まる行がdocstringに関する報告です。

version: 2.6.2 (pycodestyle: 2.0.0, mccabe: 0.5.3, pyflakes: 1.2.3, flake8-docstrings: 1.3.0, pydocstyle: 2.1.1) CPython 3.6.4 on Windows
sample.py:1:1: D100 Missing docstring in public module
sample.py:1:1: F401 'time' imported but unused
sample.py:5:1: D300 Use """triple double quotes"""
sample.py:5:1: D400 First line should end with a period
sample.py:5:1: D403 First word of the first line should be properly capitalized
sample.py:5:1: E302 expected 2 blank lines, found 1
sample.py:5:15: E231 missing whitespace after ','
sample.py:7:5: F841 local variable 'varC' is assigned to but never used

サンプルコードの修正例

すべてのエラーや警告が消えるまで修正したのが以下のコードです。良いコードになったでしょうか?

"""Sample for hatena diary."""

import fractions
import sys


def func1(var_a, var_b):
    """Return sum of a and b."""
    return var_a + var_b


print(func1(fractions.Fraction(1, 2), fractions.Fraction(1, 3)))
sys.exit(0)

その他のツール

mypy

型ヒントのためのツールです。自分はまだ理解できていません。

  • 用途: Optional Static Typing for Python
    • Python 3.6に導入された型ヒントを使っている人向けのツール。型の誤りを静的に解析する。

PyChecker

  • 用途:スタイルチェック + エラー解析
  • 詳細
    • Python 2.x系が対象。開発が止まっているようなので今から使う理由はないでしょう。

個人的な結論

  • まずはflake8をデフォルトで使う
  • flake8で足りないところがあれば、Pylintを併用するか、flake8の適当なプラグインを見つけて導入する

参考

KUPC 2018 C - 七目

本番中にパニクって解けなかったのを反省して解き直しました。DFSくらいさっと書けないとだめですね…。

  • 問題

    • C - 七目
    • 9x9のマスが白で埋められている。白マスが縦・横・斜めのいずれにも白マスが7個以上連続しないように、11個のマスを黒く塗る塗り方を求める
  • 解法

    • 素直にDFS。黒く塗るしかないマスは黒く塗り、そうでない箇所では黒く塗る場合・塗らない場合の両方を試す。
    • 各行に少なくとも一つは黒マスが必要なことを利用して枝刈りすると、自分の古いPCで1分20秒ほどですべての解が出ました。
  • コード

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

const int N = 9;
const int W = N;
const int H = N;

void debug_print(vector<vector<char>>& cells, int h_now, int w_now, bool print_cursor=true) {
    cout << "=================" << endl;
    REP(h, H) {
        REP(w, W) {
            if (h == h_now && w == w_now && print_cursor) {
                cout << "[";
            }
            else {
                cout << " ";
            }
            cout << (cells[h][w] == 1 ? '#' : '.');
            if (h == h_now && w == w_now && print_cursor) {
                cout << "]";
            }
            else {
                cout << " ";
            }
        }
        cout << endl;
    }
    cout << "=================" << endl;
}


pair<int,int> idx_to_h_w(int idx) {
    return {idx / N, idx % N};
}

// 今いるマスの左・上・右上・左上を見て、このマスを黒く塗る必要があるかを判定
bool should_put_stone(int idx, vector<vector<char>>& cells) {
    auto hw = idx_to_h_w(idx);
    int h, w;
    tie(h, w) = hw;

    int dx[] = {-1, 0, -1, 1};
    int dy[] = {0, -1, -1, -1};
    REP(d, 4) {
        int seq = 0;
        FOR(i, 1, 7) {
            int h2 = h + dy[d] * i;
            int w2 = w + dx[d] * i;
            if (w2 < 0 || w2 >= W || h2 < 0 || h2 >= H) {
                break;
            }
            if (cells[h2][w2] == 0) ++seq;
        }
        if (seq == 6) return true;
    }
    return false;
}

bool dfs(int idx, vector<vector<char>>& cells, int remain) {
    auto hw = idx_to_h_w(idx);
    int h, w;
    tie(h, w) = hw;

    // 今いるマスをとりあえず白くする
    // これを忘れると正しくdfsできない!
    cells[h][w] = 0;

//    cout << "remain = << " << remain << endl;
//    debug_print(cells, h, w);

    // 各行に少なくとも1つ黒マスが必要なことから
    // もう条件を満たせないならfalseを返す
    int minimum_need = H - h - 1;
    if (remain < minimum_need) return false;

    // 最後の判定
    if (idx == H * W - 1) {
        if (should_put_stone(idx, cells)) {
            if (remain > 0) {
                cells[h][w] = 1;
                remain--;
            }
            else {
                return false;
            }
        }
        // 条件を満たすのでprint
        debug_print(cells, h, w, false);
        return true;
    }

    // 上・左・右上・左上いずれかに6連続で白マスなら現マスは黒く塗るしかない
    if (should_put_stone(idx, cells)) {
        // もう残数がなければおわり
        if (remain == 0) {
            return false;
        }
        else {
            cells[h][w] = 1;
            return dfs(idx + 1, cells, remain - 1);
        }
    }
    // 石を置いても置かなくてもよい
    else {
        // 石を置かない場合
        auto ret = dfs(idx + 1, cells, remain);
        // 石を置く場合
        if (remain > 0) {
            cells[h][w] = 1;
            ret |= dfs(idx + 1, cells, remain - 1);
        }
        return ret;
    }
}

int main(void)
{
    vector<vector<char>> cells(N, vector<char>(N));
    dfs(0, cells, 11);
    return 0;
}

出力されたのは以下の16盤面です。

=================
......#..
....#....
..#......
#......#.
.....#...
...#.....
.#......#
......#..
....#....
=================
=================
......#..
...#.....
#......#.
....#....
.#......#
.....#...
..#......
......#..
...#.....
=================
=================
......#..
..#......
.....#...
.#......#
....#....
#......#.
...#.....
......#..
..#......
=================
=================
......#..
..#......
#......#.
.....#...
....#....
...#.....
.#......#
......#..
..#......
=================
=================
......#..
..#......
#......#.
...#.....
....#....
.....#...
.#......#
......#..
..#......
=================
=================
.....#...
...#.....
.#......#
......#..
....#....
..#......
#......#.
.....#...
...#.....
=================
=================
.....#...
..#......
......#..
...#.....
#......#.
....#....
.#......#
.....#...
..#......
=================
=================
....#....
......#..
.#......#
...#.....
.....#...
#......#.
..#......
....#....
......#..
=================
=================
....#....
..#......
#......#.
.....#...
...#.....
.#......#
......#..
....#....
..#......
=================
=================
...#.....
......#..
..#......
.....#...
.#......#
....#....
#......#.
...#.....
......#..
=================
=================
...#.....
.....#...
#......#.
..#......
....#....
......#..
.#......#
...#.....
.....#...
=================
=================
..#......
......#..
...#.....
#......#.
....#....
.#......#
.....#...
..#......
......#..
=================
=================
..#......
......#..
.#......#
.....#...
....#....
...#.....
#......#.
..#......
......#..
=================
=================
..#......
......#..
.#......#
...#.....
....#....
.....#...
#......#.
..#......
......#..
=================
=================
..#......
.....#...
.#......#
....#....
#......#.
...#.....
......#..
..#......
.....#...
=================
=================
..#......
....#....
......#..
.#......#
...#.....
.....#...
#......#.
..#......
....#....
=================

TCO19 Single Round Match 737 - Div1 Easy (AliceAndBobEasy)

2018-09-19のTopcoderに3ヶ月ぶりで出場。実験を執念で繰り返してかろうじてEasyが解けました。あわててNimゲームの勝利条件を蟻本で確認しましたが、もはやこれが前提知識となっているとは。

以下、Easyの解法とPythonコードです。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# [問題]
#   Nが与えられる。
#   以下の条件を満たす、N個の山を構成せよ。
#     Nimゲームで先攻が勝つような先攻のmove (winning move) 数を最大化する
#     各山の石の個数は1 ~ 737373737個
#   Nは1~37。
#
# [解法]
#   まずNimの勝利条件を蟻本で確認。
#   これによると、N個の山の石の数でxorをとった結果が0なら負け、非0なら勝ちの状態である。
#
#   まずNが奇数の場合を考える。
#   例えば山が5個あるとする。
#   山を順にa, b, c, d, e,
#   各山の石の数をn(a), n(b), ...とする。
#
#   1つ目の山から任意の個数の石を取り除いたあと、
#   勝ちの状態を作れるか、言い換えると、残りの山のXORをちょうど0にできるか、を考えてみる。
#
#   石の個数をa, b, c, d, eだとすると、
#   山aから石を取り除いた後の値が、n(b) ^ n(c) ^ n(d) ^ n(e)に等しくなることが、
#   この山から石を取る場合の唯一の勝利条件である。
#
#   必要な条件は、n(a) > n(b) ^ n(c) ^ n(d) ^ n(e)。
#
#   ここで、n(a) = 0b100001
#          n(b) = 0b100010
#          n(c) = 0b100011
#          n(d) = 0b100100
#          n(e) = 0b100101
#   としてみると、n(b) ^ n(c) ^ n(d) ^ n(e)の結果、最上位ビットは0になる。
#   よって n(a) > (n(b) ^ n(c) ^ n(d) ^ n(e)) とできるので、
#   n(a)から石をとることで相手を負けにできる。
#   Nが奇数のときはこの構成法でN種類のwinning moveができる。
#
#   Nが偶数のときは、実はN-1種類のwinning moveが常に最大値となる。
#   N = 4の場合を考えると、
#          n(a) = 0b100001
#          n(b) = 0b100010
#          n(c) = 0b100011
#          n(d) = 0b000001
#   と、最後の山を1にすることで、N-1種類のwinning moveができる。
#
#   では、N種類のwinning moveは可能なのか。
#   本番中では、実験的に不可能でありそうなことを確かめたが、
#   証明はできなかった。https://www.topcoder.com/blog/single-round-match-737-editorials/ 
#   を読んで、証明を理解できた。
#   
#   証明:
#   今、Nが偶数で、winning positionにいるとする。(つまり先手が石を取る直前である)
#   すべての石のxorは非ゼロなので、
#   すべての石のxorをとった値のうち、もっとも左側の1が立つビットの位置をxとする。
#   山の数は偶数だが、x番目のビットが立っている山の数は奇数である。
#   ということは、少なくとも1つの山(Pとおく)は、そのx番目のビットが立っていない。
#   山Pについては、どう石をとっても、先手は勝てない。
#   よってNが偶数の場合は、最大でもN-1種類のwinning moveしかできない。
#
# [本番]
#   ブサイクだが上記解法とほぼ同じ実装ができた。
#   生成された配列が条件を満たすかチェックする関数を作っていたので2個撃墜できた


import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import re
import string

class AliceAndBobEasy:
    def make(self, N):
        if N == 1:
            return (737,)
        elif N == 2:
            return (737, 373)
        elif N % 2 == 1:
            ret = []
            ret.append(1 << 28)
            ret.append((1 << 28) + (1 << 27))
            ret.append((1 << 28) + (1 << 26))
            for i in range(N - 3):
                ret.append((1 << 28) + i + 1)
            return tuple(ret)
        else:
            ret = []
            ret.append(1)
            ret2 = list(self.make(N - 1))
            ret += ret2
            return tuple(ret)

AGC027 B - Garbage Collector

2018-09-15のAGCに出場。Aと、Bの部分点が解けて325位。Bは考え方は正しかったのですが、計算途中のオーバーフローに泣きました。上位陣でもBはスルーしている人が多かった中で、DPをやりたくなる衝動を抑えつつ部分点が取れたので、少し自信が付きました。もっとも証明できてない箇所があるのですが。

以下、Bの解法とコードです。g++の拡張(__int128)を使っているため、Visual Studioではビルドが通りません。

// 本番時、解説PDFと同様に考えられたが、オーバーフローでlargeがWA。
// 証明できていない箇所がある。
//
// [解法]
// 以下の場合を例にとって考える
//    |------*-----*-----*------*-----*------*-----*
//    0      a     b     c      d     e      f     g
// 原点から距離iの場所にあるゴミを、ゴミiと呼ぶことにする。
//
// ロボットがゴミ箱にゴミを捨てる回数をK回と固定して考える。例えばK=3とする。
// 
// このとき、
// 1回目のゴミ捨ては、「ゴミgまで行ってゴミgを拾い、ゴミa ~ dのどれかを拾いながら原点に戻る」
// 2回目のゴミ捨ては、「ゴミfまで行ってゴミfを拾い、ゴミa ~ dのどれかを拾いながら原点に戻る」
// 3回目のゴミ捨ては、「ゴミeまで行ってゴミeを拾い、ゴミa ~ dのどれかを拾いながら原点に戻る」
// のが最適となる。本番中も直感的にそう思ったが、証明できていない。解説pdfにも「明らか」としか書かれていない。
//
// 上記を信じると、ゴミを拾いに行く行きのコストは常に定数となる。
// したがって残りの問題は、「3回のゴミ捨ての帰りのうち、ゴミa, b, c, dをどのタイミングで拾うか」
// を、帰りのコストが最小になるように決める問題となる。
//
// まずゴミa~cはないものとして、ゴミdについてついて考える。するとゴミdは3回のうち
// どのタイミングで拾っても、かかるコストは同じになることがわかる。よって1回目で拾うことにする。
//
// 次、ゴミcについて考える。選択肢として、1回目で拾うか、2回目で拾うかの2通りがある。
// (3回目に拾うのは、2回目に拾うのとコストが同じであるので考える必要がない)
// これは2回目に拾うのがよい。
// なぜなら、もし1回目で拾うと、ゴミbからゴミcまでの区間のコストが9になるのに対し、
// 2回目で拾うと、同区間のコストが4になるから。
// (ここも証明が怪しい)
//
// 同様に、遠くにあるゴミから順に、1回目のゴミ捨て、2回目のゴミ捨て、3回目のゴミ捨て、
// また最初に戻って1回目のゴミ捨て、...と拾うのが最適。
//
// この場合だと、
// 1回目のゴミ捨ては、「ゴミgまで行ってゴミgを拾い、ゴミd、ゴミaを拾いながら原点に戻る」
// 2回目のゴミ捨ては、「ゴミfまで行ってゴミgを拾い、ゴミcを拾いながら原点に戻る」
// 3回目のゴミ捨ては、「ゴミeまで行ってゴミgを拾い、ゴミbを拾いながら原点に戻る」
// が最適となる。
//
// 累積和を使うとこれを効率的に計算でき、largeが解ける。

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int main(void)
{
    cin.sync_with_stdio(false);
    ll N, X;
    cin >> N >> X;
    vector<ll> Xs(N);
    REP(n, N) cin >> Xs[n];

    // 原点から遠い順に距離をソート
    auto Ys = Xs;
    reverse(ALL(Ys));

    // 累積和を計算
    vector<ll> Y_sum(N);
    Y_sum[0] = Ys[0];
    FOR(i, 1, N) Y_sum[i] = Y_sum[i - 1] + Ys[i];

    __int128 ans = 1e18;  // ★ 最終的な解は1e18以下に収まるのだが、他の解候補がlong long intの範囲を超えることが
                          // あるため、__int128を使う必要がある!!!
    FOR(k, 1, N + 1) { // ゴミ箱に行く回数をkとする

        // ★この変数がlong long intを超える!!
        // ゴミを捨てる回数に応じたコストをまず計算
        __int128 local_ans = X * k;

        // 距離dにあるゴミを取りに行くコストはd, 取ったあと帰るコストは2^2 * d = 4d。
        // よって足して5d。
        // k回のゴミ捨てで、原点から遠いゴミk個をそれぞれ取って帰るコストは、
        // 累積和を使って以下のように計算できる。
        local_ans += 5 * Y_sum[k-1];

        ll i = 2 * k - 1;
        ll n = 1;

        // まだ取っていないゴミのうち、遠くにあるゴミから順番にk個のゴミを、
        // k回のゴミ捨てでの帰路にそれぞれ1個ずつ取っていくところをシミュレート。
        // もともとn個のゴミを持って帰るところをn+1個のゴミを持って帰ることにすることで
        // 増えるコストは、((n+2)^2 - (n+1)^2 = 2n + 3)。
        while (i <= N - 1) {
            local_ans += (2LL * n + 3) * (Y_sum[i] - Y_sum[i - k]);
            n += 1;
            i += k;
        }
        // 端数処理
        local_ans += (2LL * n + 3) * (Y_sum[N - 1] - Y_sum[i - k]);

        ans = min(ans, local_ans);
    }

    // __int128は出力に失敗するのでllにキャストする
    ll ans2 = (ll)ans;
    // ゴミを拾うコストは常に定数なので最後に足す
    cout << (ans2 + N * X) << endl;

    return 0;
}