суббота, 18 июня 2016 г.

Сокращение кода на Python для acmp.ru


ПОСЛЕДНЕЕ ОБНОВЛЕНИЕ: 24.01.2017
Существенно обновленные пункты:
6. Логические операторы: Добавлено использование min от пустых коллекций (3 абзац).
18. eval/exec: Добавлено про парсинг float (3 абзац).
19. map, zip: Добавлены краткие реализации без zip (1 и 2 абзацы).
Новые пункты:
28. Оператор **
31. Стек через односвязный список
32. Одномерные массивы вместо двумерных
33. Регулярные выражения

Предисловие

Добрый день.
Меня зовут Хворых Павел, и я сокращаю задачи на acmp.ru. Долгое время я занимался этим делом на C++ и накопил изрядное количество интересных приёмов, которые и изложил в предыдущей статье. Однако в мае 2015 администратор сайта революционно обновил сайт, добавив новые языки и обновив старые (что очень круто), и сбросил все топы (что вообще не круто). В связи с этим я решил перейти на Python (который, кстати, на данный момент является самым кратким языком в системе). Об обнаруженных мною способах сокращения кода на Python я и расскажу далее.

Однако сначала требуется обговорить ряд моментов.
  1. На acmp используется CPython 3.4.3. Далее под Python я буду подразумевать именно эту реализацию Python.
  2. Основы Python читателю предлагается изучить самостоятельно, объяснять я их не буду.
  3. У некоторых терминов Python очень туго с переводом на русский: либо общепринятого перевода вообще нет, либо он недостаточно краткий, либо он спорен. Поэтому для некоторых понятий я просто буду использовать англоязычные термины.
  4. Python является интерпретируемым языком. Это даёт ему мощь и краткость, однако из-за этого он работает ГОРАЗДО медленнее. Если для C++ примерной оценкой производительности является 109 операций в секунду, то Python осуществляет примерно 107 операций в секунду. Более того, Python фактически не производит оптимизаций и при написании эффективного кода необходимо знать некоторые принципы. Поэтому сдать некоторые задачи на Python фактически невозможно.
  5. Неопределенные фрагменты кода (например, тела циклов) будут опускаться, вместо них будут писаться многоточие.
  6. Ну и повторю традиционное предостережение: не используйте приёмы сокращения на практике!

Общие советы

В прошлой статье я описал несколько приёмов, применимых также и для Python. Большая часть их достаточно очевидна, поэтому не буду их повторять. Разве что хотелось бы напомнить о битовой арифметике (возможно, позже я даже добавлю о ней пункт и в эту статью). А вот некоторые общие советы я всё же повторю.
  1. Основой кратчайшего кода является кратчайший алгоритм. Иногда этот кратчайший алгоритм может быть значительно медленнее, чем оптимальный, что особенно критично для Python.
  2. Не следует переусложнять свой код: никаких классов и лишних функций, никаких промежуточных переменных и комментариев, никаких __main__ и других общепринятых способов грамотного оформления кода. Отличным примером сокращенного кода является код, приведенный в примере на acmp:
    print(sum(map(int, input().split())))
    В нем нет ни одной переменной!
  3. Используйте однобуквенные переменные. Их у вас как минимум 53: 26 строчных латинских букв, 26 заглавных латинских букв и _ (символ подчеркивания). Однако переменную _ удобно использовать в случаях, когда присваиваемое/возвращаемое значение требуется проигнорировать: IDE не будет выдавать надоедливое предупреждение о неиспользованной переменной. В примерах я буду использовать её именно в таких случаях.
  4. Обращайте внимание на приоритеты операторов. Например, приоритет оператора and выше приоритета оператора or.
  5. В питоне очень много встроенных функций и типов, которые можно использовать без импорта библиотек. Обязательно просмотрите встроенные функции и методы встроенных типов (особое внимание уделите методам строк (str) и списков (list)).

Разное полезное


1 Стандартная библиотека
В Python достаточно богатая стандартная библиотека, всегда пробуйте найти в ней решения каких-то стандартных задач. Модули, которые мне доводилось использовать:
  1. re - для работы с регулярными выражениями. В Python регулярные выражения иногда являются наиболее простым и кратким способом распарсить строку либо просто что-то с ней сделать.
  2. math - математические функции, а также числа pi и e.
  3. datetime - работа с датами и временем.
  4. fractions - работа с рациональными числами. В качестве приятного бонуса содержит функцию вычисления НОД - gcd.
  5. itertools - содержит внутри себя функции генерации перестановок, сочетаний и всего такого.
К сожалению, в Python нет встроенного модуля для работы с отсортированными множествами, вместо этого предлагается использовать модули heapq (очередь с приоритетами) и bisect (бинарный поиск).

2 Длинная арифметика
В тип int встроена длинная арифметика, то есть над ним можно производить любые преобразования, не боясь вылететь за границы типа.
Однако тип float представляет собой обычные числа с плавающей запятой двойной точности (double в си-подобных языках), поэтому при преобразовании int в float длинная арифметика теряется (вплоть до того, что значение int может не влезть в float, в таком случае вылетает исключение). Для решения этой проблемы можно использовать decimal (числа с фиксированной запятой) или даже fractions (рациональные числа).

3 Операторы /, //, %
Оператор / выполняет деление без округления, возвращая float даже если аргументами были int:
10 / 4 == 2.5
11.5 / 2.5 == 4.6
4 / 2 == 2.0
Оператор // выполняет деление с округлением (целочисленное деление). Если аргументами оператора // являются float, тогда результат тоже имеет тип float, но округление все равно происходит.
10 // 4 == 2
10.0 // 4.0 == 2.0
11.5 // 2.5 == 4.0
Оператор %, возвращающий остаток от деления, ведет себя аналогично:
10 % 4 == 2
10.0 % 4.0 == 2.0
11.5 % 2.5 == 1.5

Эти операторы могут быть использованы для работы с float:
x // 1 # возвращает целую часть числа
x % 1 # возвращает дробную часть числа
К сожалению, как было сказано ранее, результатами этих операций также будет являться float, что зачастую неприемлемо (например, при выводе результата через print).

Важным отличием операторов // и % является то, что в них используется математическое определение целочисленного деления (округление вниз, остаток неотрицателен) вместо принятого в си-подобных языках деления с округлением в сторону нуля. Разница появляется только на отрицательных числах:
-15 // 4 == -4 # в си-подобных языках -3
-15 % 4 == 1 # в си-подобных языках -3
Эту особенность можно использовать для реализации деления с округлением вверх:
(n+k-1)//k # 10 символов
-n//k*-1 # 8 символов

4 Строковые литералы
Строки могут быть записаны как с помощью одиночных кавычек ('), так и двойных (") - они равнозначны:
'abc' == "abc"
Это удобно использовать, если в строке присутствуют кавычки. Их не придется экранировать, если для записи строки использовать другие кавычки:
"What's your name?" == 'What\'s your name?'

Регулярные выражения часто содержат много слэшей, которые приходится экранировать:
"(\\w)(\\w+)(\\w)"
Для таких случаев в Python есть raw strings - в них слэш интерпретируется как обычный символ, а не как символ экранирования:
r"(\w)(\w+)(\w)"

Если требуется вывести несколько строк, то может быть удобно использовать многострочные строки:
"""One string
Second string
Third string"""
Это эквивалентно
"One string\nSecond string\nThird string"
В многострочных строках можно использовать одинарные и двойные кавычки без экранирования (за исключением удивительного случая, когда потребуется три кавычки подряд, да еще и именно тех, которые открывают строку).

5 Проверка на истинность
В Python все переменные могут быть проверены на истинность (использованы в логическом контексте, например, в условии if или while):
  1. Число ложно, если оно равно 0.
  2. Строка (str) ложна, если она пуста, то есть равна "".
  3. Коллекция ложна, если она пуста. Ко встроенным коллекциям относятся списки (list), кортежи (tuple), множества (set) и словари (dict).
Например, вместо
while s>0:
    ...
    s -= 1
можно написать просто
while s:
    ...
    s -= 1

6 Логические операторы
В Python операторы and и or имеют необычное поведение:
x or y # если x истинно, то возвращает x, иначе y
x and y # если x истинно, то возвращает y, иначе x
Иногда это мешает, а в некоторых специфических случаях может быть использовано при сокращении, поэтому не забывайте эту особенность.
Классическим примером использования необычности этих операторов является реализация условного оператора:
x if c else y # 9 символов
c and x or y # 8 символов
К сожалению, эта конструкция работает некорректно, если x ложно.
Пользуясь таким приёмом, а также тем, что приоритет оператора and выше приоритета оператора or, можно конструировать нечто похожее на switch из си-подобных языков:
x>0 and 1 or x<0 and 2 or 'NO'

Также следует знать, что операторы and и or являются ленивыми, то есть второй операнд не вычисляется, если достаточно первого.
Благодаря этому вместо
if y == 0: print(x)
можно написать
y or print(x)
Тут может показаться удивительным, что мы используем результат функции print, хотя, как мы знаем, она ничего не возвращает. На самом деле, любая функция возвращает результат, и если он не написан явно, то возвращается специальный объект None (который всегда ложен).

Некоторые функции, например, min, выбрасывают исключение, если передать им пустую коллекцию. Чтобы отловить такую ситуацию, вместо явной проверки на пустоту можно использовать оператор or:
min(s) if s else -1 # 15 символов
min(s or [-1]) # 12 символов
Если в коллекции s что-то есть, то оператор or передаст в функцию min именно её. Если же она пуста, то or передаст в min список [-1], минимум которого равен -1.

7 Логические значения как числа
Класс bool является подклассом класса int, а True и False равны 1 и 0 соответственно. Единственным их отличием от чисел является переопределенный метод преобразования в строку (чтобы получалось "True" вместо "1").
Во всех остальных случаях можно использовать bool как int. Например, вместо
if x>0: s += 1 # 10 символов
можно написать
s += x>0 # 6 символов

Этот приём также используется для реализации функции cmp:
(a>b)-(a<b) # 1, если a>b; 0, если a == b; -1, если a<b

В некоторых задачах возникает необходимость вывести -1, если некоторое условие не выполняется:
a<0 and x or -1 # 11 символов
Это можно записать короче:
-(a>=0) or x # 10 символов
Аналогично, пример из предыдущего пункта может быть сокращен на один символ заменой x>0 and 1 на +(x>0).

8 Операторы сравнения
Операторы сравнения (<, >, ==, <=, >=, !=, in, not in, is, not is) могут быть сцеплены в одну конструкцию, например, 0 < a < b < c. Эта конструкция эквивалентна 0 < a and a < b and b < c за тем исключением, что переменные a и b появляются и вычисляются всего один раз (а значит можно написать 0 < int(input()) < 3).

Сцепку сравнений очень удобно использовать для замены оператора and:
x > 0 and y > 0 # 9 символов
x > 0 < y # 5 символов

x > 2 and y > 4 # 9 символов
x > 2 < 4 < y # 7 символов

Сцепка операторов является ленивой и выполняется слева направо до тех пор, пока результат не будет ясен. Это позволяет использовать её в качестве условного оператора: например, вместо
if x < y: print(z) # 14 символов
можно написать
x < y is print(z) # 13 символов
Сравнение y is print(z), а значит и сама функция print(z), вызовется только в том случае, если x<y. Ну а оператор is определен для любых объектов, включая возвращаемый функцией print объект None, поэтому эта конструкция не вызывает Runtime Error.

9 Циклы
При написании циклов в Python принято использовать range:
for i in range(n):
    ...
# 15 символов
В приведенном примере i пробегает от 0 до n-1. Однако такой вариант требуется далеко не всегда. Очень часто нам вообще не нужен индекс текущей итерации либо нас вполне устроит, если эти индексы будут идти по убыванию. В таких случаях выгодно написать цикл вручную через while. Рассмотрим несколько распространенных случаев.
  1. Цикл i = 1...n.
    С range:
    for i in range(1, n+1):
        ...
    # 19 символов
    Вручную:
    i = 0
    while i<n:
        i += 1
        ...
    # 16 символов
  2. Цикл i = n...1.
    С range:
    for i in range(n, 0, -1):
        ...
    # 20 символов
    Вручную:
    i = n
    while i:
        ...
        i -= 1
    # 14 символов
  3. Цикл i = n-1...0.
    С range:
    for i in range(n-1, -1, -1):
        ...
    # 23 символа
    Вручную:
    i = n
    while i:
        i -= 1
        ...
    # 14 символов

Для убывающих циклов (2 и 3 случай) существует дополнительная оптимизация: если после цикла больше нигде не требуется переменная n, то можно не тратить три символа на создание переменной i, а итерироваться непосредственно с помощью переменной n.

10 Умножение на число
В Python для многих типов определена операция умножения на число:
"abc" * 3 == "abcabcabc"
[1, 2, 3] * 2 == [1, 2, 3, 1, 2, 3]
(1, 2, 3) * 2 == (1, 2, 3, 1, 2, 3)
Что приятно, при умножении на отрицательное число получается просто пустая коллекция.
Есть два классических примера применения данного приёма:
  1. Иногда требуется создать копию списка, однако списки в Python являются ссылочными типами и операция y=x не создает копию списка: переменные x и y просто будут указывать на один и тот же список. Операция умножения на число решает эту проблему: y=x*1.
  2. Пусть нам требуется осуществить n однотипных итераций, например, прочитать n строк, причем нам не требуется знать номер текущей итерации. Из уже известных из предыдущего пункта способов кратчайшим является убывающий цикл:
    while n:
        ...
        n -= 1
    # 11 символов
    Однако в этом случае мы портим переменную n и если этого необходимо этого избежать, приходится тратить еще 3 символа на создание временной переменной. Операция умножения на число позволяет избежать этой проблемы:
    for _ in ' ' * n:
        ...
    # 11 символов
    Если необходимо проделать 2*n итераций, то вместо естественного ' ' * 2*n можно написать ' '*n.
    Иногда бывают случаи, когда n заранее известно. В этом случае можно сократить код еще сильнее. Например, следующий код проделает ровно 4 итерации:
    for _ in '    ':
        ...
    # 9 символов

11 Цикл с индексом
Иногда требуется пройтись по строке/списку в цикле, зная при этом индекс текущего элемента. В Python это принято делать так:
for i, x in enumerate(m):
    ...
# 21 символов
Но можно сделать гораздо короче:
i = 0
for x in m:
    ...
    i += 1
# 15 символов

12 Условный оператор
Python предлагает нам ужасно многословный тернарный условный оператор:
x if c else y # 9 символов
Есть несколько вариантов решения проблемы.
  1. c and x or y # 8 символов
    Как упоминалось ранее, этот вариант не работает, если x может быть ложно. Такое бывает относительно редко, но всё же бывает, поэтому следует быть очень внимательным.
  2. [y,x][c] # 8 символов
    Этот вариант работает только если c является логическим выражением или числом 0/1.
  3. c*x or y # 6 символов
    Переменная x должна быть истинна, для неё должно быть определено умножение на число (то есть она должна быть числом, строкой, списком или кортежем). Но самой большой проблемой этого варианта является то, что переменная c должна быть числом 0/1 либо булевой переменной, что получается крайне редко. При попытке использовать вместо c логическое выражение возникает необходимость поставить вокруг него скобки, что увеличивает количество символов до 8.
    Есть несколько случаев, когда данную проблему можно решить: если известно, что n - целое положительное число, то условие n==1 можно заменить на 1//n, а условие n>1 - на 1%n; если n - неотрицательное число, то условие n==0 можно заменить на 0**n.

13 Немного теории: итераторы и итерируемые объекты
Итератор - это объект, который последовательно возвращает некоторые элементы. Итерируемый объект (iterable) - это объект, у которого мы можем получить итератор. Всё это можно рассматривать так: итерируемый объект представляет собой некую последовательность элементов, которую мы можем обойти с помощью итератора.
К итерируемым объектам относятся строки, встроенные коллекции (кортежи, списки, множества, словари), объекты определенных классов (например, файлы) и даже сами итераторы.
Для работы с итерируемыми объектами предназначена конструкция for X in Y: она запрашивает итератор у Y и поочередно получает из этого итератора элементы, подставляя их вместо X.
Большое количество функций (например, sum, max, all, sorted) могут принимать не только списки, но и произвольные итерируемые объекты, что открывает широкие возможности для сокращения (некоторые из них будут рассматриваться в последующих пунктах).
Некоторые функции (например, zip и map) возвращают итераторы, поэтому необходимо понимать следующую их особенность: итератор является "одноразовым" объектом, то есть из него можно получить последовательность элементов только один раз. При попытке повторного обхода он сразу сообщит, что элементов больше нет. С таким поведением можно было столкнуться при использовании функции map:
a = map(int, ["1", "2", "3"])
print(sum(a)) # 6
print(sum(a)) # 0
Функция range возвращает итерируемый объект, а не итератор, поэтому его можно обходить несколько раз:
a = range(4)
print(sum(a)) # 6
print(sum(a)) # 6

14 Генераторы
В Python есть специальный синтаксис для создания некоторых итерируемых объектов:
# генератор списков (list comprehension)
[expr for_comprehension] # порождает список

# выражение-генератор (generator expression)
(expr for_comprehension) # порождает итератор

# генератор множеств (set comprehension)
{expr for_comprehension} # порождает множество

# генератор словарей (dict comprehension)
{expr:expr for_comprehension} # порождает словарь
expr - это произвольное выражение; for_comprehension - это несколько записанных подряд for-выражений (for ... in ...) и if-выражений (if ...), причем первым выражением обязательно должно быть for-выражение. Чаще всего for_comprehension состоит просто из одного for-выражения.
Приведем несколько примеров, чтобы всё стало понятно:
[x*x for x in range(5)] # порождает список [0, 1, 4, 9, 16]
[x for x in range(10) if x%2 == 1] # порождает список [1, 3, 5, 7, 9]
{x:x*x for x in range(5)} # порождает словарь {0:0, 1:1, 2:4, 3:9, 4:16}
[x+y for x in "abc" for y in "xy"] # порождает список ["ax", "ay", "bx", "by", "cx", "cy"]
А теперь более полезные примеры:
s = [input() for _ in ' ' * n] # прочитать n строк
u = [x for x in u if x != n] # удалить из u все вхождения элемента n

Если выражение-генератор передать в функцию единственным аргументом, то образуется две пары круглых скобок:
all((x>0 for x in m)) # все элементы m положительны?
Специально в таком случае разрешено опускать одну из пар:
all(x>0 for x in m) # эквивалентно предыдущему выражению

15 Кортежи
Выражение, где несколько выражений стоят через запятую, автоматически формируется в кортеж:
x = 2, 3+6, 42 # x - кортеж из трёх элементов: 2, 9 и 42
y = 2, # y - кортеж из одного элемента 2
Поскольку кортеж является итерируемым объектом, то можно использовать это выражение в инструкции for, когда требуется выполнить одну и ту же операцию для нескольких значений:
for x in 1, -1: ...
Если в range используется небольшая заранее известная константа, то короче будет выписать требуемые значения явно:
for i in range(4): ... # 15 символов
for i in 0,1,2,3: ... # 14 символов

16 Присваивание
Рассмотрим интересную форму оператора присваивания, которая выглядит следующим образом:
target_list = iterable
target_list - это последовательность выражений, разделенных запятыми; iterable - произвольный итерируемый объект.
Последовательность выражений target_list может состоять даже из одного элемента, но в этом случае надо обязательно поставить после этого элемента запятую.
При таком присваивании элементы iterable присваиваются соответствующим элементам target_list. Разумеется, количество элементов в target_list должно быть равно количеству элементов в iterable.
a, b, c = x, y, z # a = x, b = y, c = z
a, b, c = "xyz" # a = "x", b = "y", c = "z"
a, b, c = range(3) # a = 0, b = 1, c = 2
a, = [1] # a = 1
a, b = b, a # меняем значения переменных a и b местами
a, b = b, a+b # казалось бы, причём тут Фибоначчи

Перед одним из элементов target_list может стоять звёздочка. Этот элемент станет списком из значений, которые не влезли в другие элементы target_list. Проще всего объяснить это примером:
a, b, *c, d, e = 1, 2, 3, 4, 5, 6, 7 # a = 1, b = 2, c = [3, 4, 5], d = 6, e = 7
Важно понять, что помеченная звездочкой переменная будет списком вне зависимости от типа iterable и от того, сколько в неё прилетает значений:
a, b, *c, d, e = 1, 2, 3, 4 # a = 1, b = 2, c = [], d = 3, e = 4
a, b, *c, d, e = 1, 2, 3, 4, 5 # a = 1, b = 2, c = [3], d = 4, e = 5
a, b, *c, d, e = "1234567" # a = "1", b = "2", c = ["3", "4", "5"], d = "6", e = "7"
Звёздочка очень полезна для сокращения, несколько полезных приёмов мы рассмотрим позже.

Элементом target_list может быть не только переменная, но и любое выражение, которому можно что-то присвоить: элемент коллекции, получаемый по индексу; срез (о них мы поговорим позже) или даже другой target_list (тогда его надо заключить в круглые или квадратные скобки):
a, (b, c), d = "12", "34", "56" # a = "12", b = "3", c = "4", d = "56"
Разумеется, во вложенном target_list также может присутствовать звёздочка:
(*a,), *b = "123", "456", "789" # a = ["1", "2", "3"], b = ["456", "789"]

17 Итератор в список
При необходимости прочитать последовательность чисел хочется написать следующий код:
u = map(int, input().split())
Проблема в том, что map возвращает итератор, который разрешает только пробежаться по полученной последовательности чисел, причем всего один раз. В более сложных случаях приходится явно преобразовывать итератор в список:
u = list(map(int, input().split())) # 32 символа
В таком случае можно использовать генератор списков вместо map:
u = [int(x) for x in input().split()] # 31 символ
Однако звёздочка решает эту проблему короче:
*u, = map(int, input().split()) # 28 символов

18 eval/exec
Функция eval принимает строку и интерпретирует её как произвольное выражение Python, возвращая полученный результат.
Это позволяет нестандартными способами решать некоторые задачи: вместо того, чтобы парсить считанную строку и производить некоторые вычисления с полученными данными (как и подразумевалось автором задачи), можно модифицировать саму строку, чтобы она обрела корректный Python-синтаксис и про-eval-ить её.
Рассмотрим простой пример: в единственной строке находится два числа и требуется поделить первое на второе нацело.
Обычное решение этой задачи:
a, b = map(int, input().split())
print(a//b)
# 39 символов
Решение с помощью eval:
print(eval(input().replace(' ', '//')))
# 37 символов
Достаточно часто в строках бывают лишние пробелы и replace выдаёт некорректную строку. Иногда справиться с этим помогает опциональный параметр count метода replace, задающий максимальное количество замен:
print(eval(input().replace(' ', '//', 1))) # заменяем только первый пробел

Другим популярным применением функции eval является повторение одной инструкции. Рассмотрим некоторые интересные случаи.
  1. Прочитать n строк:
    s = [input() for _ in ' '*n] # 21 символ
    s = eval('input(),' * n) # 20 символов
  2. Создать двухмерный массив (матрицу):
    s = [[0] * n for _ in ' ' * n] # 19 символов
    s = eval('[0] * n,' * n) # 18 символов
При такой замене s получается кортежем вместо списка. Это редко бывает важно, однако ограничения всё же накладывает: например, во втором примере это ведёт к тому, что мы не можем заменить строку матрицы другим списком (сами элементы строк менять можно, разумеется).

Для парсинга дробных чисел используется float:
float('2.4') == 2.4
Однако функция eval короче на один символ:
eval('2.4') == 2.4
Приятный бонус: если входное число было без точки, то оно распарсится как int. Это бывает полезно при парсинге группы чисел, в которых целые и дробные перемешаны:
n, *m = map(eval, '2 2.4 3.6'.split()) # n == 2 (целое), m == [2.4, 3.6] (дробные)

Функция exec, в отличие от eval, позволяет интерпретировать произвольный код. На практике может быть применена только в специфических случаях.

19 map, zip
Функция map может принимать несколько итерируемых объектов:
map(max, [1, 20, 3], [10, 2, 30]) # 10, 20, 30
Функция zip позволяет работать с несколькими итерируемыми объектами параллельно:
for a, b in zip(A, B): ...
Например, с его помощью можно сгруппировать элементы списка попарно:
for x, y in zip(s[::2], s[1::2]): ... # 28 символов
Если s представляет собой итератор (например, является результатом вызова функции map), то, благодаря одноразовости извлечения каждого элемента из итератора, выражение упрощается до
for x, y in zip(s, s): ...
Более того, с помощью функции iter мы можем получить итератор у любого итерируемого объекта (например, списка) s:
k = iter(s)
for x, y in zip(k, k): ...
# 26 символов 
В случае, когда необходимо разбивать не на пары, а на тройки, становится выгодно использовать следующую конструкцию:
for x, y, z in zip(*[iter(s)]*3): ... 
Следует отметить, что использование zip для разбиения коллекции на группки не всегда оправдано, иногда можно использовать другой подход:
while s:
    x, y, *s = s
    ...
Этот подход имеет квадратичную сложность, поэтому не рекомендуется для применения к большим коллекциям.

Другим вариантом использования zip является перебор всех пар соседних элементов коллекции:
for x, y in zip(s, s[1:]): ...
Для этого варианта также существует краткая реализация без zip:
x, *u = u
for y in u:
    ...
    x = y

20 open
Обычно функцию open используют для открытия файлов:
f = open("input.txt") # f - объект файла, связанный с файлом input.txt
Однако если заглянуть в документацию, то можно узнать, что open умеет работать с уже открытым файлом, для этого ей надо передать дескриптор этого файла. У стандартных потоков stdin, stdout и stderr есть свои дескрипторы - 0, 1 и 2 соответственно. Следовательно, мы можем написать
f = open(0) # f - объект файла, связанный со стандартным входным потоком
и читать из стандартного входного потока, как из файла.

Объект файла является итератором, поэтому можно писать код вроде этого
for s in open(0): ... # цикл по всем строкам файла
Однако чаще всего бывает нужно просто считать весь файл:
*s, = open(0) # s - список строк файла
Достаточно часто в первой строке файла находится просто количество последующих строк. Поскольку мы и так считываем все строки, эту информацию можно проигнорировать:
_, *s = open(0) # s - список строк файла кроме первой

К сожалению, open, в отличие от input, возвращает строки с символами перевода строки (если файл не заканчивается символом перевода строки, то последняя строка без перевода). Это не имеет значения, если в строках находятся числа (ведь они всё равно будут обрабатываться методом split или функцией int, которым безразличен лишний пробельный символ). Однако если нужно работать со строками именно как со строками, то придется избавиться от лишнего символа явно (например, с помощью метода strip).

У объекта файла есть метод read, который позволяет прочитать весь файл за раз, в одну строку. Например, если файл состоит только из чисел и мы хотим все их прочитать, то можно написать
map(int, open(0).read().split())

21 Функции и методы
Функции в Python являются объектами первого класса, то есть ими можно оперировать как с обычными объектами. Поэтому мы можем передавать одни функции в качестве аргументов в другие функции (например, в map) или сохранять их в переменные:
a = input()
b = input()
# 18 символов
сокращается до
I = input
a = I()
b = I() 
# 17 символов
Методы классов на самом деле тоже являются функциями, которые первым аргументом принимают объект, у которого был вызван метод (этот аргумент принято называть self). Когда мы вызываем метод непосредственно от имени объекта, он подставляется в качестве первого аргумента автоматически: obj.func(args...) эквивалентно Type.func(obj, args...), если obj имеет тип Type.
Это всё достаточно сложно устроено, поэтому не будем углубляться в детали, а просто отметим, что выражения вида obj.func и Type.func, так же как и обычные функции, являются объектами первого класса, то есть их можно сохранять в переменные
u = str.replace
t = u(u(u(s, "a", "A"), "b", "B"), "c", "C")
и передавать в другие функции
map(str.split, open(0))
Например, таким образом можно реализовать replace для списков:
map({2:5}.get, L, L) # заменяет в списке L все вхождения 2 на 5
или найти количество несовпадающих элементов в коллекциях:
sum(map(str.__ne__, A, B)) # 24 символа
sum(a != b for a, b in zip(A, B)) # 25 символов

У встроенных типов есть большое количество перегруженных операторов (методов), благодаря которым можно на лету формировать новые функции (что бывает нужно при использовании map):
s.__eq__ # функция, сравнивающая переданный аргумент с s
1 .__add__ # функция, увеличивающая переданный аргумент на 1
Обратите внимание на пробел после 1 в последнем примере: он нужен, чтобы парсер Python воспринял цифру и точку как разные токены, а не как один токен 1. (вещественное число).

22 Множественное присваивание
Python позволяет совершать сразу несколько присваиваний одной инструкцией:
expr1 = expr2 = ... = exprN = expr
эквивалентно
temp = expr
expr1 = temp
expr2 = temp
...
exprN = temp
Приведём несколько примеров:
a = b = c = 0 # создает три переменные a, b и c, равные нулю
x = y = [] # создает две переменные x и y, указывающие на один и тот же список
*x, = *y, = map(int, "1 2 3".split()) # создает списки x = [1, 2, 3] и y = []
Разберемся в причинах столь необычного поведения последнего примера. Как следует из вышесказанного, он эквивалентен
temp = map(int, "1 2 3".split())
*x, = temp
*y, = temp
Итератор, возвращаемый функцией map, сохраняется во временную переменную temp. При выполнении первого присваивания *x, = temp выполняется пробег по итератору, то есть из него извлекаются все значения. Поэтому при выполнении второго присваивания *y, = temp итератор сразу сообщает, что он пуст, и y присваивается пустой список.

23 Работа с коллекциями
Часто требуется создать пустую коллекцию:
L = [] # пустой список
L = {} # пустой словарь
L = set() # пустое множество
Создание пустого множества занимает целых 7 символов. Однако иногда можно создать множество из одного элемента, например, если этот элемент все равно будет добавлен позже либо если он не повлияет на логику программы:
L = {0} # множество из одного элемента 0

Чтобы добавить элемент в конец списка принято использовать следующую конструкцию:
L.append(x) # 11 символов
Однако добавлять список к списку намного короче, поэтому сформируем из элемента x список и прибавим его к L:
L += [x] # 6 символов
Теперь заметим, что операция += поддерживает добавление не только списка, а вообще любого итерируемого объекта, поэтому будем добавлять кортеж вместо списка:
L += x, # 5 символов
А для добавления элемента в начало списка короче всего написать
L = [x]+L

У множеств также можно использовать перегруженные операторы вместо методов:
S |= {x} # добавить x в S
S -= {x} # удалить x из S
S -= S # очистить S
У множеств вообще много операторов, но хотелось бы упомянуть необычные операторы сравнения множеств:
A <= B # является ли A подмножеством B
A < B # является ли A подмножеством B, причем A != B
Например, их можно использовать для проверки того, что строка состоит только из заданных символов:
set(s) <= set(t) # строка s состоит только из символов строки t
В качестве обратной операции можно использовать вычитание:
set(s) - set(t) # символы строки s, не входящие в строку t
if set(s) - set(t): ... # если строка s состоит не только из символов строки t

У списков и кортежей также перегружен оператор сравнения, поэтому их можно сортировать.

У словарей есть очень полезный метод get:
D.get(x, y) # вернуть D[x], если такой элемент есть в словаре, иначе вернуть y
Если ключами словаря являются строки, то может быть короче использовать именованные аргументы (keyword arguments):
{'a':1, 'b':4, 'c':9} # 19 символов
dict(a=1, b=4, c=9) # 17 символов

Использование звёздочки позволяет нам распиливать список на части:
a, *T = L # a = L[0], T = L[1:]
*T, a = L # a = L[-1], T = L[:-1] (все элементы, кроме последнего)
Рассмотрим несколько интересных частных случаев:
# Получить последний элемент списка
a = L[-1] # 7 символов
*_, a = L # 6 символов

# Извлечь последний элемент
a = L.pop() # 9 символов
*L, a = L # 6 символов

# Извлечь первый элемент
a = L.pop(0) # 10 символов
a, *L = L # 6 символов

# Получить первый элемент списка либо y, если список пуст
a = L and L[0] or y # 13 символов
a = (L+[y])[0] # 12 символов
a, *_ = L+[y] # 10 символов
Важно отметить, что инструкции со звёздочкой создают новые списки вместо использования/модификации старых, поэтому являются неэффективными.

24 Срезы (slice)
Срезы работают для строк, списков и кортежей (причем срез строки - тоже строка, срез списка - список, срез кортежа - кортеж).
Самый известный пример применения срезов - это разворот:
m[::-1]
Благодаря этому мы можем очень кратко проверить, является ли строка палиндромом:
s == s[::-1]

В задачах часто требуется вывести ту или определенную строку в зависимости от некоторого условия. Пользуясь пунктом об условных операторах, можно предложить два разных решения:
c and 'NO' or 'YES' # 15 символов
['YES', 'NO'][c] # 15 символов
Срезы дают нам третье решение:
'YNEOS'[c::2] # 13 символов

Огромным преимуществом срезов является то, что если индексы выходят за границы коллекции, то просто возвращается пустая коллекция. Это позволяет использовать их для проверки длины коллекции в условных операторах:
if len(s) > n: ... # 11 символов
if s[n:]: ... # 8 символов
а также для безопасного извлечения символа из строки:
s[i] # если выход за границы - возникает исключение IndexError
s[i:i+1] # если выход за границы - возвращается пустая строка

Для изменяемых (mutable) коллекций (например, списков) мы можем модифицировать срезы, при этом меняться будет и исходная коллекция. Для удобства во всех примерах будем полагать A = [0, 1, 2, 3, 4].
A[i:j] = B # заменить элементы среза на элементы итерируемого объекта B
A[2:4] = 9, 8, 7 # A = [0, 1, 9, 8, 7, 4]

A[:i] += B # вставка элементов итерируемого объекта B в i-ую позицию
A[:2] += 7, 7 # A = [0, 1, 7, 7, 2, 3, 4]

A[:i] += x, # вставка элемента x в i-ую позицию 
A[:2] += 7, # A = [0, 1, 7, 2, 3, 4]

A[i:j] *= k # размножить срез в коллекции
A[2:4] *= 3 # A = [0, 1, 2, 3, 2, 3, 2, 3, 4]

del A[i:j] # удалить элементы среза из A
del A[2:4] # A = [0, 1, 4]

A[i:j:k] = B # заменить элементы среза на элементы итерируемого объекта B
             # len(A[i:j:k]) должно быть равно len(B)
A[1::2] = 9, 9 # A = [0, 9, 2, 9, 4]

del A[i:j:k] # удалить элементы среза из A
del A[::2] # A = [1, 3]

25 Вывод
Пусть требуется вывести список чисел через пробел. Наивное решение этой задачи выглядит так:
print(' '.join(map(str, m))) # 26 символов
Однако лучше написать так:
print(*m) # 9 символов
Оператор * распаковывает элементы произвольного итерируемого объекта в аргументы функции. В данном случае он распаковывает элементы списка m в функцию print, которая, как известно, выводит переданные ей аргументы через пробел.

У метода print есть параметры sep и end.
Параметр sep определяет, чем разделяются аргументы. По умолчанию sep равен пробелу.
u = [2, 3, 4]
print(*u) # выведет "2 3 4"
print(*u, sep=', ') # выведет "2, 3, 4"
Параметр end определяет, чем завершается вывод. По умолчанию end равен переводу строки.
print(s) # выведет s с переводом строки
print(s, end='') # выведет s без перевода строки
print(end=s) # выведет s без перевода строки
Обратите внимание, что sep и end должны быть строками, поэтому последний пример применим только если s является строкой.

Если вывод нетривиальный, используйте оператор % вместо ручного формирования вывода или метода format:
print("Red: ", x, ", green: ", y, ", blue: ", z, ".", sep="") # 49 символов
print("Red: {}, green: {}, blue: {}.".format(x, y, z)) # 47 символов
print("Red: %d, green: %d, blue: %d." % (x, y, z)) # 41 символ
Этот оператор может оказаться полезен даже в очень простых случаях:
'('+s+')' # 9 символов
'(%s)' % s # 8 символов 

На самом деле тестирующему серверу почти во всех задачах безразлично, какими пробельными символами и в каком количестве разделены выводимые данные. Например, если в задаче требуется вывести числа через пробел, то можно спокойно выводить каждое число в отдельной строке, используя print.

26 Оператор in
Оператор in предназначен для проверки наличия элемента в итерируемом объекте:
2 in [2, 3, 4] # True
2 in range(5) # True
Однако у него есть еще одно полезное предназначение - проверка вхождения подстроки в строку:
"bc" in "abcd" # True

27 Стандартные функции
У некоторых стандартных функций есть параметры по умолчанию, которые могут быть полезны в деле сокращения. Выше уже приводился пример функции print с параметрами sep и end. Рассмотрим еще несколько примеров:
  1. У функций min, max, sorted и метода list.sort есть опциональный параметр key. Он задаёт функцию, которая извлекает из элемента ключ, по которому и будет производится сравнение. Например, результатом min(["2", "11"], key=int) будет "2", потому что int("2") < int("11").
  2. У конструктора типа int есть опциональный параметр base, задающий систему счисления:
    int("DEAD", 16) # 57005
    int("2011", 3) # 58
    int("python", 36) # 1570137287
    В частности, это можно использовать для более сжатого хранения чисел:
    # 96 символов - массив предпосчитанных значений
    u = [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790]
    
    # 82 символа - тот же массив, сжатый в строку 36-разрядных чисел
    u = [int(x, 36) for x in '1 1 2 5 E 16 3O BX 13Q 3R2 CYK 19CY 4GI4 FX84 1LBM0 5RSL9 L1U5I 256QK6'.split()]
    К сожалению, столь же мощной обратной функции нет, только несколько частных: hex, oct и bin, преобразующие в 16-, 8- и 2-чные системы счисления соответственно.
  3. У функции sum есть параметр start, который указывает, с какого значения начнется суммирование (по умолчанию равен 0).
    Это можно использовать, если вам вдруг понадобилось преобразовать список списков в список (другими словами, сложить списки):
    sum(l, [])
    К сожалению, строки так складывать запрещено, приходится использовать ''.join.
  4. У функции pow есть опциональный третий параметр, который задаёт модуль, по которому будут производиться вычисления.
    pow(x, y, z) == x**y % z
    Хотя вызов pow длиннее аналогичной записи на операторах, он производит вычисления намного эффективнее, что иногда может оказаться важным.
  5. В функцию input можно передать опциональный параметр, который будет выведен перед началом чтения:
    s = input(x) # эквивалентно print(x, end=''); s = input()

28 Оператор **
Оператор ** выполняет возведение в степень, причём если аргументами были int, возвращается тоже int:
3**4 == 81
Нельзя забывать, что если требуется возвести переменную в квадрат, следует писать более короткое x*x вместо логичного x**2.
С помощью данного оператора можно находить корень числа без подключения модуля math:
49 ** .5 == 7.0

Также этот оператор может быть применён для сокращенного объявления констант:
1000000007 # 10 символов
10**9 + 7 # 7 символов
Иногда требуется задать какую-то константу, которая была бы заведомо больше какого-то числа (например, для создания списка через [0] * n). Несколько примеров:
10**4 == 10000 # 5 символов
5**6 == 15625 # 4 символа

10**5 == 100000 # 5 символов
7**6 == 117649 # 4 символа
Впрочем, если не требуется целочисленность, то для этой задачи подойдет обычный экспоненциальный формат, например, 1e9.

29 Комплексные числа
В геометрических задачах часто возникает задача вычисления корня из суммы двух квадратов.
Обычно это пишут так:
(a*a + b*b)**.5 # 13 символов
((a-c)**2 + (b-d)**2)**.5 # 23 символа
Но лучше использовать комплексные числа:
abs(a + b*1j) # 11 символов
abs(a-с + (b-d)*1j) # 18 символов
Если требуется найти расстояние между точками, заданными кортежем/списком из двух чисел, то может быть удобно конструировать комплексные числа иначе:
c = complex
r = abs(c(*x)-c(*y))

Комплексные числа вообще удобно использовать в геометрии - это на самом деле готовый класс для точек или векторов: их можно складывать, вычитать, умножать на константу, поворачивать и т.д. Рассмотрим несколько интересных случаев.
Как уже упоминалось выше, если мы будем хранить точки комплексными числами, расстояние между ними можно вычислить как модуль разности: abs(a - b).
В задачах на графы иногда возникает необходимость обхода двумерного массива (например, волновым поиском). При этом приходится отписывать 4 варианта: идём вправо, вверх, влево, вниз. Если же хранить текущую позицию комплексным числом, то это можно записать так:
for d in 1, 1j, -1, -1j:
    f(x+d)
# 24 символа
Как известно, умножение на 1j поворачивает вектор на 90 градусов против часовой стрелки (а на -1j - по часовой). Это не только полезно для реализации поворотов налево/направо, но и может быть использовано для сокращения вышеприведенного кода:
d = 1
for _ in '    ':
    f(x+d)
    d *= 1j
 # 23 символа
При использовании комплексных чисел мы сталкиваемся с тем, что слишком длинно получать координаты из комплексного числа: z.real, z.imag. Следовательно, следует свести получение координат к минимуму, пытаясь производить все вычисления в комплексных числах. Однако если мы работаем с двумерным массивом, то необходимость получать координаты возникает при каждом обращении к массиву. Эту проблему можно попробовать решить заменой двумерного массива на словарь (dict) с комплексными числами в качестве ключа. Такое решение может сильно увеличить потребление памяти, поэтому не всегда приемлемо.

30 import
Если импортируемые из модуля объекты используются более одного раза или имя модуля состоит не менее чем из 5 символов, то выгодно использовать инструкцию from module import * вместо import module:
import math
y = math.sin(x) + math.cos(x)
# 35 символов

from math import *
y = sin(x) + cos(x)
# 30 символов

Инструкция импорта позволяет импортировать сразу несколько модулей:
import re, math

31 Стек через односвязный список
В качестве стека принято использовать список:
q = [] # пустой стек
if q: # проверка стека на наличие элементов
q += b, # добавление элемента
q[-1] # последний элемент
*q, b = q # извлечение элемента
Из грустных моментов отметим неэффективное извлечение элемента из стека.
А теперь реализуем стек через односвязный список:
q = 0 # пустой стек
if q: # проверка стека на непустоту
q = q, b # добавление элемента
q[1] # последний элемент
q, b = q # извлечение элемента
Теперь все операции эффективны, а некоторые еще и короче стали! Разумеется, при такой реализации мы уже не можем кратко пробежаться по стеку и эффективно обратиться к элементу по индексу.

32 Одномерные массивы вместо двумерных
Достаточно часто оказывается короче использовать одномерные массивы вместо двумерных. Разберём несколько сценариев использования.
Создание одномерного массива гораздо короче создания двумерного:
M = [[0]*m for _ in ' '*n]
M = n*m * [0]
Чтобы пробежаться по одномерному массиву, нужен один цикл вместо двух. Причём это оказывается короче пробега по двумерному массиву, даже если необходимо знать текущие индексы:
for i in range(n):
    for j in range(m):
     ...
# 30 символов

for k in range(n*m):
    i = k//m
    j = k%m
    ...
# 28 символов
Индексация в одномерном длиннее всего на один символ:
M[i][j] # 7 символов
M[i*m+j] # 8 символов
Но при одномерном подходе есть возможность использовать одномерную индексацию M[k], которая занимает всего 4 символа. В такой одномерной индексации оказывается короче переходить к соседним ячейкам массива:
M[i][j] # текущая
M[i][j+1] # правая от текущей
M[i+1][j] # нижняя от текущей

M[k] # текущая
M[k+1] # правая от текущей
M[k+m] # нижняя от текущей
Для хранения текущей позиции в одномерном массиве нужно одно число, а в двухмерном - два.
В двумерных массивах строки выражены явно, для получения списка столбцов можно использовать выражение zip(*M). В одномерных массивах строки и столбцы можно получать по индексу с помощью срезов:
M[i*m:i*m+m] # i-я строка
M[j::m] # j-й столбец
Как видно из вышесказанного, код для одномерного и двумерного подходов кардинально отличается и сравнивать их очень сложно, поэтому лучше всего попробовать оба варианта и посмотреть, какой выйдет короче в данной конкретной задаче.

Важный класс задач на двумерные массивы - это задачи, в которых есть некая карта и по этой карте необходимо перемещаться (поиском в ширину, заливкой, поиском в глубину, ...). В таких задачах обычно имеются запретные клетки, в которые нельзя двигаться. При движении нельзя выходить за границы карты, поэтому приходится при проверке возможности перехода прописывать множество условий примерно следующего вида:
if i: f(i-1, j)
if j: f(i, j-1)
if i<n-1: f(i+1, j)
if j<m-1: f(i, j+1)
Проблема обостряется в свете переписывания на с двумерного массива на одномерный: для проверок нужны индексы в явном виде, а на их получение при одномерном подходе тратятся дополнительные символы.
Обычным способом избавления от этих проверок является создание дополнительного слоя запретных клеток вокруг имеющейся карты. В результате алгоритм не выходит за границы карты, потому что она окружена запретными клетками.
В Python этот способ обретает второе дыхание благодаря допустимости отрицательных индексов. Поясним на примере. Предположим, что мы добавили запретные клетки справа от карты. Тогда мы автоматически получаем запретные клетки слева от карты: слева от индекса 0 находится индекс -1, который указывает на конец массива, то есть на правую границу карты, которая состоит из запретных блоков! Аналогично, добавив запретные клетки снизу от карты, мы автоматически получаем верхнюю границу.
Карта часто выдаётся в виде списка строк. Если прочитать их через open, то в конце каждой строки окажется символ '\n'. Если при написании кода считать запретными все клетки, не содержащие определённый символ (например, точку), то правая (и, соответственно, левая) граница возникает автоматически. Для завершения границ карты остается добавить строку с запретными символами в конец списка строк.
После избавления от проверок перебор возможных движений при одномерном подходе превращается примерно в следующее:
for d in 1, m, -1, -m:
    f(k+d)

33 Регулярные выражения
Типичные регулярные выражения содержат большое количество обратных слешей (\), которые приходится экранировать. Для решения этой проблемы в Python были введены raw строки, в которых \ интерпретируется как обычный символ:
"\\w+\\s+\\1" # 13 символов, обычная строка
r"\w+\s+\1" # 11 символов, raw строка

Иногда возникает необходимость задать поведение регулярного выражения, например, игнорирование регистра. Документация предоставляет набор флагов, для данного случая подходит re.I (сокращенная версия re.IGNORECASE). Однако эти флаги на самом деле являются просто числами:
print(re.I) # печатает 2
То есть, вместо того, чтобы передавать флаги, передавайте его численное значение. Бонусом получаем более краткое комбинирование флагов:
re.I | re.M # 9 символов
I | M # 3 символа (требует импорта имён из re)
2 | 8 # 3 символа (не требует импорта имён)
10 # 2 символа

Функция match проверяет, что некоторый префикс (начало) строки соответствует заданному шаблону. Чтобы проверить на соответствие шаблону строку целиком, предлагается использовать функцию fullmatch. Однако, символ $ в конце шаблона позволяет добиться нужного эффекта и для функции match:
fullmatch('[a-h]\d-[a-h]\d', s) # 30 символов
match('[a-h]\d-[a-h]\d$', s) # 27 символов

Второй аргумент функции sub указывает, на что заменяются подходящие под шаблон подстроки. В качестве этого аргумента можно передавать не только строку, но и функцию, которая для находимых подстрок должна определять на что они заменятся.

Неиспользованное

Есть еще достаточно большое количество интересных приёмов, которые мне не удалось нигде применить. Однако я мог просто не встретить нужной задачи, либо мог не додуматься до их применения, поэтому перечислю их ниже. Если у меня выйдет где-то их применить - перенесу в основную часть.

34 str.translate
Метод str.translate заменяет все вхождения заданных символов на другие символы либо строки. Замена задаётся словарём, причём в качестве ключа требуется указывать код заменяемого символа:
"data".translate({97: "aaa"}) == "daaataaa" # 97 - код символа 'a'
Метод позволяет производить несколько замен одновременно:
"password".translate({97: "@", 111: "0", 115: "$"}) == "p@$$w0rd"
Если значением является односимвольная строка, то вместо неё можно написать код этого символа:
"password".translate({97: 64, 111: 48, 115: 36}) == "p@$$w0rd" # эквивалентно предыдущему примеру
Если требуется удалить символ, то в качестве значения лучше указывать "" вместо рекомендуемого в документации None:
"what".translate({97: "u", 104: ""}) == "wut"
Возникающие после замены символы не обрабатываются, то есть новой замены для них не производится, поэтому можно заменять символы друг на друга:
"abcd".translate({97: "b", 98: "a"}) == "bacd"
Замену можно задавать не только словарём, но и любым объектом, поддерживающим индексацию (например, список или строка). Пользуясь тем, что тестирующий сервер не подсчитывает пробелы (после недавнего обновления это не всегда верно), получаем:
"abcd".translate("                                                                                                 ba") == "bacd"
В этой строке символ b стоит на 97 позиции, а символ a - на 98.

35 hashable
Ключом словаря или элементом множества может быть только hashable: объект, у которого есть не меняющийся со временем хэш. При модификации изменяемых объектов (списки, множества, словари) меняется и их хэш, следовательно, они не являются hashable. Именно поэтому нельзя создать множество множеств. Для решения этой проблемы было придумано неизменяемое множество frozenset:
{ set() } # TypeError: unhashable type: 'set'
{ frozenset() } # OK
Аналогично, в качестве неизменяемых списков можно использовать кортежи:
{ list() } # TypeError: unhashable type: 'list'
{ tuple() } # OK

36 pass
В Python принято писать pass в местах, где синтаксис требует какое-то выражение, но писать нечего. Вместо pass можно написать любое другое выражение, например 0:
try: ...
except: 0 # подавляем все исключения

37 Используем побочные эффекты
Обычно map рассматривают как способ сгенерировать новую последовательность по уже имеющейся. Функция, передаваемая в map, рассматривается просто как некоторый конвертер из старого значения в новое. Однако давайте изменим смысл работы этой функции: пусть вместо генерации нового значения она будет выполнять некоторую полезную работу:
map(print, L) # выводит все элементы L (но не совсем)
Тут мы сталкиваемся с проблемой ленивости map: так как мы не используем результат её вызова, она не проделывает ни одной итерации. Поэтому нам требуется явно проитерироваться по возвращаемому ей результату. Самый короткий способ сделать это - поискать в нём элемент, которого там заведомо нет:
0 in map(print, L) # выводит все элементы L
Полученный код на 1 символ короче аналогичного цикла:
for x in L: print(x)

В предыдущем примере мы искали элемент, которого нет в коллекции. Однако искать элемент, который там есть, то мы получим итератор, который остановится сразу после искомого элемента:
z = iter(range(7)) # z - итератор на последовательность 0, 1, 2, 3, 4, 5, 6
3 in z # бежит по итератору, пока не встретится 3
print(*z) # выводит "4 5 6"

38 bytes
Подобно тому, как строки являются неизменяемой коллекцией односимвольных строк, bytes является неизменяемой коллекцией однобайтовых чисел:
l = b"golf"
list(l) # [103, 111, 108, 102]
l[2] # 108
108 in l # True
max(l) # 111
Иногда это можно использовать для краткой записи списка небольших чисел. Если числу не соответствует никакой ASCII-символ, то его можно записать с помощью экранирования, например для 128 это будет b'\x80' или b'\200'.
# первые десять чисел Фибоначчи
s = [1,1,2,3,5,8,13,21,34,55] # 27 символов
s = b'\1\1\2\3\5\b\r\25"7' # 24 символа

39 Неожиданный else
У циклов for и while есть блок else, который выполняется, если цикл завершился естественным образом, а не через break.
for x in L: # выводим первое положительное число в L
    if x > 0:
        print(x)
        break 
else: # либо -1, если таких нет
    print(-1)
Также блок else есть у инструкции try: он исполняется, если исключение не возникло.

40 Глобальные переменные
При попытке присвоить значение глобальной переменной внутри функции просто создаётся локальная переменная с таким именем.
Если вы присваиваете какой-то переменной значение внутри функции, то оно всегда присваивается локальной переменной функции, даже если глобальная переменная с таким именем уже есть. Если вы хотите изменить именно глобальную переменную, то нужно явно об этом сообщить:
k = 5
def f():
    global k
    k = 6
f() 
print(k) # выводит "6"
# 31 символ
Однако обращаться к глобальным переменным (и даже модифицировать их, если они изменяемые) разумеется не запрещено, поэтому в некоторых специфических случаях короче использовать список из одного элемента вместо самого элемента:
k = [5]
def f():
    k[0] = 6
f() 
print(*k) # выводит "6"
# 30 символов

пятница, 7 декабря 2012 г.

Сокращение кода на C++ для acmp.ru


ПОСЛЕДНЕЕ ОБНОВЛЕНИЕ: 01.02.2016

Предисловие


Добрый день.
Меня зовут Хворых Павел и я решаю задачи на acmp.ru. В отличие от других сайтов, на acmp лучшими признаются не самые быстрые и экономные программы, а те, которые имеют наикратчайший исходный код. В этой статье я расскажу о некоторых приемах сокращения кода на C++.

В самом начале хочу обговорить несколько важных моментов.
  1. Необходимо знание C++ на уровне немного выше "Hello, World" (потоки, STL), а также отсутствие рвотного рефлекса и желания убивать при взгляде на строчку
    a[y+i%2-~x*60] += 1-i++%2*2;.
  2. При объяснении многих вещей мне приходится опускать многие моменты, так как объяснение каждого из них может вылиться в статью не меньших размеров. Например, я очень неаккуратно ввожу понятия "выражение" и "lvalue". Материалы по этим моментам достаточно легко найти в интернете, но это не требуется для понимания статьи.
  3. Приемы, описанные здесь, абсолютно бесполезны за пределами acmp. Более того, они вредны, так как представляют собой полное игнорирование соглашений о правильном программировании. НИКОГДА не используйте их на практике.
  4. В примерах кода опускается не нужный для понимания приёма код, например, подключение инклудов и префикс std::.
  5. Здесь описаны не все приемы сокращения кода. Из тех, что описаны, многие являются более-менее очевидными.
  6. Компиляторы Microsoft Visual C++ и GNU C++ будут в дальнейшем сокращаться как VC и G++. В случаях, когда версия компилятора не указана явно, подразумевается версия, используемая на acmp (Microsoft Visual C++ 2008 и GNU C++ 5.1.0).

Стандарт C++

У языка C++ есть так называемый стандарт - документ, полностью описывающий язык. Стандарт языка C++ в дальнейшем будет именоваться просто стандартом. Стандарт меняется со временем и разные компиляторы с разной степенью успешности поддерживают разные версии этого стандарта. В 2011 году был опубликован стандарт C++11, добавивший в язык большое количество нововведений. VC 2008, вышедший в 2007 году, фактически не поддерживает этот стандарт, а G++ 5.1.0, вышедший в 2015, поддерживает C++11 полностью. Среди важнейших для сокращения кода нововведений следует отметить auto и range-based for, вкратце описанные здесь.
Также следует заметить, что в компиляторах есть так называемые расширения: не указанные в стандарте возможности языка, реализуемые компилятором. Если ваш код компилируется у вас на компьютере, но не компилируется на acmp, то это означает, что либо вы написали код в более старом/новом стандарте, либо использовали расширения компилятора. Некоторые приёмы используют расширения компилятора, в таких случаях это оговаривается.

1 Общие идеи


1.1 Используйте кратчайший алгоритм
Основой для написания кратчайшего кода является кратчайший алгоритм. Придумать кратчайший алгоритм иногда непросто даже для очень простых задач.
Иногда наиболее краткий алгоритм отличается крайней неэффективностью и следует следить за ограничениями задачи: пройдет ли этот алгоритм? Для этого следует изучить понятие сложности алгоритма (это понятие в любом случае стоит изучить, даже если вы не планируете заниматься сокращением кода).
Например, если вам требуется найти длину кратчайшего пути между двумя вершинами, не спешите применять алгоритм Дейкстры (работает за O(n2)), возможно ограничения позволят применить алгоритм Флойда-Уоршелла (работает за O(n3)), реализация которого намного короче.
Оптимизации алгоритма могут быть микроскопическими. Что короче: обходить массив от начала в конец или с конца в начало? Ответ на этот вопрос меняется от задачи к задаче.

1.2 Изучите стандартную библиотеку
Просмотрите, какие функции, классы, методы этих классов существуют в стандартной библиотеке. В особенности рекомендуется изучить следующие разделы:
  1. Библиотеки C: cstdio, cstring, cstdlib, cmath.
  2. Библиотеки C++: algorithm, string.
  3. Поточный ввод/вывод: методы классов istream и ostream (такие типы имеют объекты cin и cout).
  4. Контейнеры vector, set, map.
Следует отметить, что иногда бывает короче не использовать удобные возможности стандартной библиотеки (тем более что для их использования зачастую требуется подключать соответствующий инклуд), а реализовать их вручную. В частности, использование string редко оправдано.

1.3 Минимум сущностей
Не используйте функции, структуры, классы и всякие другие приятные вещи, придуманные умными людьми для того, чтобы сделать программирование более удобным и понятным. Оптимальнее всего писать весь код программы в main. Возможные исключения:
  1. Бывает удобно использовать рекурсивные функции, например, в алгоритме поиска в глубину.
  2. Требуется оперировать нетривиальными объектами, которые не задаются примитивным типом.
Ко второму исключению следует относится с большой осторожностью. Зачастую можно обойтись без объявления своего типа.
Например, вместо создания массива точек
struct Point { int x, y; };
Point point[10];
иногда можно просто завести массив на каждую координату
int x[10], y[10];
Подобная замена приводит к сокращению одних фрагментов кода и удлинению других, поэтому необходимо рассматривать каждый случай отдельно.

2 Простейшие приёмы


2.1 Используйте однобуквенные переменные
По стандарту у вас есть как минимум 53 возможных однобуквенных имени: 26 строчных латинских букв, 26 заглавных латинских букв и символ подчеркивания.

2.2 Используйте пробелы вместо табуляции
Символ табуляции учитывается при подсчете символов, заменяйте его пробелами. Некоторые IDE заменяют символ табуляции на пробелы автоматически. Многие IDE можно настроить так, чтобы они тоже начали производить такую замену.
С 22.01.16 табуляции перестали учитываться при подсчете длины кода, можно использовать.

2.3 namespace std
Очень редко бывает выгодно использование директивы using namespace std;. Вместо этого следует писать std:: у требующих этого объектов и функций (cin, cout, sort).

2.4 _STD (только для VC)
В компиляторе VC определен дефайн _STD:
#define _STD std::
Например, можно писать _STD cin вместо std::cin.

2.5 Пишите int main
Некоторые объявляют функцию main как void main вместо int main, чтобы не писать return 0. Однако стандарт и так позволяет не писать return 0 в функции main - эта команда выполняется автоматически.
Более того, использование void main запрещено стандартом и поддерживается компиляторами в целях совместимости со старым кодом.

2.6 Пишите main (только для G++)
Если возвращаемым типом функции является int, то его можно опустить. Это правило действует и для функции main: программа main(){} является корректной.
В С существовало правило "неявного int" (или правило "int по умолчанию"). Это правило состоит в том, что если спецификатор базового типа явно не указан, то подразумевается спецификатор int. Впоследствии это правило отменили как в C, так и в C++. Однако, в G++ это правило частично поддерживается в целях совместимости со старым кодом.

2.7 Не используйте void (только для G++)
Ситуация, когда функция должна что-то возвращать, но не возвращает (выполняется до конца, не встретив return), объявлена стандартом неопределённым поведением. VC в таком случае выдаёт ошибку, а G++ всего лишь предупреждение. Благодаря этому можно объявлять функции, не возвращающие значения, как возвращающие int: то есть int f() вместо void f(). Вспомнив предыдущий пункт, выкидываем int из объявления, сокращая код еще на три символа: f().

2.8 Структуры вместо классов
Используйте структуры вместо классов: структуры позволяют ровно то же, что и классы, но все члены у структур публичные по умолчанию.

2.9 Объявление своих типов
После объявления типа можно сразу создавать переменные этого типа. Например,
struct P { int x, y, z; };
P p[10];
сокращается до
struct P { int x, y, z; } p[10];
Если вы вообще не используете имя типа в дальнейшем, то его можно опускать:
struct { int x, y, z; } p[10];

3 Основные приёмы


3.1 Объявление переменных и массивов
  1. Объявляйте массивы статически, присваивая им при этом максимально возможный в данной задаче размер. Например, если требуется считать N чисел и известно, что N <= 3000, то удобнее сразу объявить массив на 3000 элементов (int m[3000];), а не выделять массив на N элементов динамически (int * m = new int[n];).
  2. Используйте глобальные переменные вместо локальных (исключение: рекурсивные функции). Огромным преимуществом глобальных переменных является то, что они автоматически инициализируются нулем. В частности, все элементы глобально объявленного массива инициализируются нулем.
    Замечание: локальные переменные выделяются на стеке, который, как известно, ограничен. Поэтому определение больших локальных статических массивов может приводить к переполнению стека, что вызывает Runtime Error. Размер стека можно увеличить специальной директивой, но это явно не способствует сокращению программы. Во избежание таких проблем объявляйте статические массивы глобально.
  3. Обходитесь минимальным количеством переменных, переиспользуя одну и ту же переменную в нескольких местах. Например, если в программе несколько независимых циклов, то можно использовать во всех этих циклах одну и ту же переменную.
  4. Объявляйте переменные одного типа вместе, одной инструкцией: int i, j, m[10], *p;
У G++ есть важное расширение - Variable-length array (далее VLA) - массив с неизвестным на этапе компиляции размером (этот массив выделяется на стеке). Это даёт возможность написать int m[n] вместо int * m = new int[n] даже когда n является переменной.
Хотя такой массив придется объявлять в отрыве от остальных переменных (так как мы уже должны были объявить и считать переменную n), мы экономим на размере массива (пишем m[n] вместо m[10000]), что иногда позволяет сэкономить символы.
Также можно создавать многомерные VLA: int m[n][n];.

3.2 Используйте минимальные инклуды
В C++ для многих сишных инклудов name.h ввели замену cname. Например, можно писать cstdio вместо stdio.h, что экономит 1 символ. Также, многие инклуды включают в себя другие инклуды, например в VC можно не подключать cstdio, если вы подключили iostream. Но тут следует быть осторожным: такое поведение не стандартизировано и может меняться от одной версии компилятора к другой. Например, в последних версиях VC подключение iostream автоматически подключает cmath, но в VC 2008, используемой на acmp, приходится подключать cmath явно.
В G++ идея минимальных инклудов имеет мощную поддержку в виде инклуда bits/stdc++.h, который подключает все имеющиеся в языке инклуды. Используйте его, если вам нужно подключить больше одного инклуда.

3.3 Используйте наиболее краткие типы
Везде, где это возможно, пытайтесь использовать более краткие типы:
  1. int вместо bool/char/short (int занимает больше памяти, но это редко бывает критично).
  2. int вместо long (в используемых на acmp компиляторах long == int).
  3. __int64 (VC) / int64_t (G++) вместо long long.
  4. size_t вместо unsigned int. size_t равен unsigned int в силу того, что компиляторы acmp настроены под 32-битную платформу. При компиляции под 64-битную платформу size_t равен unsigned long long.
Внимательно изучите, какой размер в байтах и какой диапазон значений имеет каждый тип.

3.4 Уберите лишние скобки
Изучите таблицу приоритетов и ассоциативностей операций в C++ и не ставьте скобок там, где они не нужны. Например, важно знать, что приоритет оператора && выше приоритета оператора ||.
Иногда требуется немного видоизменить выражение, чтобы избавиться от скобок:
(a*b)/(c*d) // начальное выражение
a*b/(c*d) // избавились от лишних скобок
a*b/c/d // раскрыли скобки
Ниже будут разобраны различные техники избавления от скобок.

4 Неявная конвертация

Важной для сокращения кода чертой языка C++ является неявная конвертация: автоматическое приведение одного типа к другому без необходимости явного указания. Например, конвертация между всеми примитивными типами может быть осуществлена неявно (правда в некоторых случаях компилятор будет выдавать предупреждения). Благодаря этому можно легко оперировать объектами разных типов в одном выражении.

4.1 Конвертация в bool
В местах где ожидается bool, примитивные типы автоматически преобразуются в bool. Для числовых типов (в том числе вещественных) и указателей преобразование в bool равносильно сравнению с нулём: (bool)x тождественно x != 0. Местами, где ожидаются bool, являются, в частности, условия операторов if, while, for. Рассмотрим примеры.
  1. if(x != 0) можно записывать просто как if(x).
  2. if(x != n) можно записать как if(x - n != 0), что может быть сокращено до if(x - n).
Так как последним символом строки в C++ является символ с нулевым кодом, проход по строке можно записывать как
for(i=0; s[i] != 0; i++)
Приведенное свойство позволяет сократить этот шаблон:
for(i=0; s[i]; i++)

4.2 Конвертация из bool
true при конвертации в число преобразуется в 1, а false – в 0.
  1. Выражение if(x == 5) s++; можно заменить на s += (x == 5);. Полученное выражение можно дополнительно сократить, убрав избыточные скобки: s += x == 5;.
  2. Если аргументами оператора && являются выражения типа bool, а результат работы оператора используется как bool, то его можно заменить на оператор &. Например, вместо if(10 < x && x < 30) можно писать if(10 < x & x < 30). Данный приём применим не всегда, так как оператор & имеет больший приоритет, чем оператор &&.
    Аналогично для операторов || и |.
4.3 Конвертация из char в int
Символ в C++ – это число. Это число называется кодом символа. Коды символов можно узнать, посмотрев в ASCII-таблицу.
  1. Можно писать код символа вместо самого символа во всех выражениях (кроме инструкций, где важно наличие переменной именно типа char, например, вывод через потоки). Например, вместо if(c == 'B') можно писать if(c == 66).
  2. Если требуется вывести код символа, то необходимо преобразовать символ в число, что можно записать как int(c) или (int)c. Но если вспомнить, что компилятор C++ автоматически конвертирует небольшие типы (char, short и подобн.) в int при осуществлении арифметических операций, то можно записать это короче: +c.
    char c = 'a';
    cout << c; // выводит 'a'
    cout << +c; // выводит '97'
  3. Следует отметить, что символы в ASCII-таблице располагаются не случайным образом. Например, цифры, заглавные и строчные буквы английского алфавита располагаются по порядку. Поэтому мы можем писать 'a' <= c && c <= 'z' для проверки того, является ли символ строчной буквой. Воспользовавшись предыдущим пунктом, сокращаем это до 65 <= c && c <= 90, что можно сократить еще сильнее до 64 < c && c < 91. Аналогичным образом мы можем проверить, является ли символ цифрой: 47 < c && c < 58.
  4. Упорядоченность символов в ASCII-таблице позволяет легко определять цифру, изображенную на символе. Для этого достаточно вычесть из данного символа 48 (код символа 0):
    с - 48
    Аналогичным образом можно определять номер данной буквы в алфавите: c - 65 для заглавных и c - 97 для строчных. Эта идея позволяет кратко записать преобразование шестнадцатеричной цифры (0123456789abcdef) в число:
    c % 87 % 48
  5. Предположим, что нам дана заглавная латинская буква и нам надо преобразовать её в строчную. Заглянув в ASCII-таблицу, убеждаемся, что для любой латинской буквы строчная версия имеет код ровно на 32 больший, чем заглавная версия. Значит, искомый код будет выглядеть следующим образом:
    с += 32;
    Если перед выполнением кода в переменной c хранился символ с кодом 66 (то есть символ 'B'), то после его выполнения там будет хранится символ с кодом 98 (то есть символ 'b').

4.4 Конвертация istream в bool
Для сложных типов преобразование в bool вызывает operator bool(), если таковой определен. Важным примером такого типа является класс istream (экземпляром которого является cin). operator bool() у потока возвращает false, если при работе с потоком произошла какая-либо ошибка, например, попытка чтения при отсутствии данных для чтения. Рассмотрим использование этого свойства на примере. Пусть в задаче дан список из N точек. Каждая точка состоит из двух чисел. Наивный код:
for(i=0; i<n; i++)
  cin >> x[i] >> y[i];
operator bool() позволяет выполнять считывание жадно, то есть до тех пор, пока во входном потоке есть данные:
for(i=0; cin >> x[i] >> y[i]; i++);
Этот код короче исходного на 3 символа.

Дальше идёт объяснение того, как это работает, для сокращения кода оно не требуется
У класса istream (экземпляром которого является объект cin) перегружен оператор >>, поэтому выражение cin >> x интерпретируется компилятором как cin.operator>>(x). Метод istream::operator>> возвращает объект, у которого он был вызван, в данном случае это cin. Это нужно для того, чтобы мы могли делать так называемые "каскадные вызовы": cin >> x >> y. Это выражение выполняется следующим образом: сначала у объекта cin вызывается метод operator>>, который осуществляет считывание переменной x, после чего возвращает объект cin, у которого снова вызывается метод operator>>, который осуществляет считывание переменной y, после чего возвращает объект cin.
Из вышесказанного делаем следующий вывод: выражение cin >> x[i] >> y[i] из примера возвращает cin. Этот возвращаемый cin попадает в условие продолжения цикла и преобразуется в bool. Пока во входном файле есть числа, считывание происходит успешно, поток cin находится в корректном состоянии и при преобразовании в bool возвращает true. Как только во входном файле заканчиваются числа, выполнение выражения cin >> x[i] >> y[i] переводит поток cin в состояние ошибки и при преобразовании в bool он возвращает false, прекращая цикл.

5 Выражения

Для понимания дальнейшего материала важно изучить такие сущности, как выражения. Выражение – это некая комбинация переменных и операций над этими переменными. Свойством выражений является то, что они возвращают результат. Примеры выражений:
x // возвращает переменную x
++x // возвращает переменную x
x + y * 12 // возвращает число
x > 10 ? 1 : -1 // возвращает число
"456" // возвращает строку
x = 67  // возвращает число
sin(3.14)  // возвращает double
cout << x // возвращает cout
Инструкции, содержащие управляющие конструкции (if, for, while, return, break и.т.д.), выражениями не являются. Важным свойством выражений является то, что их можно записывать через запятую. При этом вся эта конструкция также является выражением, которое возвращает результат последнего в списке выражения:
x += 3, y -= 4 // возвращает y
Выражения можно сочетать причудливым образом:
cout << (x += 3, y -= 4)
// прибавляет 3 к x, отнимает 4 от y, выводит y, возвращает cout
Логическим выражением будем называть выражение, которое может быть преобразовано к bool. Как следует из предыдущего раздела, все приведенные в данном отступлении выражения являются логическими.

5.1 Экономия фигурных скобок
Тело операторов if, else, while, for должно обрамляться фигурными скобками. Однако если это тело состоит всего из одной инструкции, то фигурные скобки писать необязательно. Зачастую количество инструкций в теле можно уменьшить до одной и избавиться от фигурных скобок. Рассмотрим пример:
while(cin >> x)
{
  s += x;
  cout << s;
}
Тело while состоит из двух инструкций, каждое из которых является выражением. Запишем выражения через запятую:
while(cin >> x)
{
  s += x,
  cout << s;
}
Теперь тело while состоит всего из одной инструкции, что позволяет убрать фигурные скобки и сэкономить два символа:
while(cin >> x)
  s += x,
  cout << s;

5.2 Тернарный оператор
Тернарный оператор имеет вид boolean_expr ? expr1 : expr2, где expr1 и expr2 представляют собой выражения, а boolean_expr – логическое выражение. Выражения expr1 и expr2 должны иметь общий тип (не обязательно совпадающий). Тернарный оператор сам по себе является выражением и типом этого выражения является как раз этот общий тип. Во многих случаях можно заменить условие if на тернарный оператор:
if(x > 2) y = 3; // 11 символов
x > 2 ? y = 3 : 0; // 10 символов
При этом могут получаться достаточно сложные конструкции:
if(x < y)
  s = "1";
else if(x == y)
  s = "draw";
else
  s = "2";
// 44 символа
эквивалентно
s = x < y ? "1" : x == y ? "draw" : "2";
// 26 символов
Полезным примером использования тернарного оператора является нахождение максимума/минимума двух чисел:
a>b?a:b // max(a, b)
a<b?a:b // min(a, b)
Рассмотрим нетривиальный пример:
if(x > 10) cout << y; // 16 символов
сокращаем до:
x > 10 ? cout << y : 0; // 15 символов
Однако этот код не компилируется, потому что cout << y и 0 имеют несовместимые типы: ostream и int соответственно. Мы можем схитрить и использовать запятую:
x > 10 ? cout << y, 0 : 0; // 17 символов
Выражения cout << y, 0 и 0 имеют одинаковый тип int, поэтому код корректен. Хотя в полученном коде на 1 символ больше, чем в изначальном, мы избавились от if, т.е. получили выражение, что открывает простор для дальнейших оптимизаций.

При использовании тернарного оператора часто возникает необходимость использовать в качестве expr1 и expr2 сразу списки выражений:
if(z > 5) { cout << x; x += 3; }
else { cout << y; y += 4; }
пытаемся сократить до
z > 5 ? cout << x, x += 3 : cout << y, y += 4;
Но если для expr1 использование списка выражений корректно, то для expr2 мы сталкиваемся с проблемой приоритетов операций: тернарный оператор имеет больший приоритет, чем оператор запятая и вышеуказанное выражение интерпретируется следующим образом:
(z > 5 ? cout << x, x += 3 : cout << y), y += 4;
Данную проблему всегда можно решить расстановкой дополнительных скобок:
z > 5 ? cout << x, x += 3 : (cout << y, y += 4);
Но иногда возможно более оптимальное решение. Например, если списком выражений является только expr2, то можно заменить условие тернарного оператора на противоположное, поменяв expr1 и expr2 местами:
z > 5 ? x += 3 : (cout << y, y += 4); // 24 символа
сокращается до
z < 6 ? cout << y, y += 4 : x += 3; // 22 символа

Тернарный оператор допускает вариант, когда выражения expr1 и expr2 оба имеют тип void. В этом случае, выражение, состоящее из тернарного оператора, также имеет тип void. Выражение имеет тип void, например, если оно представляет собой вызов функции, возвращающей void.

Если expr1 и expr2 оба являются lvalue-выражениями и имеют одинаковый тип, то всё выражение с тернарным оператором тоже является lvalue. lvalue – это грубо говоря то, чему можно присвоить значение. Например, lvalue являются следующие выражения:
x
++x
x += 4
m[x]
Из этого следует достаточно интересное свойство тернарного оператора: код
if(condition)
  x = 4;
else
  y = 4;
можно записать как
(condition ? x : y) = 4;
если x и y являются переменными одного типа.

5.3 Логические операторы && и ||.
Логические операторы && и || должны участвовать в выражениях вида
boolean_expr1 && boolean_expr2
boolean_expr1 || boolean_expr2
то есть оба операнда оператора должны являться логическими выражениями. Операторы && и || обладают интересным эффектом: если значения первого аргумента достаточно, чтобы узнать результат выражения, то второй аргумент не вычисляется:
a && b эквивалентно a ? b : false
a || b эквивалентно a ? true : b
Этот эффект позволяет использовать логические операторы как альтернативу if и тернарному оператору. Рассмотрим код из предыдущего примера:
x > 10 ? cout << y, 0 : 0; // 17 символов
Поскольку cout << y является логическим выражением, можно написать более лаконичный код:
x > 10 && cout << y; // 14 символов

5.4 for вместо while
Выражение while(...) занимает столько же символов, сколько и for( ;...; ). Однако у for есть два дополнительных места, куда можно вставлять выражения: перед первой точкой с запятой (выполняется перед началом цикла) и после второй точки с запятой (выполняется после каждой итерации). Благодаря этой возможности часто можно сэкономить пару символов:
cin >> n;
while(cin >> a)
  s += a, cout << s;
// 33 символа
сокращается до
for(cin >> n; cin >> a; cout << s)
  s += a;
// 31 символ

5.5 Краткая запись циклов
Рассмотрим следующий код:
int i, m[5];
int main()
{
  for(i=0; i<5; i++)
    cin >> m[i];
}
// 47 символов
Заметим, что переменная i уже равна 0, так как объявлена в глобальной области, а значит нет необходимости в инструкции i=0 в цикле. Также можно перенести инструкцию i++ внутрь тела и совместить её с инструкцией cin >> m[i]:
int i, m[5];
int main()
{
  for(; i<5; )
    cin >> m[i++];
}
// 43 символа

Рассмотрим следующий код:
int i, m[5];
int main()
{
  for(i=4; i>0; i--)
    cin >> m[i];
}
// 47 символов
Заметим, что инструкцию i=4 можно "исполнить" прямо на этапе создания переменной i, сразу инициализировав её значением 4. Также перенесём инструкцию i-- внутрь тела и совместим её с инструкцией cin >> m[i]:
int i=4, m[5];
int main()
{
  for(; i>0;)
    cin >> m[i--];
}
// 45 символов
Теперь заметим, что цикл продолжается до тех пор, пока i больше 0, то есть до тех пор, пока i не станет равно 0. Значит условие i>0 можно заменить на условие i != 0. Вспоминая совет 4.1, в свою очередь заменяем i != 0 на i:
int i=4, m[5];
int main()
{
  for(; i;)
    cin >> m[i--];
}
// 43 символа

Есть интересный способ сэкономить 1 байт. Пусть у нас есть два цикла подряд:
int i, m[5];
int main()
{
  for(; i<5; )
    cin >> m[i++];
  for(i=0; i<5; )
    cout << m[i++];
}
// 72 символа
Заметим, что во убрать инструкцию i=0 во втором цикле не получилось, так как i уже не равно 0. В этом случае выгодно объявить новую глобальную переменную j и использовать её:
int i, j, m[5];
int main()
{
  for(; i<5; )
    cin >> m[i++];
  for(; j<5; )
    cout << m[j++];
}
// 71 символ

Рассмотрим задачу "найти наибольшее из чисел". В первой строке файла расположено количество чисел N, в следующей строке записано N чисел. Пишем решение задачи:
int i, n, x, a;
int main()
{
  for(cin >> n; i<n; i++)
    cin >> x,
    x>a ? a=x : 0;
}
// 58 символов
Воспользуемся приёмом из совета 4.4:
int n, x, a;
int main()
{
  for(cin >> n; cin >> x;)
    x>a ? a=x : 0;
}
// 49 символов
Заметим, что у нас пропала необходимость в переменной n. Однако она есть во входном файле и её надо куда-то прочитать. Заметим, что на следующей инструкцией происходит чтение в переменную x и её предыдущее значение затирается. Это позволяет нам считать ненужное значение в переменную x:
int x, a;
int main()
{
  for(cin >> x; cin >> x;)
    x>a ? a=x : 0;
}
// 47 символов

При переносе инструкций инкремента внутрь кода следует быть очень внимательным, чтобы не сломать логику кода. Также можно напороться на неопределенное поведение (undefined behaviour). Пример кода с неопределенным поведением:
cout << a[x] + b[x++];
Это связано с тем, что оператор + не является точкой следования и компилятор может вычислять аргументы суммы a[x] и b[x++] в произвольном порядке: он может посчитать a[x] перед b[x++] и получить a[x] + b[x], а может посчитать b[x++] перед a[x] и получить b[x] + a[x+1]. Причем это поведение может зависеть от операционной системы, платформы, компилятора, версии компилятора, флагов компиляции и так далее. Для интересующихся C++ рекомендуется почитать о точках следования дополнительно, например, здесь. Впрочем, никто не мешает попробовать сдать на acmp код с неопределенным поведением, надеясь, что он скомпилируется именно так, как вам нужно.

6 Специфические приёмы


6.1 Битовая арифметика
Побитовые операции позволяют совершать некоторые интересные вещи.
  1. Выражение ~n эквивалентно выражению -n-1 и равняется 0 тогда и только тогда, когда n равно -1. Это позволяет заменять условие n != -1 на ~n, так же как n != 0 можно заменять на n (совет 4.1), Такие условия возникают в убывающих циклах в виде n >= 0 и n > 0 (совет 5.5).
    Также оператор ~ может быть полезен для сокращения выражений, где прибавляется/отнимается 1, например выражение a+b+1 можно сократить до a-~b, а выражение a-b-1 до a+~b.
  2. Выражения ~-n и -~n эквивалентны выражениям n-1 и n+1 соответственно. Унарные операторы имеют значительно больший приоритет, чем оператор сложения, что позволяет использовать это приём для избавления от скобочек: 3*(n+1) можно сократить на 2 символа до 3*-~n.
  3. Инструкция x ^= y ^= x ^= y; меняет значения переменных x и y местами.
  4. Выражение n & (n-1) равняется 0 тогда и только тогда, когда n является степенью двойки либо нулём. На самом деле есть еще один вариант, когда это выражение равно 0 - это минимальное возможное значение знаковых типов: -231 (INT_MIN) для int и -263 (LLONG_MIN) для long long. Это исключение возникает потому что знаковое число -231 представляется в памяти как беззнаковое число 231, которое является степенью двойки (для интересующихся гуглить "дополнительный код").
В двух следующих приёмах я буду подразумевать, что все числа являются неотрицательными. Для отрицательных чисел эти приёмы тоже применимы, но требуют некоторых замечаний и уточнений, описание которых заняло бы достаточно много места.
  1. Операции битового сдвига x >> n и x << n эквивалентны делению/умножению x на n-ую степень двойки (например, 3<<4 == 3*2*2*2*2 == 48). В частности, 1<<n равняется n-ой степени двойки (например, 1<<8 == 256).
    Это бывает удобно для создания больших массивов: например, если требуется создать массив на 1000000 элементов, можно просто создать чуть больший массив на 1<<20 == 1048576 элементов, сэкономив 2 символа.
    Следует отметить, что операторы битового сдвига имеют очень маленький приоритет, что иногда позволяет использовать их для сокращения: (x+y)/2 можно сократить на 1 символ до x+y>>1.
  2. В случаях, когда y является степенью двойки, выражение x%y можно заменить на x&y-1. Например, выражение x%2 можно заменить на x&1. Оператор & имеет намного меньший приоритет, чем оператор %, что иногда позволяет использовать его для сокращения: (x+1)%2 можно сократить до x+1&1. Кстати, конкретно этот пример можно сократить еще на один символ: ~x&1.

6.2 Числовые литералы
Литералами называются константы, записанные в коде. Литералы бывают 4 видов: целые числа (157, 0xFE), числа с плавающей запятой (0.2, 0.2E-01), символы ('c') и строки ("dog"). К литералам можно приписывать суффиксы, которые задают литералу конкретный тип:
4u // эквивалентно (unsigned int)4
4ll // эквивалентно (long long)4
Это может быть удобно, когда требуется перемножить числа по модулю, при этом результат умножения может выйти за рамки типа int:
(a * b) % p // переполнение int при умножении a на b
Выходом может быть замена типов переменных a и b на long long. Однако это может критически замедлить программу, поэтому приходится явно говорить компилятору, что необходимо проводить умножение не в int-ах, а в long long-ах. Для этого достаточно привести один из аргументов к long long:
((long long)a * b) % p // избавились от переполнения ценой 10 символов
Числовые литералы предоставляют более лаконичное решение:
(1ll * a * b) % p // избавились от переполнения ценой 4 символов
Это работает потому что 1ll изначально имеет тип long long и поэтому все умножения автоматически производятся над long long.

Аналогичный приём применим в случае, когда необходимо преобразовать число к double, например, при выполнении деления:
(double)a / b // 11 символов
можно сократить до
1.0 * a / b // 7 символов
Если слева или справа от точки у числа стоит 0, то его можно опустить:
.4 // то же, что 0.4
2. // то же, что 2.0
Это позволит сократить код еще сильнее:
1. * a / b // 6 символов

Другими полезными литералами являются числа с плавающей запятой, записанные в экспоненциальном (научном) формате: литерал 1e6 эквивалентен литералу 1000000.0. Это может быть удобно в коде, когда необходимо иметь дело с большими константами, например, когда требуется завести заведомо большое число: int M = 1e6 на 2 символа короче, чем int M = 1<<20. Нужно помнить о том, что литералы с плавающей точкой нельзя использовать при задании размера массивов, а использование этих литералов в арифметических выражениях может приводить к ошибкам округления.

6.3 Округление
При приведении вещественного числа к целому типу оно округляется в сторону нуля, то есть дробная часть просто отбрасывается:
int(x) // округление в сторону нуля
Однако иногда нам требуется округлить число к ближайшему целому, в этом случае используется следующий приём:
int(x + .5) // округление до ближайшего целого, работает при неотрицательном x
При делении одного целого числа на другое, оно делится нацело, то есть дробная часть деления просто отбрасывается:
x / y // деление с округлением в сторону нуля
Однако иногда нам требуется поделить с округлением вверх, в этом случае используется следующий приём:
(x+y-1) / y // деление с округлением вверх, работает при неотрицательных x,y
Например, чтобы поделить на 2 с округлением вверх, можно написать (x+1) / 2. Битовая арифметика позволяет сократить этот код до -~x / 2.

6.4 Указатели
В случаях, когда выполняется обход по массиву, бывает оптимальней использовать указатели. Рассмотрим простую задачу: на вход подается строка S длиной не более 100 символов и символ C. Требуется вывести строку, полученную из строки S удалением всех вхождений символа С. Пользуясь приемами, описанными в статье, пишем следующий код:
char s[101], c;
int i;

int main()
{
  for(cin >> s >> c; s[i]; i++)
    s[i] - c && cout << s[i];
}
// 71 символ
Использовав указатель p вместо индекса i, получаем более короткое решение:
char s[101], c, *p=s;

int main()
{
  for(cin >> s >> c; *p; p++)
    *p - c && cout << *p;
}
// 65 символов

6.5 Дефайны
Дефайны позволяют давать кускам кода имена и в дальнейшем вместо этих кусков кода вставлять эти имена. В обычном коде использование дефайнов зачастую сводится к простому определению констант:
#define N 3000
Однако дефайны гораздо мощнее: они позволяют определять любую последовательность токенов. Рассмотрим это на примере кода, который возник в совете 5.5:
int x, a;
int main()
{
  for(std::cin >> x; std::cin >> x;)
    x>a ? a=x : 0;
}
// 57 символов
Заметим, что в коде есть длинный повторяющийся кусок кода: std::cin >> x;. Задефайним его:
#define X std::cin >> x;
int x, a;
int main()
{
  for(X X)
    x>a ? a=x : 0;
}
// 55 символов
Несколько замечаний о дефайнах:
  1. Для определения того, насколько сократится код после применения определённого дефайна, я использую следующий алгоритм: вычисляем количество символов в определении дефайна, вычисляем количество применений дефайна, уменьшаем оба числа на 1, перемножаем их и вычитаем из результата 9. В приведенном примере в определении дефайна было 12 символов, он был применен 2 раза, отсюда получаем, что сокращение кода будет равно 11*1 - 9 = 2 символа.
  2. Определение дефайна может включать имена других дефайнов. То есть можно дефайнить фрагменты кода, в которых уже использовались другие дефайны.
  3. Иногда задефайниванию поддаются совсем небольшие куски кода. Например, если в коде по меньшей мере 6 раз встречается взятие индекса массива [i], то его выгодно задефайнить.
    Иногда для одного массива используется несколько индексов, например s[i] и s[j]. В этом случае полезно вспомнить, что s[i] для указателей и массивов эквивалентно *(s+i), а значит s[i] == *(s+i) == *(i+s) == i[s]. Поэтому мы можем заменить s[i] и s[j] на i[s] и j[s] и задефайнить [s].
    Часто выгодно объявить одномерный массив вместо двумерного, например int m[10000] вместо int m[100][100]. Казалось бы, что из-за этого придется вместо m[x][y] писать m[n*x+y], что длиннее на 1 символ. Однако заметим, что при каждом обращении к массиву будут возникать 4 символа m[n*, поэтому их можно задефайнить.
Иногда выгодно применять дефайны с параметрами (такие дефайны называются макросами). В макросах вам могут пригодится операторы препроцессора # и ##. О макросах вкратце здесь. Примером применения макросов может служить алгоритм Флойда-Уоршелла. Рассмотрим фрагмент кода этого алгоритма:
for(k=0; k<n; k++)
  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
// 48 символов
Применим макрос:
#define F(x) for(x=0; x<n; x++)
F(k)
  F(i)
    F(j)
// 39 символов
Проводить сокращение кода дефайнами следует в последнюю очередь, когда все остальные оптимизации уже проведены, иначе можно легко запутаться в своем коде. Иногда получаемый код поддается сокращению дефайнами только после существенных переделок, возможно даже увеличивающих размер кода. Поэтому в некоторых случаях следует писать код сразу с оглядкой на последующее применение дефайнов.

6.6 [Устарело] Использование файловых потоков (только для VC)
На сайте в качестве примера программы на C++ приведен следующий код:
std::ifstream I("input.txt");
std::ofstream O("output.txt");
Эти строки можно переписать немного по другому:
std::fstream I("input.txt"), O("output.txt", std::ios_base::out);
Объяснение того, как это работает довольно обширно, поэтому я ограничусь следующим фактом: поток I обращается с файлом так, как это делает fopen с флагом "r+", а поток O – как fopen с флагом "w". Посмотрев заголовочные файлы, можно выяснить, что std::ios_base::out – это обычная константа, равная 2. И этот факт позволяет нам записать конечный вариант, который короче исходного на 12 символов:
std::fstream I("input.txt"), O("output.txt", 2);