2021-01-31

競プロ練習記録（ABC189、ABC190など）

ABC190に参加した。その前に練習で ABC189もやっておいた。ABCトーナメントに参加するのが主要な動機。練習自体には、多少慣れた以上はあまり意味がなかったが、python のTLE対策に関してはいくらか知見を得た。

コードテストについて

実行時間的に間に合うかどうか微妙な時は高速化する必要がある。その場合、

闇雲に高速化する。
コードテストでパフォーマンスをチェックしながら確認する。

の二通りの選択肢がある。最悪ケースが簡単に作れる場合は迷わずに 2. の選択肢を選ぶが、そうでない場合は 2. ができるように入力を作るのが億劫で 1. で無理やり何とかしてみようとすることが多かった。

しかし、そんなに億劫がる必要はない気もする。

例えば、今回最初にTLEした

Submission #19812154 - AtCoder Beginner Contest 190

の場合、入力部分は

N,M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
K = int(input())
cs = [int(s)-1 for s in input().split()]

となる。これを大きな入力についてテストしようとすると、例えば

if 0:
    N,M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edges[a].append(b)
        edges[b].append(a)
    K = int(input())
    cs = [int(s)-1 for s in input().split()]


if 1:
    N,M = 10**5, 10**5
    edges = [[] for _ in range(N)]
    for i in range(M):
        a,b = i,(i+1)%N
        edges[a].append(b)
        edges[b].append(a)
    K = 17
    cs = [s**3 for s in range(K)]

となるが、コピーペーストで被る部分の多さを考えると、実は大した労力ではなさそうだ(５分もあれば十分？)。

結論：TLEチェック用の入力を自作するのは実はそこまで手間がかからない。闇雲に高速化を試みるより、はるかにまし。

入出力について

import sys
input = lambda: sys.stdin.readline().rstrip()

とするだけで爆速になる。早速、atcoder-toolsの「# Failed to predict input format」部分に追加した。

PyPy3で提出

atcodertools/common/language/.py の PYTHON部分で該当箇所を、 submission_lang_pattern=re.compile("^PyPy3.*"),

に書き換えた。これで、atcoder-tools submit したときにPyPy3で提出してくれるようになった。

消費時間

全体では６〜８時間ぐらい使ったように思う。しかし、今回のABC練習は基本的にABCトーナメントをより楽しむためのもので、レート向上を目指したものではない。TLE原因の調査などはレート向上を目的としたものなので、だいたい３時間ぐらいをレート向上のための消費時間として計上するのが妥当か。このあたりはルール曖昧だが。

今回の消費時間：3時間

今年の消費時間：17時間

2021-01-17

競プロ練習記録(キーエンスプログラミングコンテスト 2021)

キーエンスプログラミングコンテスト 2021に参加した。

ARC級コンテストはおそらくレート期待値<現在のレートなので、参加するのはレート的に損だと思ったが、折角なので参加した。

また、コンテスト前に、E - Wandering TKHS (まだ途中)を考えたり、環境整備したりした。

結果

ABCD の4完で238位レーティング：2534→2503 (-31)

A,B ・・・特になし
C・・・落ち着いてできなかった。途中で勘違いに気付いた時に小手先の修正だけで何とかしようとして余計に被害を広げてしまった。そんなときこそ落ち着くのが大事。
D・・・今回はたまたま思いついたが・・・。若干運任せなところがある。

E問題について

解説を読んで完全に理解したが、この方針を確実に思いつくプロセスを確立できていない。

方針を思いつくための方針論を、後日考察したい。

TODO

E - Wandering TKHS の研究
E - Greedy Ant の研究

消費時間

今回の消費時間：3時間

今年の消費時間：14時間

2021-01-16

競プロ練習記録（簡単めの問題、実装なし）

前回の練習で典型力が足りないと考えたため、問題をたくさん見てみることにした。

やったこと

AtCoder Problems 上でdifficulty 1200 〜1999 の 2018年の問題（全部で40問強ぐらい）を、一問5分程度を目安に頭の中で方針だけ考えるということを、何日かに分けて行った。

結果

難易度1200〜1599の問題については成果なし。5分以内に思いついた問題がほとんどで、苦労した問題はなし。

難易度1600〜1999では、短時間では方針が浮かばなかった問題は次の1問だった。

C - String Coloring これは、半分全列挙が想定解。列の長さが36というだけで指数関数時間アルゴリズムを方針から外してしまった。

あと、間違えてしまったのは次の二問。

まとめ

苦労したARC111のB問題が diffiiculty1300 ほどなので、その点数帯の問題をたくさん当たれば、苦手がつぶせると期待したが、その当ては外れてしまった。

ただし、頭を慣らすには良さそうなので同様の作業をコンテスト直前にするのはありかもしれない。

おそらく見逃している典型がまだまだあると思うが、割合的には少ないだろうし、発見するのにも時間がかかる。この方向性は辞めてもっと考察が重い問題を練習した方が効率が良さそう。

今回の消費時間：5時間ぐらい

今年の消費時間：11時間ぐらい

あと、ACLライブラリを見てみたり、segment treeに関する理解を深めるなどもしたが、これは競プロ本位の勉強じゃないので、上の時間にはノーカウントとした。

2021-01-12

競プロ練習記録(ARC111)

ARC111のA~Eで練習。

各問題について

A

特になし。

B

カードを辺と思う発想はなかった。もう少し知識を広げて、典型と感じれる範囲を増やした方がいいかも。

C

特になし。

D

前回の反省でpythonの再帰を使うべきじゃないと書いたのに、この問題ではむしろ再帰を使わないと厳しかった。

E

解説を見るに、floor_sum を知らないと厳しい問題っぽい。知識が不足している。

総合的な反省点

考えてる途中、割とぼーっとしがち。集中し続けることの難しさを痛感する。
十分に方針を固めてから実装しないと、かえって時間がかかる。
典型力(?)が足りていない。大量に問題を見た方が良さそう。
ACLは、確認しておいた方が良さそう。

今回の消費時間：約3時間

今年の消費時間：約6時間

集中力が足りてない。今回の練習効率はあまり良くなかった。

2021-01-03

競プロ練習記録（ABC187、環境整備など）

開催してたABC187で録画しながら練習した。

Eで詰まったので途中で切り上げて、録画の分析。

観察したこと

テストや提出をするための作業に一問60〜90秒ほど使っている。これは、コンテスト時間の10％ほどを占めうるので、自動化するメリットはそれなりに大きそう。
ケアレスミスによるタイムロスは想像以上に大きい。思った以上に確実性を優先した方が良さそう。
pythonで再帰は絶対ダメ。スタックを使う。

環境の整備

上記を踏まえ、環境を整備した。具体的にはatcoder-toolsをインストール。

~/.atcodertools.tomlを作成し、以下のようにした。

[codestyle]
indent_type='space' # 'tab' or 'space'
indent_width=4
#template_file='~/my_template.cpp'
workspace_dir='~/atcoder-workspace/'
lang='python' # Check README.md for the supported languages.
#code_generator_file="~/custom_code_generator.py"
[postprocess]
exec_on_each_problem_dir='clang-format -i ./*.cpp'
exec_on_contest_dir='touch CMakeLists.txt'

[etc]
download_without_login=false
parallel_download=false
save_no_session_cache=false
in_example_format="in_{}.txt"
out_example_format="out_{}.txt"

また、バグがあってsubmit出来なかったので

Fix #204 Submission language pattern for python was no longer matchin… by kyasbal-1994 · Pull Request #208 · kyuridenamida/atcoder-tools · GitHub

に従い、修正。

以上の作業で動くようになった。

今回の消費時間は全部で3時間ほど。

2021-01-01

2021年の競技プログラミングの目標

最近は、惰性で競技プログラミングをしていてあまり良くないなと思ったので、今年は目標を立てることにしました。

目標

今年の目標は

「出来るだけ少ない消費時間でAtCoder赤になる」

とします。

消費時間というのはコンテスト参加時間や練習、解説を読むなど、レートを上げるための作業全般に使う時間とします。

現状

私は、5~10年ほど前は割と熱心にやってましたが、最近は全然です。

私の現在のレートは2534で、2800から赤コーダーなので、あと300弱上げる必要があります。

これがどの程度の難易度かはあまり検討がついていません。

アクティブユーザのみのランキングでは、私は現在264位で、144位からが赤なので人数的には半分ほどですが果たして。

目標の詳細

とりあえず、競プロ（Heuristics系のコンテストを除く）に使った時間は大まかにでも記録しておこうと思っています。

目標としては出来れば50時間以内で達成したいです。

150時間以上は絶対に使わないようにします（150時間使っても赤コーダーになれなかった場合は、その時点で諦める）。

2016-09-03

やねうら王ver3.57　USER_ENGINEのコンパイルで躓いたのでメモ

c/c++初心者の自分が、やねうら王のコンパイルで躓いたが、解決できたのでメモ。

最初にしたこと。

Visual c++2015をダウンロード。
やねうら王ver3.57(2016年9月2日時点での最新版)をgithubからダウンロード。
やねうら王のプロジェクトファイル（YaneuraOu.sln）を開く。
shogi.h を開いて、思考エンジンを USER_ENGINEに変更。
extra/config.h を開いてターゲットCPUをNO_SSEに変更
ビルドを実行

すると次のようなエラーがでてコンパイルに失敗した。

...
1>evaluate_bona_piece.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>evaluate_kpp.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>evaluate_material.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>book.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>misc.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>movegen.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>shogi.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>position.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>thread.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>usi.obj : error LNK2005: "int __cdecl Eval::calc_check_sum(void)" (?calc_check_sum@Eval@@YAHXZ) already defined in user-search.obj
1>..\..\YaneuraOu2016Engine\YaneuraOu.exe : fatal error LNK1169: one or more multiply defined symbols found
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

いつもなら、ここで心が折れるところだが、少し頑張ってみることに。ネットで検索して調べてみたところ、どうやらEval::calc_check_sum(void)が、多重に定義されててリンカーがエラーを起こしているらしい？よく分からん。

ソースコードを検索してみると、calc_check_sum(void)の定義らしきものは evaluate.h と evaluate_kppt.cppに書かれているようだ。

さらにネットで調べてたら、headerファイルに関数の定義を書くべきではない的なことが書いてある。

evaluate.h のソースコードの39〜47行目を見ると次のように書いてある。

  // 評価関数パラメーターのチェックサムを返す。
  s32 calc_check_sum()
#if defined(EVAL_KPPT) || defined(EVAL_KPPT_FAST)
	  ;
#else
  {
	  return 0;
  }
#endif

今は#if内は無視されているので

  s32 calc_check_sum()
  {
	  return 0;
  }

こうなる。これって、ネットに書いてあった、ヘッダに関数定義を書いたらリンカーでエラーになるという状況そのものだ。

しかし、おかしい。

ヘッダーに関数定義を書くとエラーが出るらしい。
ヘッダーに関数定義が書いてある。
よってエラーが出る。

というステップは理解したが、それなら何故ヘッダーに関数定義が書いてあるのか訳がわからない。それに、ヘッダー内で関数定義されている箇所は他にもある。そこでは何故エラーが出ないのか？

更にネットで調べてみたが、どうやら関数がコンパイラーによってinline展開されている場合は、リンカーのエラーは起きないようだ。よって、コンパイラーによって自動的にインライン展開されるような単純な関数はヘッダーに定義を書いてもいいようだ。

そこでさっきの部分を次のように変更した。

  // 評価関数パラメーターのチェックサムを返す。
#if defined(EVAL_KPPT) || defined(EVAL_KPPT_FAST)
  s32 calc_check_sum();
#else
  inline s32 calc_check_sum() {
	  return 0;
  }
#endif

これでようやく実行ファイルの生成に成功した。