textareaの高さを自動調整する仕組みをNuxt.jsアプリに実装してみる

入力されているテキストの行数に応じて、textareaの高さが自動調整される仕組みです。改行を入力したり折り返しが発生するたびにリアルタイムに高さが変化します。

CSSだけで高さ調整をしており、JavaScriptはほとんど使いません。

HTMLソースは以下の通りです。

<template>
  <div class="flexible-textarea-wrapper">
    <!-- 次の行の `{ { message + "\n" } }` の記述の前後で改行してはいけない -->
    <div id="flexible-textarea">{{message + "\n"}}<textarea v-model="message"></textarea></div>
  </div>
</template>

ポイント

  • textareaの高さをCSSで100%にし、その外側のdivと同じ高さにする
  • textareaで編集中のテキストを、その外側のdivにもそのままテキストで表示する
  • divのテキストはdivの高さを自動調整する働きを持つが、同じ大きさのtextareaで上から隠され、textareaのみが見える状態とする

message はdataで与えておきます。

<script>
export default {
  data() {
    return {
      message: "Hello, World!",
    };
  },
}
</script>

CSSは以下のようにします。

<style>
/* これは高さ自動調整にとって重要ではない */
.flexible-textarea-wrapper {
  margin-left: auto;
  margin-right: auto;
  width: 400px;
}

/* ここからが高さ自動調整に必要 */
#flexible-textarea {
  position: relative;
  width: 100%;
  min-height: 32px;
  box-sizing: border-box;
  border: 0;
  padding: 5px; /* 下のtextareaのborder+paddingと同じ幅にする */
  text-align: left;
  white-space: pre-wrap; /* 改行や連続した空白を表示に反映 */
  font-size: 16px;
}

#flexible-textarea textarea {
  position: absolute; /* 外側のdivのテキストにかぶせるように表示 */
  left: 0;
  top: 0;
  width: 100%; /* 外側のdivと同じ大きさ */
  height: 100%;
  box-sizing: border-box;
  border: 1px solid #cccccc;
  border-radius: 6px;
  padding: 4px;
  outline: none;
  resize: none; /* 右下のリサイズのUI表示を非表示に */
  overflow: hidden; /* スクロールバーを非表示に */
  text-align: inherit;
  font-family: inherit; /* 外側のdivと同じフォントで表示 */
  font-size: inherit;
}
</style>

MarkdownのHTMLレンダリングをNuxt.jsのアプリに実装してみる

Nuxt.jsのアプリにMarkdownを表示させてみます。MarkdownからHTMLへの変換です。Nuxt 2です。

パッケージインストール

$ npm install @nuxtjs/markdownit

package.json の依存性の記述には以下が追加されました。

    "@nuxtjs/markdownit": "^2.0.0",

nuxt.config.js に以下のような記述を追加します。

  modules: [
    '@nuxtjs/markdownit',
  ],

  markdownit: {
    // ref: https://github.com/markdown-it/markdown-it
    linkify: true,
    breaks: true,
    use: [
    ],
  },

Vueファイル記述

HTMLの部分の記述例です。 $md.render というメソッドを呼び出して v-html に指定します。

<v-card-text>
  <div class="markdown" v-html="$md.render(content)"></div>
</v-card-text>

content にはMarkdownサンプルを以下のように文字列で直書きしておきます。Markdown書式でタイトル、コード、箇条書き、テーブル表示をサンプルに含めています。

export default {
  data() {
    return {
      content: `
# title 1

## title 2

### title 3

\`\`\`cpp
#include <iostream>

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
\`\`\`

C++プログラムは、\`main()\` 関数から実行を開始します。

- 東京都
- 神奈川県
- 千葉県
- 埼玉県

| 都道府県 | 県庁所在地 |
|---------|---------|
| 東京都   | 東京      |
| 神奈川県 | 横浜      |
| 埼玉県   | 埼玉      |
| 千葉県   | 千葉      |
| 茨城県   | 水戸      |
| 栃木県   | 宇都宮    |
| 群馬県   | 前橋      |
`
    }
  }
}

以下のようになりました。MarkdownがHTMLに変換され、表示されています。

※このMarkdownテキストのサンプルは、ChatGPTにいくつか質問した断片を集めたものです。最後は県庁所在地を聞いたものですが、埼玉県の県庁所在地が誤っていて、「さいたま」が正解です。

見た目を整える

CSSを以下のように書きます。内容はお好みに応じてです。

.markdown h1,
.markdown h2,
.markdown h3,
.markdown p,
.markdown pre,
.markdown ul,
.markdown table {
  margin-top: 10px;
  margin-bottom: 10px;
}

.markdown table {
  border-collapse: separate;
  border-spacing: 0 0;
}

.markdown table th,
.markdown table td {
  padding: 6px 12px;
  border-bottom: 1px solid #eeeeee;
  border-right: 1px solid #eeeeee;
}

.markdown table tr:first-child th {
  border-top: 1px solid #eeeeee;
  background-color: #333;
}

.markdown table tr th:first-child,
.markdown table tr td:first-child {
  border-left: 1px solid #eeeeee;
}

.markdown table tr:first-child th:first-child {
  border-top-left-radius: 8px;
}

.markdown table tr:first-child th:last-child {
  border-top-right-radius: 8px;
}

.markdown table tr:last-child td:first-child {
  border-bottom-left-radius: 8px;
}

.markdown table tr:last-child td:last-child {
  border-bottom-right-radius: 8px;
}

table関連の指定はChatGPTのテーブル表示に寄せました。

テーブルの枠線で色を指定している箇所があります。ダークモード前提での配色ですので、適宜調整してください。

コード表示のところ(<pre>...</pre>)を整えたいのですが、次の記事に書くことにします。

追記

次の記事 qiita.com

Twitterで星空botを運用しています

天文

毎日の星空の様子や天体の位置などをTwitterでツイートするbotを作って2年前から運用しています。

@hoshizora_today

開発した当時にこのブログで紹介するのを忘れていたのでいつか書こうと思っていたのですが、Twitterの経営方針が変わって今後のTwitterのbot運用がどうなるのか不透明で、botがいつ止まってしまうかもわからないので、このタイミングで思い出としてbotの設計を記憶の範囲で書いておきます。

このbotは、天体の位置を計算できるものはツイートを自動生成し、ツイート頻度が低く計算のハードルが高い内容は事前に手動でツイートを作成しています。

以前からこういうのを作りたいと思いながら、計算するプログラムをどう書いていいのかわからなくて挫折していました。しかし、約2年前に改めて調べてみたところ、勢いで計算できちゃったので、運用始めました。

ツイート内容の計算方法

太陽や月、惑星の位置は、NASAのJPL(Jet Propulsion Laboratory)が公開しているDE430というデータから計算しています。このデータは軌道要素ではなく、32日間の期間ごとのチェビシェフ多項式の係数が含まれており、係数から惑星の位置を計算できるようになっています。軌道要素のずれである摂動を考慮済みの位置を直接計算できます。

チェビシェフ多項式については以前に以下の記事を書きました。

チェビシェフ多項式(Chebyshev polynomials)でフィットさせた係数から値を復元 - suzuki-navi’s blog

地球からの惑星や月の相対位置を計算するにはまず地球の位置を計算する必要があります。地球の位置を直接計算するデータはDE430にはありません。かわりに、地球・月系の重心位置、および地球から見た月の位置を計算するためのデータがDE430にあります。この2つから地球の位置を計算することになります。

恒星時は時間の1次関数です。特定の時間における惑星や星座の方位角や高度は、恒星時と東京の経緯度から計算しています。地心視差は考慮していません。本当は月に関しては地心視差を考慮したほうがいいかもしれません。

星座に関するツイートは、あらかじめ原稿を用意していて、恒星時からツイートするタイミングだけを計算しています。

構成

ツイートテキスト生成と自動ツイートの2つの構成です。

ツイートテキスト生成

ツイートテキストを生成するローカルで動かすプログラムです。ツイートテキストとツイート時間のペアの一覧をこのプログラムで生成して、AWSのS3にアップロードします。単一のテキストファイルを生成しています。

プログラムの構成は最初に作ったときから半年ほどかけて少しずつ変わりました。

Ruby
↓
Ruby + Scala
↓
Ruby + Scala + Node.js
↓
Scala + Node.js
↓
Scala

一番最初はRubyだけで実装していました。なぜRubyなのかというと以下の方のgemを利用したかったためです。

Ruby - JPL 天文暦 gem の作成！ - mk-mode BLOG

しかし、ツイート内容の柔軟な生成がRubyでは辛かったのと、計算速度が遅かったため、途中で一部をScalaにしました。さらに、自動生成と手動生成をマージするところだけNode.jsで書きました。マージ処理の言語はなんでもよかったのですが、後述の通りPythonもすでに併用していたので、せっかくならばとバラバラな言語で書いてみました。

その後、計算速度改善のためRubyのコードは全部Scalaに置き換わりました。その後、ロジックの柔軟な対応のためにNode.jsでの実装もScalaに置き換えました。

ソースコードは以下にあります。リファクタリングをしようとして中途半端になっており、非常に汚いコードです。手動で作成したツイート内容はテキストファイルで書いてあります。

https://github.com/suzuki-navi/hoshizora_today/tree/main/calc

自動ツイート

AWS Lambdaで動くプログラムです。Twitter APIにアクセスしてツイートします。Pythonで書きました。

EventBridgeで5分に一度Lambdaを起動します。S3からデータを読み取って、その時間帯にツイートすべきテキストがあればツイートします。

Pythonソースコードは以下にあります。

https://github.com/suzuki-navi/hoshizora_today/blob/main/tweet/tweet.py

Twitter APIにアクセスするのはtwitterというずばりな名前のパッケージを使っています。

twitter · PyPI

ツイートテキストに出てくる用語集

  • 月相
    • 新月から次の新月までを0から28として、月の満ち欠けの状態を表した数値です。7が上弦の月、14が満月、21が下弦の月を表します。平均すると24時間で0.95ずつ進みますが、月の軌道が楕円で速度が一定でないため、月相の進み方も一定ではありません。星空botでは地球から見た太陽と月の黄経差で計算しています。地心視差は考慮していません。星空botでは0から28で表現していますが、0から360で表現することもあるようです。
  • 南中
    • 北天の天体であれば天の北極から、観測地点の天頂を通って、天の南極に達する直線を天体が通過することです。日本からであれば、惑星や南天の星ならば真南を通過することです。北天の星なら北極星の上です。
  • 黄道十二星座
  • 二十四節気
    • 天球上の太陽の通り道を24等分した点を太陽が通過する瞬間です。24個に名前が付いています。春分、夏至、秋分、冬至はよく知られている二十四節気ですが、それ以外にも20個あります。
  • 衝
    • 地球よりも外側を回る惑星（火星、木星、土星など）が、地球から見て太陽と反対の方向に来た瞬間です。太陽と反対なので、夜に見えやすい位置です。地球との距離も衝の前後に近くなります。
  • 合
    • 地球から見て太陽と同じ方向に惑星が来た瞬間です。この前後は地球からその惑星を観測ることができません。地球よりも外側を回る惑星（火星、木星、土星など）は、地球から見て太陽よりも向こう側になります。地球よりも内側を回る惑星（水星、金星）は、太陽よりも向こう側に来る外合と、太陽よりも手前に来る内合の2種類あります。

以下のページにも説明を書いています。

hoshizora_today

開発当時のブログ記事

このbotを開発するときに書いた関連するブログ記事は以下があります。

これを見るといろいろな言語で試行錯誤していたようです。当初はRubyで全部書こうとしていたのでAWS LambdaでRubyを動かす方法を調べていたのですが、途中で言語は適材適所と考え直し、AWS LambdaからTwitter APIにアクセスする部分はPythonで書くことにしたのだと思われます。

セルオートマトンによるCPU作成

CPUを自作しました！（って言ってもバーチャルなものです）

世の中CPUを自作している人はたくさんいます。汎用のICチップを組み合わせて作る人もいれば、トランジスタを大量に組み合わせて作る人もいます。

この界隈ではバイブルのような「CPUの創りかた」という本もあるらしいです。私は読んでいないのですが、これを読めばたぶんだれでもCPUを作れるんだと思います。

半導体を使わずにリレーでCPUを作る人もいます。回路のスイッチングができればなんでもよいのです。
Relay Computer / リレーコンピュータ #shorts - YouTube

リレーとはこんな部品です。
継電器 - Wikipedia

昔は本当にリレーで作られたコンピュータもありました。
機械音がカッコいい！ 60年前の世界初の小型純電気式計算機「14-A」を動かしてみた＠樫尾俊雄発明記念館 - YouTube

リレーは物理的にスイッチが動くので動作速度を向上させられず、現代では半導体に比べてメリットがありません。

こちらはボールを転がして計算させているコンピュータです。
Learn how COMPUTERS work using MARBLES - YouTube

物理ではなく仮想世界では、マインクラフトでCPUを作る人もいます。
MOD・コマブロ無しで6bitCPU作ってみた - YouTube

仮想世界でのCPUがありならば、セルオートマトンでCPUを作る人もいます。

セルオートマトン(cellular automaton)は格子状に並んだセルが単純な規則で次々に状態遷移するモデルです。各セルは隣接するセルの状態に応じて次の時間の状態が決まります。状態遷移の規則によってさまざまなセルオートマトンが考案されています。代表例がライフゲームです。
ライフゲーム - Wikipedia

ライフゲームでCPUを作っている例
A Simple CPU on the Game of Life - Part 4

ワイヤワールドというセルオートマトンでもCPUを作っている人がいます。このサイトはCPUの仕組みを理解する上でとても参考になります。物理世界のCPUとワイヤワールドのCPUとで異なるところは多いと思いますが、似ているところもあるはずです。
The Wireworld computer

半導体でもリレーでも仮想世界でも媒体はなんでもよく、論理回路と順序回路があればCPUを作れます。論理回路はANDやNOTなどの論理演算ができる回路です。信号は瞬時に伝わるのではなく素子の間を順番に時間差で伝わっていきます。その時間差を利用した回路は順序回路と言います。

マインクラフトもセルオートマトンみたいなもんですね。

ということで私はセルオートマトンで作ることにしました。今回のセルオートマトンは、ライフゲームやワイヤワールドとは異なるルールで私のオリジナルです。これによりCPU設計の疑似体験ができました。

完成形はこんな感じです。ブラウザ上でセルオートマトンが動き、CPUとして機能します。

このCPU開発日記をしばらく連載として記事にしていくつもりです。続かなかったらごめんなさい。続いたら、基本的な回路を組み合わせるだけでCPUになるということを示したいと思います。

セルオートマトンによるCPU作成の連載目次

AtCoder参戦日記 ABC185 2020/12/13 12回目

AtCoder

AtCoderの12回目の参加となった2020/12/13のABC185の記録です。9か月も下書きのまま放置してしまっていましたが、前回記事に引き続き、AtCoderの感を取り戻すための復習記事です。

100分の競技時間ぎりぎりで5完でした。

Dまでは35分ほどで完了しました。Eは問題文を1回読んですぐにあきらめ、Fに進みました。Fはコードを書くのに時間がかかってしまいましたが、ぎりぎりACを取れました。

パフォーマンスは1160で、AtCoder Beginner Contestとしては過去2番目にいい成績ではありました。

問題 結果 言語 競技後
A AC JavaScript
B AC Java Scala
C AC Ruby C++
D AC Scala
E
F AC C++ Java

5問できたのもめずらしいのですが、5言語使ったのは初めてです。1問目の言語選択は理由はないのですが、他は問題ごとに最適な言語を選んだつもりです。

過去の参戦記録

参加日 # コンテスト名 結果 使用言語
2020/08/29 1 ABC177 3完 / 614 Scala, Scala, Java
2020/09/13 2 ABC178 5完 / 1466 Python, Scala, Scala, C++, Scala
2020/09/19 3 ABC179 3完 / 1004 Java, Scala, Scala
2020/10/03 4 ARC104 2完 / 1067 Python, Scala
2020/10/10 5 HHKB2020 3完 / 902 C++, Scala, Java
2020/10/11 6 ARC105 2完 / 1069 Ruby, Java
2020/11/01 ABC180 4完 / (937) Ruby, Scala, C++, Java
2020/11/01 7 ABC181 4完 / 1136 C++, Scala, Java, Java
2020/11/07 ABC171 5完 / (1557) C++, Scala, Ruby, Java, Java
2020/11/08 8 ABC182 4完 / 1072 Ruby, Scala, Scala, Java
2020/11/15 9 ABC183 4完 / 871 Ruby, Ruby, Java, Java
2020/11/21 10 ARC108 3完 / 1979 Ruby, Java, Java
2020/12/05 11 ARC110 3完 / 1562 Ruby, Scala, Java
2020/12/13 12 ABC185 5完 / 1160 JavaScript, Java, Ruby, Scala, C++

※結果欄は、時間内にAC取れた問題数とパフォーマンスです。パフォーマンスの括弧の数字はバーチャル参加の推定値です。

A - ABC Preparation

問題へのリンク

言語の練習のためにJavaScriptにしました。競技本番でJavaScriptを書いたのは初めてです。

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
const [a1, a2, a3, a4] = lines[0].split(" ").map(s => Number(s));
console.log(Math.min(a1, a2, a3, a4));

B - Smartphone Addiction

問題へのリンク

手続き型で書きたかったので関数型のScalaではなくJavaで書きました。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int t = sc.nextInt();

    var abs = new int[2*m];
    for (int i = 0; i < m; i++) {
      abs[2*i  ] = sc.nextInt();
      abs[2*i+1] = sc.nextInt();
    }

    int c = n;
    int ct = 0;
    for (int i = 0; i < m; i++) {
      int a = abs[2*i ];
      int b = abs[2*i+1];
      c -= a - ct;
      if (c <= 0) {
        System.out.println("No");
        return;
      }
      c += b - a;
      if (c > n) c = n;
      ct = b;
    }
    c -= t - ct;
    if (c <= 0) {
      System.out.println("No");
      return;
    }
    System.out.println("Yes");
  }
}

9か月後のいま、Scalaで書き直しました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, m, t = sc.nextInt();

  var n1: Int = n;
  var t1: Int = 0;
  var result: Boolean = true;
  (0 until m).foreach { _ =>
    val a, b = sc.nextInt();
    n1 = n1 - (a - t1);
    if (n1 <= 0) {
      result = false;
    }
    n1 = n1 + (b - a);
    if (n1 > n) {
      n1 = n;
    }
    t1 = b;
  }
  n1 = n1 - (t - t1);
  if (n1 <= 0) {
    result = false;
  }
  if (result) {
    System.out.println("Yes");
  } else {
    System.out.println("No");
  }
}

C - Duodecim Ferra

問題へのリンク

組み合わせ数を計算するだけですが、64bit整数でオーバーフローを回避する方法がすぐには思いつかず、Rubyの整数で計算しました。

l = gets.strip.to_i

s = 1
for i in 12..(l-1)
  s = s * i
end
for i in 2..(l-12)
  s = s / i
end
puts(s)

9か月後のいま、他の人の回答を見て、演算の順序を気にすればいいとわかって、書いたコードが以下です。

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

int main() {
  int l;
  cin >> l;

  long long result = 1;
  for (int i = 1; i <= 11; i++) {
    result *= l - i;
    result /= i;
  }
  cout << result << endl;
}

D - Stamp

問題へのリンク

関数型で書くのが楽そうだったのでScalaにしました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, m = sc.nextInt();
  val as = Array.fill(m)(sc.nextInt());

  val as_sorted = as.sorted;

  val intervals = (0 to m).map { i =>
    if (m == 0) {
      n;
    } else if (i == m) {
      n - as_sorted(i-1);
    } else if (i == 0) {
      as_sorted(i) - 1;
    } else {
      as_sorted(i) - as_sorted(i-1) - 1;
    }
  }.filter(_ > 0);

  val answer = if (intervals.size == 0) {
    0;
  } else {
    val min = intervals.min;
    intervals.map { d =>
      (d-1) / min + 1;
    }.sum;
  }
  println(answer);
}

E - Sequence Matching

問題へのリンク

問題文を1回読んで、すぐにあきらめました。

F - Range Xor Query

問題へのリンク

少し考えて解法を思いついたものの、コードを書くのに時間がかかってしまいました。解法はあとで解説を読んで、セグメント木というらしいです。最後につまらないバグにもはまってしまい、問題文を読み始めてからAC取るまでに1時間近くかかってしまいました。

解法を思いついた時点で、処理速度の勝負だと思ったので、C++にしました。

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

int main() {
  int n, q;
  cin >> n >> q;

  int count = 1 << 19 + 1;
  int as[count];
  for (int i = 0; i < n; i++) {
    cin >> as[i];
  }
  for (int i = n; i < count; i++) {
    as[i] = 0;
  }
  int *ass[19];
  for (int di = 0; di < 19; di++) {
    int d = 1 << di;
    int c = count >> (di+1);
    ass[di] = new int[c];
    for (int i = 0; i < c; i++) {
      int id = i << (di+1);
      int xo = 0;
      for (int j = 0; j < d; j++) {
        xo = xo ^ as[id + j];
      }
      ass[di][i] = xo;
    }
  }

  for (int i = 0; i < q; i++) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) {
      int z = x - 1;
      for (int di = 0; di < 19; di++) {
        if (((z >> di) & 1) == 0) {
          int zi = z >> (di+1);
          ass[di][zi] = ass[di][zi] ^ y;
        }
      }
    } else {
      int zo = 0;
      int z = y;
      for (int di = 0; di < 19; di++) {
        if (((z >> di) & 1) != 0) {
          zo = zo ^ ass[di][z >> (di+1)];
        }
      }
      z = x - 1;
      for (int di = 0; di < 19; di++) {
        if (((z >> di) & 1) != 0) {
          zo = zo ^ ass[di][z >> (di+1)];
        }
      }
      cout << zo << endl;
    }
  }
}

9か月後のいま、ゼロベースで考えてJavaで書いたコードが以下です。上記とたぶん同じロジックだと思うのですが、上記を今となっては読み解けません。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    int q = sc.nextInt();

    int max = 1 << 19;
    int[] segment = new int[max];
    int[] buf = new int[20];

    for (int i = 0; i < n; i++) {
      int a = sc.nextInt();
      updateSegment(i, a, segment, buf, max);
    }

    for (int i = 0; i < q; i++) {
      int t = sc.nextInt();
      int x = sc.nextInt();
      int y = sc.nextInt();
      if (t == 1) {
        x = x - 1;
        updateSegment(x, y, segment, buf, max);
      } else {
        x = x - 1;
        y = y - 1;
        int ax = fetchSegment(x, segment, buf);
        int ay = fetchSegment(y + 1, segment, buf);
        int answer = ay ^ ax;
        System.out.println(answer);
      }
    }

  }

  private static void updateSegment(int idx, int x, int[] segment, int[] buf, int max) {
    indexOfUpdateSegment(idx + 1, buf, max);
    int i = 0;
    while (true) {
      int s = buf[i];
      if (s < 0) break;
      segment[s] ^= x;
      i++;
    }
  }

  private static int fetchSegment(int idx, int[] segment, int[] buf) {
    indexOfFetchSegment(idx, buf);
    int i = 0;
    int ret = 0;
    while (true) {
      int s = buf[i];
      if (s < 0) break;
      ret ^= segment[s];
      i++;
    }
    return ret;
  }

  // 13 -> 13, 14, 16, 32, 64, 128
  private static void indexOfUpdateSegment(int idx, int[] buf, int max) {
    int offset = 0;
    while (idx < max) {
      int lastBit = idx & -idx;
      buf[offset] = idx;
      offset++;
      idx = idx + lastBit;
    }
    buf[offset] = -1;
  }

  // 13 -> 13, 12, 8
  private static void indexOfFetchSegment(int idx, int[] buf) {
    int offset = 0;
    while (idx != 0) {
      buf[offset] = idx;
      offset++;
      int lastBit = idx & -idx;
      idx = idx - lastBit;
    }
    buf[offset] = -1;
  }
}

AtCoder参戦日記 ARC110 2020/12/05 11回目

AtCoder

AtCoderの11回目の参加となった2020/12/05のARC110の記録です。9か月も下書きのまま放置してしまっていましたが、前回記事に引き続き、AtCoderの感を取り戻すための復習記事です。

65分ほどでA, B, Cの3完でした。

20分ぐらいでA, Bまで終わったところで、C以降がとても難しそうだったので、解けそうな問題を探そうと、C, D, Eの問題を読みました。C -> E -> D の順に取り掛かろうと判断し、Cを65分ぐらいでできました。残り時間はEを考えたものの、さっぱりわからずあきらめました。

パフォーマンスは1562で前回に続き奇跡的にいい成績でした。ABCよりもARCのほうがパフォーマンスが出やすい気がします。

問題 結果 言語 競技後
A AC Ruby
B AC Scala
C AC Java
D
E
F

過去の参戦記録

参加日 # コンテスト名 結果 使用言語
2020/08/29 1 ABC177 3完 / 614 Scala, Scala, Java
2020/09/13 2 ABC178 5完 / 1466 Python, Scala, Scala, C++, Scala
2020/09/19 3 ABC179 3完 / 1004 Java, Scala, Scala
2020/10/03 4 ARC104 2完 / 1067 Python, Scala
2020/10/10 5 HHKB2020 3完 / 902 C++, Scala, Java
2020/10/11 6 ARC105 2完 / 1069 Ruby, Java
2020/11/01 ABC180 4完 / (937) Ruby, Scala, C++, Java
2020/11/01 7 ABC181 4完 / 1136 C++, Scala, Java, Java
2020/11/07 ABC171 5完 / (1557) C++, Scala, Ruby, Java, Java
2020/11/08 8 ABC182 4完 / 1072 Ruby, Scala, Scala, Java
2020/11/15 9 ABC183 4完 / 871 Ruby, Ruby, Java, Java
2020/11/21 10 ARC108 3完 / 1979 Ruby, Java, Java
2020/12/05 11 ARC110 3完 / 1562 Ruby, Scala, Java

※結果欄は、時間内にAC取れた問題数とパフォーマンスです。パフォーマンスの括弧の数字はバーチャル参加の推定値です。

A - Redundant Redundancy

問題へのリンク

n = gets.strip.to_i

p = 1
i = n
while i >= 2
  p = p.lcm(i)
  i -= 1
end

puts(p + 1)

B - Many 110

問題へのリンク

かなりの力技です。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val t = sc.next();

  val c = 10_000_000_000L;

  val answer = if (t == "1") {
    c * 2;
  } else if (t == "0") {
    c;
  } else if (t == "00") {
    0;
  } else if (t == "01") {
    c - 1;
  } else if (t == "10") {
    c;
  } else if (t == "11") {
    c;
  } else {
    val pre = t.substring(0, 3);
    val n3 = n / 3;
    val nm = n % 3;
    if ((1 until n3).exists(i => !t.startsWith(pre, i * 3))) {
      0;
    } else {
      val suf = t.substring(n3 * 3);
      if (!pre.startsWith(suf)) {
        0;
      } else {
        if (pre == "110") {
          if (nm == 0) {
            c - n3 + 1;
          } else {
            c - n3;
          }
        } else if (pre == "101") {
          c - n3;
        } else if (pre == "011") {
          if (nm <= 1) {
            c - n3;
          } else {
            c - n3 - 1;
          }
        } else {
          0;
        }
      }
    }
  }
  println(answer);
}

もう少しシンプルな方法はないかと、他の人の回答を参考に書き直したのが以下です。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val t = sc.next();

  val c = 10_000_000_000L;

  val answer = if (t == "1") {
    c * 2;
  } else if (t == "11") {
    c;
  } else {
    if (("110" * (n / 3 + 3)).indexOf(t) < 0) {
      0;
    } else {
      def count(str: String, pattern: String): Int = {
        @scala.annotation.tailrec
        def sub(offset: Int, result: Int): Int = {
          val p = str.indexOf(pattern, offset);
          if (p < 0) result else sub(p + 1, result + 1);
        }
        sub(0, 0);
      }
      if (t.endsWith("0")) {
        c - count(t, "0") + 1;
      } else {
        c - count(t, "0");
      }
    }
  }
  println(answer);
}

C - Exoswap

問題へのリンク

コンテスト当時にAC取ったコードです。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    var ps = new int[n];
    for (int i = 0; i < n; i++) {
      ps[i] = sc.nextInt() - 1;
    }

    var fsa1 = new boolean[n];
    var fsa2 = new boolean[n];
    var fsb1 = new boolean[n];
    var fsb2 = new boolean[n];
    for (int i = 0; i < n; i++) {
      var p = ps[i];
      if (p > i) {
        for (int j = i; j < p; j++) {
          if (fsa1[j]) {
            System.out.println(-1);
            return;
          }
          fsa1[j] = true;
        }
        fsa2[i] = true;
      } else if (p < i) {
        for (int j = i-1; j >= p; j--) {
          if (fsb1[j]) {
            System.out.println(-1);
            return;
          }
          fsb1[j] = true;
        }
        fsb2[p] = true;
      } else {
        System.out.println(-1);
        return;
      }
    }
    for (int i = 0; i < n-1; i++) {
      if (!fsa1[i]) {
        System.out.println(-1);
        return;
      }
      if (!fsb1[i]) {
        System.out.println(-1);
        return;
      }
    }
    for (int i = n-2; i >= 0; i--) {
      if (fsa2[i]) {
        System.out.println(i+1);
      }
    }
    for (int i = 0; i < n-1; i++) {
      if (!fsa2[i]) {
        System.out.println(i+1);
      }
    }
  }
}

これを9か月後のいま見ても、よくわからなかったので、もう一度書き直しました。1時間ではできなかったし、なかなかバグが取れず大量にWAを出してしまいました。衰えています。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    var ps = new int[n];
    for (int i = 0; i < n; i++) {
      ps[i] = sc.nextInt() - 1;
    }

    var f1 = new boolean[n]; // 右を先に交換
    var f2 = new boolean[n]; // 左を先に交換

    for (int i = 0; i < n; i++) { // 0 - 3
      var p = ps[i];
      if (p < i) {
        for (int j = p + 1; j < i; j++) {
          if (f2[j]) {
            System.out.println(-1);
            return;
          }
          f1[j] = true;
        }
        if (p > 0) {
          if (f1[p]) {
            System.out.println(-1);
            return;
          }
          f2[p] = true;
        }
        if (i < n - 1) {
          if (f1[i]) {
            System.out.println(-1);
            return;
          }
          f2[i] = true;
        }
      } else if (p > i) {
        for (int j = i + 1; j < p; j++) {
          if (f1[j]) {
            System.out.println(-1);
            return;
          }
          f2[j] = true;
        }
        if (i > 0) {
          if (f2[i]) {
            System.out.println(-1);
            return;
          }
          f1[i] = true;
        }
        if (p < n - 1) {
          if (f2[p]) {
            System.out.println(-1);
            return;
          }
          f1[p] = true;
        }
      } else {
        System.out.println(-1);
        return;
      }
    }

    int i = 1;
    while (i < n) {
      if (f1[i]) {
        int j = i + 1;
        while (f1[j]) {
          j++;
        }
        int j0 = j;
        while (j >= i) {
          System.out.println(j);
          j--;
        }
        i = j0 + 1;
      } else {
        System.out.println(i);
        i++;
      }
    }

  }

AtCoder参戦日記 ARC108 2020/11/21 10回目

AtCoder

AtCoderの10回目の参加となった2020/11/21のARC108の記録です。10か月も下書きのまま放置してしまっていましたが、久しぶりにAtCoderの感を取り戻したくて復習がてらブログ記事に公開します。

65分ほどでA, B, Dの3完でした。Cはとっかかりが全然わからず、早々にDに進みました。そのあとCに戻ってコードを書き始めましたが、時間切れとなりました。

パフォーマンス値が過去最高の1979になり、緑の上位半分に昇格しました。実力が上がってきたというわけではなく、今回はたまたま自分にとって簡単な問題だっただけなのだと思います。

問題 結果 言語 競技後
A AC Ruby JavaScript
B AC Java
C
D AC Java
E
F

f:id:suzuki-navi:20210904232020p:plain

過去の参戦記録

参加日 コンテスト名 結果 使用言語
2020/08/29 #1 ABC177 3完 / 614 Scala, Scala, Java
2020/09/13 #2 ABC178 5完 / 1466 Python, Scala, Scala, C++, Scala
2020/09/19 #3 ABC179 3完 / 1004 Java, Scala, Scala
2020/10/03 #4 ARC104 2完 / 1067 Python, Scala
2020/10/10 #5 HHKB2020 3完 / 902 C++, Scala, Java
2020/10/11 #6 ARC105 2完 / 1069 Ruby, Java
2020/11/01 ABC180 4完 / (937) Ruby, Scala, C++, Java
2020/11/01 #7 ABC181 4完 / 1136 C++, Scala, Java, Java
2020/11/07 ABC171 5完 / (1557) C++, Scala, Ruby, Java, Java
2020/11/08 #8 ABC182 4完 / 1072 Ruby, Scala, Scala, Java
2020/11/15 #9 ABC183 4完 / 871 Ruby, Ruby, Java, Java
2020/11/21 #10 ARC108 3完 / 1979 Ruby, Java, Java

※結果欄は、時間内にAC取れた問題数とパフォーマンスです。パフォーマンスの括弧の数字はバーチャル参加の推定値です。

A - Sum and Product

問題へのリンク

最初は全探索しようと思って処理速度が必要だと思い、Javaで書き始めました。しかし全探索はだめなんじゃないかと思い、2次方程式で解を求める方法に変更しました。その方法で提出したものの、10の12乗をさらに2乗するところで long では桁数が足りなくてWAになってしまいました。Javaで手っ取り早い解決策が思いつかなかったので、整数の桁数を気にしなくてもよいRubyで書き直しました。

あとで解説を読んで全探索でもよかったのだとわかりました。

↓WAになったJavaのコード。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    long s = sc.nextLong();
    long p = sc.nextLong();

    long sq = s * s - 4 * p;
    int sqrt = (int)(Math.sqrt((double)p));
    if (sqrt * sqrt != sq) {
      sqrt++;
      if (sqrt * sqrt != sq) {
        System.out.println("No");
        return;
      }
    }
    if ((s - sqrt) % 2 == 0) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

↓ACをとったRubyのコード。

s, p = gets.strip.split(" ").map(&:to_i)

sq = s * s - 4 * p
sqrt = Integer.sqrt(sq)
if sqrt * sqrt != sq
  puts("No")
  exit(0)
end
if (s - sqrt) % 2 == 0
  puts("Yes")
else
  puts("No")
end

後日JavaScriptでも書きました。Rubyと同じロジックでは正しい答えを出せず、全探索しました。Rubyと同じロジックができなかった理由は、巨大な整数を扱えないためと思われます。

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
const [s, p] = lines[0].split(" ").map(s => Number(s));

const max = Math.sqrt(p);
for (let i = 1; i <= max; i++) {
    if (i * (s - i) == p) {
        console.log("Yes");
        process.exit(0);
    }
}
console.log("No");

B - Abbreviate Fox

問題へのリンク

この問題でも処理速度が必要だと思い、Javaで書きました。

長大な文字列を頻繁に書き換えながらの処理なので、Stringではなくchar<>を使いました。

size2という変数は処理速度を少しでも稼ぐためですが、意味があったのかどうかは不明です。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    var str = sc.next();
    var arr = new char[n+2];
    for (int i = 0; i < n; i++) {
      arr[n-1-i] = str.charAt(i);
    }
    int size = n;
    int size2 = n;
    int i = n-3;
    while (i >= 0) {
      if (arr[i] == 'x' && arr[i+1] == 'o' && arr[i+2] == 'f') {
        for (int j = i+3; j < size2; j++) {
          arr[j-3] = arr[j];
        }
        size -= 3;
        size2 -= 3;
      } else if (arr[i] == 'o' || arr[i] == 'f') {
        // nothing
      } else {
        size2 = i;
      }
      i--;
    }
    System.out.println(size);
  }
}

C - Keep Graph Connected

問題へのリンク

最初はぜんぜんわからず、Dに先に進みました。DのあとにCに戻ってコードを書き始めたものの、時間切れとなりました。

D - AB

問題へのリンク

規則性を見つければ難しくない問題です。ここまでの惰性でJavaになりました。

import java.util.Scanner;

class Main {
  static int m = 1_000_000_007;

  static int pow2(int n) {
    long s = 1;
    long a = 2;
    while (n > 0) {
      if ((n & 1) != 0) s = s * a % m;
      a = a * a % m;
      n >>= 1;
    }
    return (int)s;
  }

  static int com(int n) {
    int s1 = 1;
    int s2 = 1;
    for (int i = 0; i < n; i++) {
      int t = (s1 + s2) % m;
      s1 = s2;
      s2 = t;
    }
    return s2;
  }

  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    boolean caa = (sc.next().equals("B"));
    boolean cab = (sc.next().equals("B"));
    boolean cba = (sc.next().equals("B"));
    boolean cbb = (sc.next().equals("B"));
    int answer = 0;
    if (n == 2) {
      answer = 1;
    } else if (cab && cbb) {
      // ABBB
      answer = 1;
    } else if (!cab && !caa) {
      // AAAB
      answer = 1;
    } else if (cab && !cba) {
      answer = pow2(n-3);
    } else if (cab) {
      answer = com(n-3);
    } else if (!cab && cba) {
      answer = pow2(n-3);
    } else if (!cab) {
      answer = com(n-3);
    }
    System.out.println(answer);
  }
}