giantneco’s blog

技術メモ

AtCoder Panasonic 2020

Contest Result - AtCoder

祝水色。

まだまだレーティングを上げる余地はありそうだ。

ただし青以上のパフォーマンスは一度も取っていないので、青になるためにはかなり精進が必要っぽい。

まず 5 完を安定してとれるようにならないといけないか。

A

配列を問題文からのコピペでつくって出力するだけ。

B

1 WA だしてしまった。

基本的に h * w / 2 で、h * w が奇数なら +1でよい。

しかし、h か w が 1 の場合は例外になるのでこれを考慮する必要があった。

C

4 WA だしてしまった。

精度の問題にはしたくないので式変形して (c - a - b)2 > 4ab の形にもっていく。

なんで WA 食らったかというと、c - a - b < 0 の場合を見落としていたから。

若干パニックになって必要のないところをいじってまた WA くらったりしてた。

D

全ての並び替えを出す要領で、1 文字目は{a}、2 文字目は {a,b}、3 文字目は {a,b,c} という感じの組み合わせを全列挙する。

このままでは条件に合わない組み合わせが含まれるので、一文字飛ばして新しい文字が出現するようなものはフィルタアウトする。

たとえば "aac" は 'b' を飛ばして 'c' が出現しているが、これは辞書順で出現済みなはずの "aab" が同値なので外さないといけない。

たぶんもっとスマートな方法があるとは思う。

ちなみに WA は入力を読み込み忘れたまま提出してしまったため。粗忽だ。

E

解法が思いつかず総当りっぽく解こうとしたが無事 TLE。

解説みるとやっぱり総当りだったが、自分の実装より時間がかからずになっていたのでまあそうなるか。

AtCoder Beginner Contest 157

Contest Result - AtCoder

今回は A から E までの 5 完。わりと調子良かった。

入水できるんじゃないかなと期待もしたが、思っていたよりレーティングは上がらなかった。 もう 2 回位は水パフォーマンスが必要そう。

A

n を 2 で割ったものに、n が奇数ならさらに 1 加算する。

B

愚直に 3x3 の2次元配列を作って、それがビンゴの条件を満たしているか確認する。

ちょっと実装がめんどいぐらい。

C

調べればいい範囲がたかだか 1000 以下だったので、総当りで条件にあっているものを探す。

こっちも愚直な実装になった。

D

Union Find 木を使って、グループ分けをする。

その後 1 から N までについて、グループのサイズから「直接の友人関係にある人数」と「グループ内でブロックしている人数」、「自分自身」の数を引く。 Union Find 木のテンプレートを持ってなかったので0から実装したがなんとか間に合った。テンプレ実装は用意しておいたほうが良さそう。

なお、自分はこれよりも E を先に解いていた。他にも同じような判断をした人はそこそこいるっぽい。

E

競技プログラミングでよくある発想の転換が要求される問題だと思う。

最初に考えた 2 個目のコマンドの「l 文字目から r 文字目までで含まれる文字種のカウント」は、愚直にやっていたら計算量が大きくなりそう。

最悪の場合は N x Q で 1010 かかるので、時間内に終わらないと判断した。

考えを変えて、ある文字が「l 文字目から r 文字目までで含まれる」かどうかを 26 回高速に判定できれば良さそう、と考えた。

なので 26 個アルファベットごとに std::set<ll> を用意して、出現位置を入れておく。

コマンド 1 は set への追加と削除で済ませて、コマンド 2 の方は l より大きい出現位置を lower_bound でとってそれが r 以下なら条件を満たすとしてそれぞれカウントすればよい。

int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    vector<set<ll>> d(26, set<ll>());
    for (ll i = 0; i < n ; ++i) {
        int c = s[i] - 'a';
        d[c].insert(i+1);
    }
    ll m;
    cin >> m;
    for (ll j = 0; j < m; ++j) {
        int com;
        cin >> com;
        if (com == 1) {
            ll i;
            int idx;
            char c;
            cin >> i >> c;
            idx = c - 'a';
            for (ll k = 0; k < 26; ++k) {
                d[k].erase(i);
            }
            d[idx].insert(i);
        } else {
            ll left, right;
            cin >> left >> right;
            ll count = 0;
            for (ll k = 0; k < 26; ++k) {
                auto iter = d[k].lower_bound(left);
                if (iter != d[k].end() && *iter <= right) {
                    ++count;
                }
            }
            cout << count << endl;
        }
    }
}

Object Oriented Conference 2020 参加してきたメモ

ooc.connpass.com

2/16 に行われた Object Oriented Conference に参加してきた。

OOC は名前の通り、「オブジェクト指向」についてのカンファレンス。 セッションは大小 34 あり、設計やアーキテクチャの話が多かったし、DDD も結構テーマに上げられてた。 CfP 倍率は 3 倍程度で結構応募があったらしい。

全体的には、キーノートでも言われていたが、多様性により OO といっても立場や考えが色々異なる視点からの話が聞けた。

以下聞いてきたセッションの話。

キーノート Object Oriented Diversity

OOC keynote: Object Oriented Diversity - Speaker Deck

OO が様々な意味を持つようになってしまい、 同じ OO の話をしていても行き違いが発生しやすくなってしまった。 ということで OO について話すときには「コンテキスト」を意識しましょうという話だった。

実際 OOP にしてもメッセージパッシングのことを OO と言っていたり、抽象データ型を使うことを OO と言ったりもするので、文脈を共有するのは大事そう。

DDD はオブジェクト指向言語でどのようにメンテナンス可能なコードを書くか

DDDはオブジェクト指向を利用してどのようにメンテナブルなコードを書くか

DDD の話。

  • モデリングが重要
    • {ドメインエキスパートからの知識 → モデルに反映 → 運用からのフィードバック}の改善ループが重要
    • モデルの継続的な改善のためにも高い拡張性が必要
  • 軽量 DDD でベストプラクティスを取り入れるのでも効果はある。そこからモデリングに進むと良い
  • DDD を導入する際にはお手本となるコードを作ってから、それを参考にして残りをつくる、というやり方がおすすめ

  • モデリング手法

    • 決まった方法はない
    • よく使われるのは

ユースケース駆動のポイントとしては:

紹介されていた DomainLanguage.com https://domainlanguage.com/ はよくまとまっているし参考にしたい

数理的システム設計

ソフトウェアシステム設計における アレグザンダー理論の活用 数理的システム設計手法の提案 #agileto2019 - Speaker Deck

アーキテクチャ設計の話だが、ちょっとついていけなかった。

自分もアレキザンダーの本とかやっぱりちょっとは目を通してみるべきかも。

アジャイル時代のモデリング 平鍋健児

Modeling in the Agile Age

アジャイルでのモデリングの話。手法というよりもどうモデリングを続けていくかのプラクティスの話か。

紹介されていたアイディアとしては、モデルを作成した際に出来る図・資料を保存するもの = KEEPS とすぐ破棄するもの = TEMPS に分けると良いとのこと。

KEEPS にするものは価値を生み出すもの:

TEMPS にするものはほとんど価値を産まないもの: - カジュアルモデリングの成果物 - クラス図、シーケンスダイアグラムなど

他に Impact Mapping というモデリング手法や C4 Model というものが紹介されていた。

「モジュールとしてのマイクロサービス」と「分割単位としてのドメイン」について考える

「モジュールとしてのマイクロサービス」と 「分割単位としてのドメイン」について考える - Speaker Deck

システムをどのように分割するかの話。

  • 複雑なものは分けて考える
  • 重要な設計要素は、モジュール性とビジネスの関心事
  • 人間のコミュニケーションを阻害しないようにシステムとチームを構成する
  • 分散システムの難易度などの落とし穴に注意
  • モノリスが常に不利益を生むわけではない
    • モジュラモノリスという内部的に分割を行うパターンも採用例がある
  • MSA していてもフロントエンドがモノリス化してしまうことが多々ある
    • フロントエンドもモジュラモノリスにするとよい

オブジェクト思考プログラミングの過去・現在・未来

オブジェクト指向プログラミングの現在・過去・未来

OOP とはなにか?に対しては「データの抽象化」がそれに当たるという主張。 データ抽象により、語彙(ユビキタス言語か)、自己文書化、関心事の分離などできる。

後半は OOP の歴史の話。

黎明期から始まり、型を軽視や怪しげな例え話などによる混乱があったが、現在はその混乱が収束しつつある。

型がない言語で OOP できっこない、という話があったが、個人的にはちょっと反対したい。

AtCoder Beginner Contest 156

Contest Result - AtCoder

今回は A から D まで。ランクは少し上がった。

今回の問題では、組み合わせを高速に計算する手法は学習済みだったのが役に立った。

E は考え方は合っていたが時間がなくてコンテスト期間中に回答が間に合わなかったので悔しい思いをすることになってしまった(後日 AC 済み)。

特に「 r 個を n 部屋に 1 つ個以上ずつ分ける」というのがとっさに出てこなかったのが痛い。

ところで、E では k が 1 の場合には「すべての部屋に1個ずつある状態」が実現できないんじゃないかと思ったんだが、解説でも触れられてないし他の人のブログ記事でも触れているものがない。

そういうようにコードをいじっても AC になるのでなんかちょっとモヤモヤするなあ。

(追記) よく見たら問題分の方で k は 2 以上になっていた。問題文を微妙に見落としているのは良くない。

Go の名前付き返り値

Go の名前付き返り値の扱いでちょっと迷ったのでメモ。

名前付き返り値を使うとローカル変数扱いにされるとはわかっていた。 return文で新しいインスタンスを作って返した場合もちゃんとケアされるか不安だった。 仕様見ても明記されている箇所が見つけられずよくわからんかったし。

で下のようなコードで確認してみると杞憂だったのがわかった。よかったね。 どうもreturn文の時点で名前付き返り値に代入されるようなイメージで良いらしい。

package main

import (
    "errors"
    "fmt"
)

func f1() (err error) {
    return errors.New("hoge")   
}

func f2() (err error) {
    defer func(){
        err = errors.New("huga")
    }()
    return errors.New("hoge")   
}

func f3() (err error) {
    defer func(){
        err = errors.New("huga")
    }()
    err = errors.New("hoge")
    return err
}

func main() {
    fmt.Println("Hello, playground")
    fmt.Printf("f1: %v\n", f1()) // hoge
    fmt.Printf("f2: %v\n", f2()) // huga
    fmt.Printf("f3: %v\n", f3()) // huga
}

Go で後処理が必須になる場合の API

datastore/sqlRowsQuery で取ってきた後に Close() を呼び出さないといけない。これはまあ常識。

で、恥ずかしい話だが、最近自分が書いたコードでこのCloseし忘れをやってしまっていた。

おそらく原因としては Exec から Query機械的に変換したときにCloseを付けるのを忘れてたのだと思う。自分はこのパターンで何かしらの処理を付け忘れてしまうことが多い。

しかし人が頑張って Close を書くようにするのではヒューマンエラーがいつか出るのは確実だ。 なので、できれば Go でこういう Close し忘れは検知してもらいたい。

残念ながらそういうことをしてくれるツールを見つけられなかったので、問題を解決するのに次のようなAPIを考えてみた。

resource, close, err := something.Open()
defer close()

後処理が必要なリソースを確保する場合には、確保時に終了処理となる関数を返すのがいいのでは?というアイディアだ。 終了処理となる関数をローカル変数に束縛しておけば、これを呼び出さない場合に Go 側で「未使用の変数がある」と検知してくれるはず。 握り潰しそうとした場合もコード上でわかりやすくなるはず。

という感じのことを自作 API ではやろうと思うのだがどうなんだろうか?

こういうことをしているベストプラクティス見つからないので、それほど良さげな解決策ではないのかも。

AtCoder Beginner Contest 151

Contest Result - AtCoder

今回は A から C まで。ランクも下がった。

どちらかというと今回は解けたという話でなく、どうして解けなかったか?という話になる。 普段は競技プログラミングで点が取れなかった話は振り返ってみても役に立たないので書かないが、 今回は教訓を見出したので自戒を込めてブログ記事にしている。

で、

その解けなかったのは D で、与えられた迷路に対して適当な始点と終点を与えて最短パスを最長にする、というような問題だった。

問題サイズは割と小さかったので、総当りで始点を設定して BFS で最も遠い点を出せばいいかと考えた。 ただ実行時間はなるべく短くしたかったので、始点からは次の条件を満たすものを除外することにした。

  • 上下の点が通行可能
  • 左右の点が通行可能

要するに通路のあたるような点は始点終点から外そうとした。 これは割ともっともらしい。最短パスが最長になる始点終点はなにかしら端のほうになりそうだ。

ということで実装をして提出してみたのだが、最後の1ケースだけ WA になるという残念な結果になってしまった。 コンテスト時間中はなにかしら問題文で見落とした箇所があったのかとか、特殊なケースがあったりするのか、など考えていたが、 なんのことはない、上に述べた除外している箇所を外すだけでうまく動いたのだった。

これに気付いた後で、そのケースを考えてみると次のようなものがあった。

 ■■■■■
 ■□□□■
 ■□■□■
 ■□□□■
 ■■□■■
 ■□□□■
 ■□■□■
 ■□□□■
 ■■■■■

このような8の字型の迷路だと、8の上側の通路と下側の通路を指定すると最短経路が最長になる。

なにが悪かったか?

明らかに余計な条件を加えたのがよろしくなかった。

高速化の鉄則として、

まず正しく動くものをつくり、それから最適化する

というのがある。これこそなにより自分が気を付けなければいけなかったことで、競技プログラミングであってもこの鉄則に従わなかったのは申し訳がたたない。

「高速化する」というのは競技プログラミングの上でももっともらしく聞こえるが、まず正解を出すのが最優先だ。 そもそも速くなるケースは限られるという時点で、最も時間がかかるテストケースが投げられてくる競技プログラミングへの解答としては不適切であったし、今回のようにパッと思いつかないようなレアケースに足を引っ張られることもある。

教訓としては、総当りでいくと決めたら変に高速化を目指さない、ということになるか。TLE になってから考えればよいし、焼け石に水的な高速化はおそらく間違いの場合が多い。