Python > 競技プログラミング対応

入力

通常、入力は str 形式で認識されるので、変換は必要。入力後の処理に関しては、色々記事あり。

複数行入力

例題で自分のプログラムを評価する際には、複数行を入力するのが手間なので、コピペでテストしたい場合が多いが、input()のままでは複数行の入力ができない。

通常コンソールの場合

いわゆるコマンドライン
import sys
a1 = sys.stdin.readline()
a2 = sys.stdin.readline()
で一行ずつ読み取っている状態になる。この場合は input() を使っているのと同じ状態

Spyder

初期状態では、IPythonコンソールが表示されており、ここに複数行の入力をペーストした場合は、split("\n")で改行コードごとに分解すれば、一行ずつにできる。
ただし、ここから1行ごとに入力を使おうとすると、先頭を読み取っては削除(pop(0))などする必要があり、多分実行速度が遅くなる(気がする)。

ツール→設定→実行 から、コンソールを「外部システムコンソールで実行」に変更することで、上記の通常コンソールの場合のように実行できる。ただし、自動的にコンソールが閉じるわけで無いので、毎回 Ctrl + Z か exit() で最後に閉じる必要はある。切り替えるのは結構面倒。

iPython, Jupyter Notebook の場合

これがよくわからない。いわゆる stdin が効かない。input() で一行ずつ読み取るしかないか。


入れ替えを伴う文字列を扱う場合

文字をクエリに従って入れ替えたりする場合、文字列はイミュータブルなので部分的な書き換えができない。別の情報として持つことができない場合にはどうしても文字列の再構築が必要になる。そこで
S_before = input()  # abcdefg
S_after = [*input()]  #  ['a','b','c','d','e','f','g']
と分解して持たせると、それぞれの文字は上書き可能となる


モジュールを使おう

  • 結果の数え上げ Counter() (from collections import Counter)
  • キュー : deque
  • 階乗(組み合わせ) : math.factorial

設定しよう

  • 再帰呼出しの回数
    • sys.setrecursionlimit(2000)

アルゴリズム 出題と参考

ダイクストラ法

ABC-141-D
ABC-164-E
AOJ-GRL-1-A

ベルマン・フォード法


ワーシャル-フロイド法

全点対間最短路。Vが少ない場合。
AOJ-GRL-1-C
https://proc-cpuinfo.fixstars.com/2015/11/all-pair-shortest-path-html/

Binary Indexed Tree(BIT), Fenwick Tree

部分和を求める
ABC-163-F, ABC-156-F?
ビット積の話とか、 i += i&-i の意味とか、プログラムからはピンと来なかった。


セグメント木

ABC-158-F
この辺がわかりやすかったかなぁ。
https://algo-logic.info/segment-tree/

C++ での解説に慣れる

#define
: 読み替え
sort : どこからどこまでの範囲を並べ替える、という指定ができる。vector 型にも.first(), .end() という関数がある。
https://ja.cppreference.com/w/cpp/algorithm/sort
vector : 配列の拡張版 -> deque とか

auto : 自動で型付けができたのか。。。 C++ 11から => 気にしない
[&] : lambda式、lambda って書くんじゃないんだ。また、& でスコープ外の変数にアクセスできるようになる。 => lambda
https://snuke.hatenablog.com/entry/2015/12/06/005054

& 参照渡し。値渡し/ポインタ渡し/参照渡し、の参照渡し。ポインタ渡しと参照渡しの差がいまいち。。。

  • グローバル変数が自然と初期化される?
    • int型なら 0

前置インクリメント と 後置インクリメント
https://qiita.com/suuungwoo/items/e054fdcb5a4805bb226b

template

最終更新:2020年08月11日 11:58