nakamurk’s diary

日々思うことは残していきます。しっかり生きます。

私の解法(ABC194_Cについて)

ブログ(アウトプット)を再開するためにこちらを書きます。今回は、2021年3月6日(土)に実施されたAtCoder Begginer Contest194のC問題について(C - Squared Error*1、私の解法を解説します。

TL/DR

考え方

愚直な実装

Σの分だけ二重ループで解こうと思うと、次のようになると思います。

#include 
#define ll long long
using namespace std;

int main() {
  ll N, ret = 0; cin >> N;
  vector A(N+1); // 0オリジン(始まり)なので+1しています
  for (int i = 1; i <= N; i++) cin >> A[i];

  for (int i = 2; i <= N; i++) {
    for (int j = 1; j <= i - 1; j++) {
      ret += (A[i] - A[j]) * (A[i] - A[j]);
    }
  }
  cout << ret << endl;
  return 0;
}

しかし、これでは、入力例は問題なくても、次で詳細を説明するTLEが起こりそうな量の入力には耐えられません。

  • 入力例1

    $ IN=1.in; cat $IN; timeout -sKILL 2 bash -c "time ./a.out < $IN"
    3                // 入力
    2 8 4
    56               // 出力
    real    0m0.017s // 計算時間
    user    0m0.001s
    sys     0m0.005s
    

  • 入力例2

    $ IN=2.in; cat $IN; timeout -sKILL 2 bash -c "time ./a.out < $IN"
    5
    -5 8 9 -4 -3
    950
    real    0m0.017s
    user    0m0.000s
    sys     0m0.006s
    

  • 最大の入力例

    $ IN=stdin.; head $IN; timeout -sKILL 2 bash -c "time ./a.out < $IN"
    300000
    18
    72
    -144
    3
    10
    -57
    94
    106
    149
    Killed                          // TLE
    

私の解法

N=3で式を眺めてみます。簡単のためAiをabcと表すことにします。


\sum_{i=2}^3 \sum_{j=1}^{i-1} (A_i - A_j)^2  \\
= (b - a)^2 + (c - a)^2 + (c - b)^2  \\
= (b^2 -2ba + a^2) + (c^2 - 2ca + a^2) + (c^2 - 2cb + b^2) \\
= 2(a^2 + b^2 + c^2) - 2(ba + ca + cb)

同様にN=5で式を眺めてみますと、次のようになります。


\sum_{i=2}^5 \sum_{j=1}^{i-1} (A_i - A_j)^2  \\
= (b - a)^2 + (c - a)^2 + (c - b)^2 \\
 + (d - a)^2 + (d - b)^2 + (d - c)^2 \\
 + (e - a)^2 + (e - b)^2 + (e - c)^2 + (e - d)^2 \\
= (b^2 -2ba + a^2) + (c^2 - 2ca + a^2) + (c^2 - 2cb + b^2) \\
 + (d^2 - 2da + a^2) + (d^2 - 2db + b^2) + (d^2 - 2dc + c^2) \\
 + (e^2 - 2ea + a^2) + (e^2 - 2eb + b^2) + (e^2 - 2ec + c^2) + (e^2 - 2ed + d^2) \\
= 4(a^2 + b^2 + c^2 + d^2 + e^2) - 2(ab + ab + ad + ae + bc + bd + be + cd + ce + de)

ここで、それぞれの項の特徴に気が付きます。

  • 2乗の項
    • ①自身以外の項との組み合わせの数だけ項が存在する:N-1個
  • 各項の積
    • ②aからeの入った袋から2つ球を取り出すときの組み合わせの数

②に関して、安直に組み合わせを考えると、次のようにTLEを起こしそうです。


_N C _2 = \frac{300,000 x 299,999}2 = 44,999,850,000

ですので、計算方法でカバーします。第2項だけに着目すると次のように計算量を少なくできそうです。


ab + ab + ad + ae + bc + bd + be + cd + ce + de \\
= a(b + c + d + e) + b(c + d + e) + c(d + e) + de

これが私の実装の解説となります。変数名などが今一つですが、コード長は423 Byte、実行時間63 ms、メモリ5480 KBと、そこそこの実装だと思います。

テスト(タイムアウトをしないか試験する)

ABCのC問題は愚直に計算するとTLEが起きる問題が多いと思うので、ローカル環境でも、TLE が起きそうなケースを試しておくとよいと思います。

コマンドの準備(汎用的)

Linuxのコマンドにタイムアウトというものがあります。

$ timeout --version
timeout (GNU coreutils) 8.30

タイムアウトさせたい時間とその時のシグナルを設定できます。

# timeout -sKILL 2 ./a.out < stdin

また、実行時間も計測したいので、timeコマンドも挟んでみましょう。

$ timeout -sKILL 2 bash -c "time sleep 1"

real    0m1.003s
user    0m0.001s
sys     0m0.001s

sleep(実行時間を想定)がtimeoutを超えると次のようになります。

$ timeout -sKILL 2 bash -c "time sleep 3"
Killed

今回のテストデータの準備

試験本番ではテストデータの用意の仕方間違えました…。

$ echo 300000 > stdin; for i in `seq 1 300000`; do echo $i >> stdin; done
$ head stdin
300000
1
2
3
...

これでは制約事項「@|Ai|<=200@」が満たされていませんね。実際に入力してみると桁あふれしていることが分かります。

$ ./a.out < stdin
-7529530734753409792

ですが、実行時間だけを取ってみれば、間に合っていることが分かります。私はこの段階で、提出をしました(汗)。

$ timeout -sKILL 2 bash -c "time ./a.out < stdin"
-7529530734753409792

real    0m1.072s
user    0m0.236s
sys     0m0.079s

本来であれば、絶対値が200以下の自然数ですので、次のように与えるべきですね*2。そして、これでは完全なランダムではないですが一旦置いておくことにします。10秒ほどで、テストデータが作成できました(答えは不明です…)。

$ time (echo 300000; while true; do echo $(( ($RANDOM - 16383) % 200 )); done) | head -n 300001 > stdin

real    0m9.753s
user    0m7.171s
sys     0m10.019s

$ head stdin.
300000
18
72
-144
3
10
-57
94
106
149

実際に実行してみると、次のようになりました。1秒以内に結果が出力されているので問題なさそうですね。

$ wc -l stdin; timeout -sKILL 2 bash -c "time ./a.out < stdin"
300001 stdin
1187018545951196

real    0m0.701s
user    0m0.190s
sys     0m0.036s

蛇足

記事書くの大変ですね。この文章で5,000文字くらい(原稿用紙12枚、35ツイート分)で、2,3時間くらいかけました。丁寧な解説をされている先輩方には頭が上がりません。また、感想戦?組の実装は驚異的です。bashawkでの実装までありました。もはや脱帽というか、禿げそうです!それは脱毛w

https://m.media-amazon.com/images/I/41oruV+aJIL._SL75_.jpg https://m.media-amazon.com/images/I/51TtkYDXZFL._SL75_.jpg https://m.media-amazon.com/images/I/51hkUx5456L._SL75_.jpg

とある社畜の振り返り(2021年3月7日)

お題「#この1年の変化

数か月ぶりの投稿になります。筆まめになりたいものです。さてと…。

会いたい人・会いたくもない人と対処の仕方

家族や大好きな異性、あるいは行きたいお店など、わたしにも好きな人がいるのですが、そういう人には会いたいという気持ちと、今だから会いに行けないという気持ちがあり、とても葛藤していますね。少ない機会を設けたり、日ごろはなるべくほかの人との接触を避けるようにしています。

他方で、会わなくてもいいじゃんという人はたくさんいます。愚痴になるのであれですが、仕事をしているととうにね(笑)。誰かを否定しているだけの人、自分が常に正しいと言っている人、大した力もないのに上に立ち声だけ大きい人もういいですねそういう人、4月に部署移動するのですが、正直なところ早くバイバイしたいですね。反面教師にしかならないので、同じ時間を過ごすだけで、機会の損失なんですよね。こちらは、会いたくないという気持ちと、仕事だからしょうがなくコミュニケーションしなければいけないという気持ちで、葛藤しています。私が大人になって、我慢するのですよ。あの人たち、全体を見れない子供なんで(´;ω;`)

時間は掃いて捨てるほど存在しない

そして、転職や移動なども考えた一年でした。31歳になって、自分のやりたいことってなんだっけ?と、考えても何がしたいのかわからない自分がいました。反省です。プログラマーになりたかった小学生の頃の自分、今やている仕事はSIerということですが、自分の思っているプログラマーの仕事とは程遠く、でもお客様がいて、間違いがあってはいけないから正しいことをするために自分の時間を浪費する。そんな感覚ですね。だからこと一生懸命にもがいて走り続けても、会社での成果しかないと。お客様に喜んでいただけることはあっても、会社から評価されないのはアンバランスでしたね。Fワードが出てきてしまいそうになります。

そんな中で、現在は在宅中心の仕事になって、読書や筋トレなどの時間が確保できています。とても良い傾向です。開発がしたいと言っても、いろいろなニュアンスがありしっかり説明できていなかったので、私は次のような分類で勉強し始めています(まだまだビギナーから抜け出せていません)。カッコ内はそのためにしていること。

  • アルゴリズム競技プログラミング
    • 計算量の部分ですね。考えなくてもいい時はありますが、リソースが有効に使えたり時間が早くなるので大切になるときがあります。
  • セキュリティ(CTF)
    • コンピュータを利用して仕事をするのに切っては切り離せないものですね。セキュリティがざるでは信用問題です。ゲームのように楽しみながらやっていきます。基礎というか、(業務じゃ全く触れられないような)大前提の知識だったりするので見過ごせません。
  • 機械学習(Kaggleなどのコンテスト)
    • 少し飛びつくのが遅れましたがキャッチーな奴です。まだまだ、本を読んで、初心者コンテストに出たくらいなので、少しずつ成長します。
  • その他知識(IPAなど資格試験)
    • コンピュータサイエンスの基本的な知識ももっとつけたいですね。IPAの試験は系統的に学ぶことができるので、ちゃんとやります←。
  • サービス作成(言語、フレームワークチュートリアル
    • アプリ作成やビジネスなど漠然と憧れるところ。ですが、何をしていいのかわからないし、何から手を付けていいのかわからなかったところ。今は、ひたすらに言語やサービスにチュートリアルを試すことにしています。全然時間とれてないけど…。

気が付いたのは、まだまだ勉強が足りていないということと、ITという分野は好きで、これから先もずっと仕事にしていくのだろうなということ。ただし、しこたま残業はあるので、その穴埋めのためにアニメを見たり、ぼーっとしてしまうので、ライフワークバランスを直したいと考えています。

VScodeの環境整備でWSLのパスワード忘れてて笑った話

AtCoderでローカルではコンパイルできたのに、提出したらCE(コンパイルエラー)になった。 AtCoder用の環境を整理してて、ローカル環境のパスワードとかを忘れてしまったので、対処メモ。

TL;DR

  • 開発環境:Windows10、VScode、WSLインストール済み
  • 何が起きた:WSLでアプリをインストールしようとしたらパスワード忘れて詰まった
  • 何をした:WSLでパスワードリセットした
  • 残り物:あれ?ローカルだと普通にコンパイルできるんですけど。。。ちょっと難しい算術演算ができない?

環境構築

AtCoderでプログラミングを勉強中だが、よく考えたらVScodeの使い方とかちゃんと調べてなかったので、調べたら、、、パスワードが分からなくなってて詰んだ(笑)

【VScode+WSLで始める】競プロ用C++デバッグ環境構築 - Qiita

AtCoderコンパイルオプションとか重要ですよね。

WSLのパスワードリセット

ということで、はい、こちらで簡単にできましたね。

WSLでLinuxのパスワードを忘れてしまった場合の対処法 | LFI

  1. ログインユーザーをrootにする(パスワードなしで入れる)
  2. ubuntu1804を起動。rootでログインできたことを確認
  3. 一般ユーザのパスワードを変更する
    • 今回はnakamurkを変更
      root@DESKTOP-MIE219J:~# passwd nakamurk
      Enter new UNIX password:
      Retype new UNIX password:
      passwd: password updated successfully
      
  4. 安全のためログインユーザを一般ユーザ(私の場合はnakamurk)に戻す

この節は以上

略語

「あしたの家族のつくり方」を観て

2020年3月8日、Gyao!にて鑑賞。日本生まれ、日本育ちで、アメリカの文化にも疎い私が感じたのは、なんというか、似て非なる高校生生活ということでした。イースターの文化、ホームパーティー、教会で育つ。どれも、ぴんとは来ないし、国家や国境というものについても、価値観が大分違うと感じました。

あるべき姿と閉塞感

邦訳はどことなく、もったりしている印象ですが、原題は「As Cool as I Am」ですたぶん。オープニングにでかでかと出てました。英語できないけど、たぶん直訳すれば「私の思うように生きるって素晴らしい」と言う意味ではないかと思いまう。作中も、それぞれの葛藤と衝突。そして、自分らしく生きようというのが主題にあったように思います。どこか、主人公の親世代が型にはまってしまい、自分らしさと言う型に自身を押し込めて生活をする毎日。ストレスを見ないふりして頑張ったけど、何か歯車が狂うと、途端に押し込めていたはずの感情が爆発して、生活がうまくいかなくなてしまう。でも、どうしようもない…。子供にも、それを当てはめようとします。

しかし、主人公とその同級生たちは、閉塞感ではなく、自分の中の正義と不安、そして若さゆえの過ちもありながら、柔軟に大人たちと対話している姿が、描かれていたように思います。もちろん明らかな過ちや、虚栄ともいえる対応もありましたが、それでも、今を生きている感じがして勇気づけられます。高校生の姿に、30のナイスミドルであるはずの私が(笑)。また、少し生々しい表現があったりで、夕飯時には家族で見れません!

大人はどことなく汚いですね。押しつけもあるし、歪んだままな気がする。料理関係の人と病院の人くらいじゃないですかね、この映画でまともな大人。子供たちのためになる大人ってやつは。好きなように生きることは、確かに自己責任で歩いていかなければならないと思いますが、それは決して、誰かを踏み付けていくこととは違うと、私は思います。

お求めはこちら

90分くらいなので、サクッとみられるかと思います!2020年3月15日(日) 23:59までは #GYAOで!それ以降はAmazonで!

時間のかかるコマンドの終了を見逃さないためにすること

twitterを眺めていた時に、Dockerの終了のタイミングが分からないんだよね。。。と言うのを見つけて、解決方法をサクッと調べてみました。組み合わせたのは次の機能です。私はBashが好きなので、アイディアはパッと思いつけました!Beerの方ではなく、Shellの方です(笑)

解決案はこちら。これで、DOCKER(などの時間のかかるコマンド)を実行後にlocalhostに対して、hogeと言う文字列が書かれた、メッセージボックスを出力させることができます!

prompt> DOCKER & msg * /server:localhost hoge

安直にはtimeoutを使って、タイマーなんかも作れますね。例えば、一時間でhogeと出力させるにはこちら

prompt> timeout 3600 & msg * /server:localhost hoge

勉強会に参加してみた(2020/01/16)

仕事終わり「みんなのPython勉強会#53 - connpass」に参加してきました。Pythonjsonをパースするモジュールで一行のコマンドくらいでしか触ったことないんですけどね^_^;。

雰囲気

若い方から少しお年を召された方まで色々で、男女比は安定の男性過多…言語にもよるのでしょうか?若手だと転職組やこれから!という意気込みの方が多い気がしました。お年を召された方々は、仕事で使ってますって方が多い印象でした。懇親会もワイワイやっていましたし、参加することに関してのハードルは低いかなと思います。

スピーカーの方々

メインのセッションに登壇された方々は「伝えたいもの」をもってらっしゃるというのがまず凄いなと感じました。私もいつか、誰かのために伝えることをしてみたい。と言うことで、LTから始めてみようかな、と昨日勝手にTwitterで宣言してました。

資料も作り込まれてますし、何より感じたのが「勉強している!」と言うことでした。本も沢山読んでるし、成果物でアウトプットも出してるし、本の執筆や話者としてもアウトプットも出している。そりゃ、今の立場にいますよ。私もインプットして、アウトプットしていかなければなと感じました。

ちゃんと懇親会にも参加して、ビールを嗜んだのですが、LTも開催されていて、お酒も入っているし、みんな話をしてるし、と集中してくれない環境で、メンタルをやられずによく話ができるな!と感じました。特に先ほどの宣言は、この時、思ったことですね。

いつまでも初心者として

メインに戻しまして、話者の方々は本当に勉強しているな、と感じましたが、おこがましくも今の私と比較すると、「軸があるな」というのと「評価の尺度をお持ちだな」と言うのが違いとして感じました。もう少し書くと「軸に対して座標が打てる」という感じですね。伝わるのかこの言い方?「今、私はここにいます」と説明できる感じ!

それに対して、いつまでも技術やその傾向を追いかけていく姿は私も同じなのかなと、安心しました。初心者といての気持ちを持っておられるようですが「それ、強くてニューゲームでしょ!」って感じですね(笑)

2020年、元号は令和。時代のせいで、環境が整備され過ぎていて、フロンティア精神というものは培い辛いですが、ハングリー精神で突き進みたいと思います!

映画「カンパニーメン」(2019/11/30, Gyao!にて)

早いもので、今年も11月を終わろうとしています。来月30歳になるということで、これまでと違うことをしようと画策した11月。やらなきゃ良かった(笑)。これまでの人生の選択は、あながち間違っていなかったことが分かりましたが、そうでない世界が見えたのもまた一つ意味があったように思います。

さて、久しぶりに映画を観ました。最近の映画だと思いますが、現代の日本人的感覚で言えば「社畜」になってしますのでしょうか。いえ、そんなことありません。いうなれば「働くとは何か?」と言う感じでしょうか。

感想

主人公は結婚して子供がいて、家を持っていて、と今の私とは状況が違うので感情移入はできませんでしたが、感じるところは多々ありました。両親の様子に心乱れる息子の様子や、家庭をもってから職を失い実家に厄介になるところなどはそのようなものなのかと思いました。それから、人間って見栄っ張りなんですよね。職を失ったことをご近所さんに気が付かれたくないので、朝はびしっとして家を出て、夜まで帰ってくるなって。。。つらい現実です。

会社員と私

会社員として働く以上、会社に尽くすというイメージを持っていたのですが、少し印象が違いました。アメリカの話なのですが、「私はこれだけの給料を払う価値がある」というような自分自身の評価とそれを会社が認めて払うという構図です。だからこそ、払う価値があると思っている自分にとって、それが認められないのが、不安やうつの原因になるのではないでしょうか。日本人的には、そういうようなタフな交渉をしていない印象です。というか、私自身そんな自信はなかったですね。そう「なかった」です。今は、自分の仕事量は自己評価できるので、何とか精神を病むことはないですが、これまではそれができておらず、剥げてきましたね(笑)。話は変わりますが、この前中学の友人と飲みに行って、隣で飲んでいた女性二人が「安倍総理はすごい。だって、あれだけストレスがかかる仕事しているのに、剥げないんだもん。毛根が強い!」なんて話をしていました。私は総理向きではないようです。I'm sorry(笑)。

何か手伝う?

定時後、みんなが返った職場で、女の人が上司に対して「何か手伝うことはありますか?」なんて質問していました。上司は、大丈夫だよと言って女性を返していましたが、こういうやり取りが人間的な会話だと思います。私の仕事、あなたの仕事、その垣根を越えて共通する目標のために仕事をするのが良いのではないでしょうか。もちろん、金もうけが必要ですから、株式を売り切ったもん勝ちなのですが、人間的な結びつきがない関係なんて、VRで十分だと思います。おそらく、VRなどは人間的な結びつきを攻めてくるでしょうから、現実世界で得られない人間的な結びつきをVRの世界に求めていくのが将来の荒廃した世界ではないでしょうか。。。

社員よりも株主に責任がある

そうなんです。株式会社の使命は社員の幸せではなく、株主の儲けです。いまでは、小口でも株主になれますとか言っていますが、そういう小口の人は基本的には搾取される側の人ですから、大多数の株を持っている少数の株主を幸せにするために私たちは働いていると思うと、むなしくなってしまいますね。今の私の気持ちは、「お金なんて人生に必要ない」的な崇高な感じのする考えではなく、「お金に困らない人生にするために準備する」ですな。頭の回路をシフトしたので、本気で稼いでいこうと思います!さてどうやろう。

話を戻して、株主に責任があるとかおっしゃる社長、正しいかもしれませんが、社員の顔は歯車に見えていることでしょう。おそらく家族の顔も、立派なスーツやかっこいい車と同じように見えているのではないでしょうか。お金なんてと同じような思想ですが、兌換紙幣をいくら積み上げたって、あなたの人生なんてそこまで素晴らしいのでしょうか?と枕もとでつぶやいてあげたくなりますね。「あなたの葬式には誰も来ませんよ」と。

see, smell, touch

見て、香って、触れて。仕事について夢を語る場面で出てきた表現でした。日本語字幕にはsmellの部分がなかったように思いますが、まさに、生きている、働いている感じが出ていますね。どれだけIT化が進み、キャッシュレスが浸透しても、私は現金派ですね。もちろん使わないこともないのですが。。。最近分かったのは、1か月の給料分であれば、自由に使えると考えている節があるようです。後輩を引き連れて飲みに行っても、馬鹿なことをしても、お祝いとして渡しても、給料以内であれば心にしこりなく渡せる自分がいました。でも、学生時代アルバイト代を茶封筒に包んでもらった日はドキドキしながら帰ったのを今でも覚えています。それくらい、現金と言うのは強力だと思っています。キャッシュレスは便利ですが味気ない。

お求めはこちら

働き方改革などどうせ誰かが儲けたいがための仕組みだと思うので、それに巻き込まれないように考えていこうと心に決めました。こちらは、末期の世界が見れる良い作品と思います!