おはやし日記

テーマ……バイク←プログラミング←旅

AtCoder ABC167【3完】

こんにちは。

↑これは昨日の僕。今日が当日です。

今回はAからCまで、1発ACでした。Dは時間的に無理だったし細かい実装もわからんので諦めた

A

atcoder.jp

提出

AC

#include <bits/stdc++.h>
using namespace std;
int main(){
  string s, t;
  cin>>s>>t;
  int l = s.size();

  for(int i=0; i<l; i++){
    if(s[i]!=t[i]){
      cout<<"No\n";
      return 0;
    }
  }
  cout<<"Yes\n";
  return 0;
}

最初、sとtが1文字違い、というのを判定しようとしていたがそもそも制約で一文字違いだと書いてあった。

最後の1文字はどうでもいいので短い方(s)の文字数だけ、それぞれが一致しているか確認するだけ。

依然文字列の比較を一文字ずつやりがち。Lの最後を削ってif(s==t)にしても良かったと思う。

↑できた。 ACしかも、さっきは実行時間6msだったのが、こっちは2msになった

#include <bits/stdc++.h>
using namespace std;
int main(){
  string s, t;
  cin>>s>>t;

  t.erase(t.end()-1);

  cout<<( s==t ? "Yes\n" : "No\n" );
  return 0;
}

B

atcoder.jp

提出

AC

#include <bits/stdc++.h>
using namespace std;
int main(){
  long long A, B, C, K;
  cin>>A>>B>>C>>K;
  if(K<=A){
    cout<<K<<endl;
    return 0;
  }else if(K<=A+B){
    cout<<A<<endl;
    return 0;
  }else{
    cout<< (A- (K-A-B) )<<endl;
    return 0;
  }
}

1のカードから取っていくのが最適なので、K枚でどこまで拾えるかを場合分けにした。

C

atcoder.jp

提出

AC

Submission #13070119 - AtCoder Beginner Contest 167

日中に、bit全探索なる手法を見ていたので、bit全探索の神の声が聴こえた。

C - HonestOrUnkind2

この問題がわからんくて、解説を探したりしていたら「bit全探索」と書いてあった。

今回も、N,Mが12以下なので、各参考書の買う/買わないをbitにして探索しても間に合うと思い、なんとか実装。

最初、Xを読み込むのを忘れていてなかなかテストがうまくいかなくて悩んだw

個人的に良かったところ

  • int CA[15][15] = {};
    CとAを分けて読み込んでいたが、こんがらがるし意味がないのでまとめたらスッキリした

  • lastans = *min_element(ans.begin(), ans.end());
    理解度の分岐を通過した(理解度を全てX以上にできる買い方の)金額で最小のものを選びたかったわけだが、ans = min(ans, CA_sum[0])としていたら最初にansを超大きい値にしておかないといけないのでは?と思ったので、とりあえず全部候補に突っ込んで後で最小のものを選ぶことにした。
    min関数にvector<int>ansを突っ込もうとしたが、なんかダメっぽいので検索したらmin_element関数に出会った。
    これは、配列の渡した範囲で最小の要素のイテレータを返すので、*をつけて答えを引っ張り出した。

振り返り

今回はCまで解けて良かった。えらい!

おしまい。

Automateについて書いた方がええんか

なんか、このブログ初めて初期にAutomateというAndroidアプリについてちょっと書いてたんですけど、アクセス解析を見るとgoogle検索に「Automate」だとかなんとか入れてここにたどり着いている人が多いらしく…………

f:id:o-treetree:20200508164631p:plain

試しに検索してみたら公式の次に2番目くらいででてきてたまげた。

それならもうちょっと真面目に書いた方がええんかなぁって思っている

Automateとは、Android用の自動化アプリです。

llamalab.com

様々な命令を入れたボックスをつないで簡易的なアプリケーション的なサムシングを作ることができます。

タイマーとか、自動でタップするとか、クリップボード操作とか、HTTPリクエストもできます。

検索で見つけてくれるひとがいるんなら、もうちょい書いた方がええかなぁって

どうせ暇なので。

おしまい。

ナンプレ攻略プログラムがWebで使えるようになりました

o-treetree.hatenablog.com

1ヶ月ほど前にこれ↑が完成しました。

C言語で、(大抵の)ナンプレを解いてくれるプログラムです。

これをJavaScriptに書き換えて、Web上で使えるようにしました!

oha-yashi web test

↑こちらから。

特に機能に変わりはないですが、ボタン一発で解答できるようになったのはでかいですね

別に使い方は見ればわかると思うので、C→JSの移植で大変だったところをメモする。

本題は終了。

ちょっとまともなところがある。初歩の初歩の話だが

変更点

データの取り扱い、メソッド化

hoge.fuga()みたいなやつできればいいなぁってなったのでクラスを使ってみた

Cでは

typedef unsigned short np;

だったのをJSでは

class np{
    /** @param {Number} d */
    constructor(d){
        this.d = d;
    }

にしてみた。

calc.hの

#define NUM(d) ((d)>>12)
#define set_num(d, i) d = d & 0x0fff | (i<<12)
#define BLOCK(n) (LINE(n)/3*3 + ROW(n)/3)

をJSで

class np{
  NUM(){ return this.d>>12 }
  set_num(i){ this.d = this.d & 0x0fff | (i<<12) }
}
function BLOCK(n){return Math.floor(LINE(n)/3)*3 + Math.floor(ROW(n)/3)}

としたり。

そんなにいいことはなかった。書き換えがめんどくなった。

set_num(data[n], i)data[n].set_num(i)になったのでその辺をまるっと修正する必要があった。

あとは、整数÷整数がCのような切り捨てではなくJSだとご丁寧に小数にしてくれるのでMath.floorをかまさなければいけなかった。

データのみを扱う操作くらいしかメソッドにできない割にあとでめんどくさくなった

関数の書き換え

functionの引数に型を明示しなくていいのは楽だと思った

    /** @c NUM(data[n]) @js data[n].NUM() */
    NUM(){ return this.d>>12 }
    /** @c FLAG(data[n], i) @js data[n].FLAG(i) */
    FLAG(i){ return this.d>>i & 1 }

↑この辺の書き換えが面倒だった

read_and_delete_lrb

//@c
void read_delete_lrb(int start, int kouho, int byA, int byB, int byC, char c){
    int sum[3] = {}; int keep[3] = {};
    int i, j, k, roop, sum_all, cont;

//中略 keepに3つ数字が入る

    for(i=0; i<3; i++)for(j=0; j<3; j++){
        roop = start + i*byB + j*byC;

        for(k=0; k<3; k++){
            if(roop == keep[k]) goto NEXT;
        }
        flag_off(data[roop], kouho);
        NEXT:;
    }
}
//@js現行ver.
function read_delete_lrb(start, kouho, byA, byB, byC, c){
    var sum = [3]; var keep = [3];//←改めてみたら変だったので後で直した
    var i, j, roop, sum_all, cont;

//中略 keepに3つ数字が入る
    
    for(i=0; i<3; i++)for(j=0; j<3; j++){
        roop = start + i*byB + j*byC;

        if(roop===keep[0] || roop===keep[1] || roop===keep[2]){
            //何もしない
        }else{
            data[roop].flag_off(kouho);
        }
    }
}

roopはkeepのどれかに一つのみに一致するか、あるいはどれにも一致しない。

最初cの形をそのままjsに書き換えたらおかしくなった。gotoから↓みたいなcontinueにしたんだが

cの方自体は問題なく動作していたはずなのだが…………わからん

もう一回書き直してみたらちゃんと動作した。まあ現行の方が条件がわかりやすいな

//@js書き直し
//前略

    NEXT:
    for(i=0; i<3; i++)for(j=0; j<3; j++){
        roop = start + i*byB + j*byC;

       for(var k=0; k<3; k++){
           if(roop===keep[k]){
               continue NEXT;
           }
       }
       data[roop].flag_off(kouho);
    }
}

only_two_pair_lrb

//@c
void only_two_pair_lrb(int start, int byA, int byB){
    int i, j, k, l, roop, cnt;
    int q_k[10] = {};
    for(k=1;k<=9;k++){
        for(i=0;i<3;i++)for(j=0;j<3;j++){
            roop = start + i*byA + j*byB;
            if(FLAG(data[roop], k))q_k[k]++;
        }
    }
    int pair_k_in[10][2] = {};
    
    for(k=1; k<=9; k++){
        cnt = 0;
        if(q_k[k] == 2){
            for(i=0;i<3;i++)for(j=0;j<3;j++){
                roop = start + i*byA + j*byB;
                if(FLAG(data[roop], k)){
                    pair_k_in[k][cnt] = roop;
                    cnt++;
                }
            }
        }
    }
    //ブロック内で2箇所のみkが入るマスがpair_k_in[k][2]に入った
    for(k=1; k<=8; k++){//k<=8で正しい
        if(q_k[k] == 2){
            for(l=k+1; l<=9; l++){
                if(pair_k_in[k][0] == pair_k_in[l][0]
                && pair_k_in[k][1] == pair_k_in[l][1]){
                    //pairの組が一致したらそこでkとlが独占
                    data[ pair_k_in[k][0] ] = data[ pair_k_in[k][1] ] = 0x0;
                    data[ pair_k_in[k][0] ] = data[ pair_k_in[k][1] ] |= 1<<k;
                    data[ pair_k_in[k][0] ] = data[ pair_k_in[k][1] ] |= 1<<l;
                    //フラグ立てをkとlのみにする
                }
            }
        }
    }
}
//@js
function only_two_pair_lrb(start, byA, byB){
    var i, j, k, l, roop, cnt;
    var q_k = new Array(10).fill(0);//0で初期化
    for(k=1;k<=9;k++){
        for(i=0;i<3;i++)for(j=0;j<3;j++){
            roop = start + i*byA + j*byB;
            if(data[roop].FLAG(k))q_k[k]++;
        }
    }

    var pair_k_in = Array2Dnull(10, 2);
    
    for(k=1; k<=9; k++){
        cnt = 0;
        if(q_k[k] == 2){
            for(i=0;i<3;i++)for(j=0;j<3;j++){
                roop = start + i*byA + j*byB;
                if(data[roop].FLAG(k)){
                    pair_k_in[k][cnt] = roop;
                    cnt++;
                }
            }
        }
    }
    //ブロック内で2箇所のみkが入るマスがpair_k_in[k][2]に入った
    for(k=1; k<=8; k++){//k<=8で正しい
        if(q_k[k] == 2){
            for(l=k+1; l<=9; l++){
                if(pair_k_in[k][0] == pair_k_in[l][0]
                && pair_k_in[k][1] == pair_k_in[l][1]){
                    //pairの組が一致したらそこでkとlが独占
                    data[ pair_k_in[k][0] ].d = data[ pair_k_in[k][1] ].d  = 0x0;
                    data[ pair_k_in[k][0] ].d = data[ pair_k_in[k][1] ].d |= 1<<k;
                    data[ pair_k_in[k][0] ].d = data[ pair_k_in[k][1] ].d |= 1<<l;
                    //フラグ立てをkとlのみにする
                }
            }
        }
    }
}
罠にはまるその1
//@c
int a[10] = {};
for(int i=0; i<10; i++){
 a[i]++; 
}

これ(概略)をJSにしようとして最初こうやった

//@js
var a = new Array(10);
for (i=0; i<10; i++){
 a[i]++; 
}

失敗。ここでaは空白の配列なので元々a[i] = undefined。インクリメントできずNaNになる

//ブラウザコンソール
> var a = new Array(10);
for (i=0; i<10; i++){
 a[i]++; 
}
< NaN
> a
< [NaN, NaN, NaN, NaN, NaN, NaN, NaN, NaN, NaN, NaN] (10)

こうすれば良かった

var a = [0,0,0,0,0,0,0,0,0,0];
for (i=0; i<10; i++){
 a[i]++; 
}
//ブラウザコンソール
> var a = [0,0,0,0,0,0,0,0,0,0];
for (i=0; i<10; i++){
 a[i]++; 
}
< 0
> a
< [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] (10)

でもカッコよくないのでこうした

var a = new Array(10).fill(0);
for (i=0; i<10; i++){
 a[i]++; 
}
//ブラウザコンソール
> var a = new Array(10).fill(0);
for (i=0; i<10; i++){
 a[i]++; 
}
< 0
> a
< [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] (10)
罠にはまるその2(?)

多次元配列がJavaScriptには無い(?)のでつくらんといけない、ということで

function Array2Dnull(p, q){
    var a = new Array(p);
    for(var i=0; i<p; i++){
        a[i] = new Array(q);
    }
    return a;
}

var a = Array2Dnull(10, 2);
罠にはまるその3(?)

Cの時data[n]自体をビット演算できた(ただの整数型なので)けどJSだとdata[n].dにしなければいけなかった

まあこれは単に面倒だったという話。

HTMLを使う利点

マス目をinputで作る

jQueryは便利ですね。

/** <input>を入れる配列 */
var masus = [];
/** viewFieldに9*9マスを描画する */
function printMasu(){
    for(var i=0; i<9; i++){
        newRow = $("<div>").appendTo(viewField);
        for(var j=0; j<9; j++){
            roop = i*9 + j;
            masus[roop] = $("<input>").attr({
                type:"text", id:"box"+roop, maxLength:1
            }).css({
                borderStyle       : "solid",
                borderColor       : "black", 
                borderTopWidth    : i%3===0 ? "medium" : "thin",
                borderBottomWidth : i%3===2 ? "medium" : "thin",
                borderLeftWidth   : j%3===0 ? "medium" : "thin",
                borderRightWidth  : j%3===2 ? "medium" : "thin"
            }).val(
                data[roop].NUM()===0 ? "" : data[roop].NUM()
            ).appendTo(newRow);
        }
    }
}

iのループで縦9行の、9列inputを並べるためのdiv要素newRowを作る。サイズとかはCSSで整える。

jのループではroop=i*9+jについて

masu[roop]に対して、input要素を作って、typeとidを決めてmaxLengthを指定し、cssをマスの位置によって設定し、dataによってvalueを放り込み、newRowの末尾につける

これが一文でできるとは。

css設定のborderStyleとborderColor、cssファイルに書いてみたら適用されませんでした。CSS読み込んだ後にinputを生成したからなんですかね…………CSSの同じ場所に書いたwidthとかheightは適用されてるのに…………謎。

マスに入れた数字をデータに読み込んで、処理して、マスに反映させるというのが大きな流れですねぇ

ボタンが作れる

ボタンのclickイベントに関数を結びつけることでチェックが楽になった

よかったね。

おしまい。

ABC165, 166反省会

ABC165

ダメでした

A

A - We Love Golf

提出

AC

#include <stdio.h>
int main(){
  int K, A, B;
  scanf("%d%d%d",&K,&A,&B);
  int bl = 0;
  for(int i=A; i<=B; i++){
    if((i%K)==0)bl++;
  }
  if(bl){
    printf("OK\n");
  }else{
    printf("NG\n");
  }
}

B

B - 1%

提出

long long型を使えば良かったのにintにしていて(下の変数yokin)オーバーフローし、提出してみる前に諦めてしまった

遅れてAC

#include <stdio.h>
int main(){
  long long X;scanf("%lld",&X);
  int year = 0;
  long long yokin = 100;
  while(yokin<X){
    yokin += yokin/100;
    year++;
  }
  printf("%d\n", year);
  return 0;
}

C

C - Many Requirements

わがんね。おしまい。

Eテレでアニメ「君の膵臓をたべたい」をやっていたので観ました。

ABC166

今日こそは頑張ろうと思いました。

A

A - A?C

提出

AC

#include <stdio.h>
int main(){
  char s[100] = {};
  scanf("%s", s);
  if(s[1]=='B'){
    printf("ARC\n");
  }else {
    printf("ABC\n");
  }
}

文字を丸ごとstrcmpで比較しようかと思ったんだけど# include <string.h>やるのめんどかったので2文字目だけを判定しました

B

B - Trick or Treat

提出

1ミスの後AC

#include <stdio.h>
int main(){
  int N, K;
  int d, buf;
  scanf("%d%d", &N,&K);
  int sunuke_kasi[110] = {};
  for(int i=0; i<K; i++){
    //お菓子ごとに
    scanf("%d", &d);
    for(int j=0; j<d; j++){
      scanf("%d", &buf);
      sunuke_kasi[buf]++;
    }
  }

  int count = 0;
  for(int i=1; i<=N; i++){
    if(sunuke_kasi[i] == 0)count++;
  }

  printf("%d\n", count);
}

C

C - Peaks

提出

最初C言語でやった。論理的にはあってるはずだけどなんかよくわからんエラーを吐いた。

WA Submission #12764426 - AtCoder Beginner Contest 166

c++に切り替えてsetを使って実装

AC Submission #12769712 - AtCoder Beginner Contest 166

c++は触ってはいたけど、実戦でいきなりsetの配列を使えたのはえらい!!!

D

数学かと思ったら、ちゃんと範囲を絞り込めば全探索できたのか…………

おしまい。

黒岩知事の緊急速報に苦言を呈しているやつはバカ

今朝10時ころ、神奈川県の黒岩知事からエリアメールが届きました

母親のスマホには来て、僕のには来ませんでしたが、これはまあ設定とか対応してるかの話でしょう。論点ではありません。

で、少々びっくりしたのは事実ですが、なんだかこのエリアメールを批判している人がいて訳ワカンねぇなぁて思ったので。

適当に検索して、ツイート埋め込みで引っ張ってきて適当にコメントをします。ツイート埋め込みは著作権侵害とかには当たらないので。念の為。

心臓に悪い

緊急速報なんだから心臓に悪いアラーム音で気づいてもらわんといけないでしょう。

緊急地震速報がトラウマ

トラウマになってて良かったですね。おかげでこの後災害が起きた時もすぐに緊急速報に気付けますね。

散々言われてる

散々言っても来るバカがおるからエリアメールだしてんだろうが。バカはどっちだ

時間

これは別に晒すほどでもないけど

夜に流したらそれこそ「夜中にうるさい!」とキレるのがオチ。

県民に言うことか

県民はそのまま家にいろ。県外から来るやつは帰れってことじゃん

ニュースで三浦に釣りしにきている県外ナンバーのニュースやってたけど、あいつらの釣竿全部折ってタイヤパンクさせてやりテェなって思ってました。

おわり

10時の発報から時間が経ってるのでキチツイ探すのめんどくなってるし、バカなツイート検索したらイライラしてくるし、「エリアメール出すのも当然じゃん」みたいなのが多くなっててうんうんそうだね ^ - ^ ってなったのでおしまい。

ねとらぼが早かった。流石。

STAY HOME。おしまい。

makefileを利用して簡単にmac,VSCodeでbits/stdc++.hを使う

こんにちは。

競プロではC++が強いそうですね。

C++ではインクルードファイルとして

#include <iostream> //入出力
#include <string> //文字列
#include <vector> //配列
...

等々書くそうですが、面倒なのでAtCoderでは<bits/stdc++.h>を使うと良い、という話になっています。

これは、gccに付属する、諸々のインクルードファイルを一気に読み込むためのファイルだそうです。つまり

#include <bits/stdc++.h>

とかけば済むということです。

しかし、macでは使えないそうです(参考文献参照)。

これを、makefileを活用して楽に使えるようにしてみました。

ファイル構造

abc150/a.cppコンパイルしてみたいと思います。

@AtCoder
|
|-- abc150
|   |-- a.cpp
|
|-- bits
|   |-- stdc++.h
|
|-- makefile

abc150-a

ちなみに上のa.cppはA - 500 Yen CoinsにACで通過します(それはそう)。

コンパイルしてみる

(環境について何をかけば良いのかあんまりわかってないので不十分かも。ごめんなさい)

普通にコンパイルすると

$ cd .../@AtCoder
$ c++ abc150/a.cpp

abc150/a.cpp:1:10: fatal error: 'bits/stdc++.h' file not found
#include <bits/stdc++.h>
         ^~~~~~~~~~~~~~~
1 error generated.

怒られた。元々のインクルードパスにbits/stdc++.hが無いですよ、ということ。

bits/stdc++.hの準備

ここ↓にあります

libstdc++: stdc++.h Source File

これをコピペして@AtCoder/bits/stdc++.hに保存します。(行番号もコピーしてしまうので頑張って消した)

参考文献にあるように、コンパイル時にインクルードパスを指定してコンパイルすれば良いので

$ c++ -I /Users/.../@AtCoder abc150/a.cpp

これで一応はコンパイルできます。

簡単にする

毎回インクルードパスを書くのは面倒なのでmakefileを作ってそこに書いておきましょう。

ということで、冒頭にも置きましたが

# .../@AtCoder/makefile
%: %.cpp
    c++ -I /Users/.../@AtCoder $< -o $@

これだけ。ちなみに2行目の頭の空白は、スペースではなく「タブ」でなくてはいけません。

それでもって

$ make abc150/a

コンパイル(拡張子.cppをつけないことに注意)。実行は

$ abc150/a

です。

おまけ-Cのファイルとの共存

もともとabc150/a.cがあった場合、今まではmake abc150/aコンパイルできたのが、makefileの変更によってmake abc150/aではc++のファイルがコンパイルされてしまいます。

makefileを改良して

%pp: %pp.cpp
    c++ -I /Users/.../@AtCoder $< -o $@

とし、c++のファイルはapp.cpp, bpp.cppのようにファイル名の方にもppをつけてやるとa.c, b.cとの共存が図れます。

まあ、cをコンパイルするときは先に移動しておけば良いんですけどね

$ cd abc150
$ make a (a.cコンパイル)
$ ./a (実行)

参考文献

Qiitaにも書いてみました

makefileを利用して簡単にmac,VSCodeでbits/stdc++.hを使う - Qiita

ABC164【A, B完】

ABC164でした。

atcoder.jp

今回はダメだった。

生活リズムガバガバすぎて18時頃にはクソ眠かった

20:40にアラームかけて寝落ちしたけど起きるのに時間かかったりしたので30分ほど遅刻してスタート

A

atcoder.jp

提出

AC Submission #12371389 - AtCoder Beginner Contest 164

#include <stdio.h>

int main(){
    int S, W;
    scanf("%d%d", &S, &W);
    printf("%s\n", (S>W)?"safe":"unsafe");
    return 0;
}

三項演算子を使った。かっこいい(?)。

B

atcoder.jp

提出

AC Submission #12373798 - AtCoder Beginner Contest 164

#include <stdio.h>

int main(){
    int A,B,C,D;
    scanf("%d%d%d%d",&A,&B,&C,&D);
    while(1){
        C -= B;
        if(C<=0){
            printf("Yes\n");
            return 0;
        }
        A -= D;
        if(A<=0){
            printf("No\n");
            return 0;
        }
    }
    return 0;
}

素直なコード(?)。

C

提出

WA Submission #12381623 - AtCoder Beginner Contest 164

う〜〜〜ん、何が悪いんかわからん。入力例のは通ったし考え的には合ってると思うのだが……

てかテストケースも最後の二つ以外通ってるしなぁ…………

ここでやる気が尽き、D問題もぱっと見手に負えないので断念。

さいなら。

セットが使えればよかったんだけどCはない(はず)だしな…………

解説(https://img.atcoder.jp/abc164/editorial.pdf)でも

文字列を辞書順などでソートしてから重複を確認したり

とあるので悪い方針ではなかったのだが

反省

他の人の解答Submission #12399739 - AtCoder Beginner Contest 164が役に立ちそうだ

何が違うかと言うと、比較関数のところだ

自分は、qsortの比較関数を知った時にやってたint用の処理をそのまま書いてしまっていた。多分これが何か悪さをしていたのだ

int compar(const int *val1, const int *val2) {
    if ( *val1 < *val2 ) {
        return -1;
    } else if ( *val1 == * val2 ) {
        return 0;
    } else {
        return 1;
    }
}

......

qsort(S, N, sizeof(char)*20,
    (int (*)(const void *, const void *))compar
);

今回は「文字列」を比較するので比較関数を書き直さなければいけない

  • 再提出

AC https://atcoder.jp/contests/abc164/submissions/12400852

な〜〜〜〜〜るほど完全に理解した(怪しい)。

int compar(const char *a, const char *b){
    return strcmp(a, b);
}

......

qsort(S, N, sizeof(char)*20,compar);

qsortに関数をぶち込む時名前だけ書けば良いことも知った。

ただ、なんか調べるに、比較関数の引数はconst void*にしておいて比較関数の中でキャストすべきらしい。

そこんところちょっと確認しておこう。

おしまい。

プライバシーポリシー ・お問い合わせはこちら